Workspace Code & DSA
Learning pathsPricingA
← DSA problem library

DSA-145 · FOCUSED PRACTICE

Queue Reconstruction by Height

Advanced · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 22623 deterministic checks. Learner drafts are not executed.

Understand the problem

Each input occurrence [height,k] describes one person who must have exactly k people of greater or equal height before them in the final queue. Reconstruct a queue satisfying every occurrence, or reject infeasible constraints.

  • people is a non-null int[][] with 0..2000 rows. Each row is non-null, has exactly two entries, has nonnegative signed-int height, and has k in 0..n−1. Null outer/row values throw NullPointerException; shape, range, size, or infeasibility errors throw IllegalArgumentException.
  • Return a fresh outer array with fresh two-entry rows and the same multiset of [height,k] occurrences. Preserve caller values, row identities, and order, including aliased input rows. Equal values still represent separate people; impossible duplicate constraints must be rejected. Empty input returns a fresh empty array.
  • Greater or equal includes equal-height predecessors. A valid input need not come with a feasibility promise. Sort a deep private copy by height descending and k ascending, insert at zero-based index k, then verify every final count. Return any valid value arrangement; original person identities are not part of the output contract.

Examples

  1. Input: people=[[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
    Output: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

    Each final prefix contains exactly the stated number of people at least as tall.

  2. Input: people=[[6,0],[5,0]]
    Output: [[5,0],[6,0]]

    Inserting the shorter person at zero does not change the taller person’s qualifying count.

  3. Input: people=[[5,0],[5,0]]
    Output: IllegalArgumentException

    Two equally tall people cannot both have zero equally-or-taller predecessors.

Before you start

  • Stable comparator reasoning and dynamic-array insertion
  • Inductive invariants and permutation feasibility

Recognize the structure

Process people in an order that makes their constraints become literal positions. If everyone already inserted is at least as tall as the current person, then every preceding inserted person counts and inserting at index k satisfies the current constraint. Later strictly shorter people cannot affect taller counts. Equal heights require ascending k so their order is already compatible; infeasible repeated [height,k] rows need a final validation rather than an assumption of validity.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

No unsaved text changes · 132/20,000 characters

Self-review

Use the checklist to test your explanation. Checks apply to this visit.

Try before revealing

Hint 1

In what processing order would every already placed person count toward the current k?

Hint 2

If every existing person qualifies, where should a new person with count k be inserted?

Hint 3

Sort by descending height and ascending k, insert at k, then verify feasibility under the stated contract.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Enumerate permutations of physical occurrences

Deep-copy and validate the input, then backtrack over every unused occurrence to build a queue. At a complete permutation, count qualifying predecessors for each person and accept if all constraints hold. If every permutation fails, throw IllegalArgumentException. This O(n!·n²) upper-bound time and O(n) workspace plus output is a tiny-input reference. Distinct occurrences with the same values are still separately permuted; duplicate-value pruning is not necessary for the bounded test cases.

Improve the baseline

Make caller ownership explicit

Cloning only the outer array still exposes caller rows to sorting or result mutation. Clone each row after shape and range validation, sort that private matrix, and return the inserted private rows. Output rows share neither outer nor inner arrays with input.

Sort taller people before shorter people

When placing [h,k], every already placed row has height at least h. No binary search for a qualifying subset is necessary: all current positions qualify. Use comparingInt(...).reversed().thenComparingInt(...) rather than subtraction, so full-width heights remain safe.

Break equal-height ties by increasing k

An equal-height person with a smaller required predecessor count must appear before one with a larger count in a valid final queue. Ascending k respects this order. Inserting equal heights with the same k would shift an earlier equal person and invalidate its count, which is why such input cannot be silently accepted.

Insert at k and understand shifting

Before insertion, k existing people must precede the new person. ArrayList.add(k,person) shifts all positions k and later one step right. Later shorter people may change numeric positions of taller people without changing their qualifying predecessor counts.

Check feasibility on both boundaries and final meaning

If k exceeds the current queue size, there are not enough previously placed qualifying people and the constraints are impossible. After all insertions, explicitly recount every result prefix; this rejects contradictions such as duplicate equal-height k values. The final pass also keeps the public infeasibility contract visible rather than depending on an undocumented platform promise.

Why it is correct

Sorted order is forced for equal heights

For two equal-height people in any valid queue, the later person counts at least the earlier person plus that earlier person itself. Its k is strictly larger. Thus equal-height k values must be distinct and increasing in their relative order.

Insertion preserves all feasible prefix constraints

Assume previously processed constraints are satisfied. The new person sees exactly k existing people before them, all qualifying. A strictly shorter insertion cannot affect any taller count. A later equal-height row has a greater k, so it is inserted after earlier equals in a feasible instance and does not alter their counts. The induction establishes the complete valid queue.

Rejection and output correctness

In a feasible queue, a processed person has k qualifying predecessors among already processed taller people and earlier equals, so k cannot exceed their count. A too-large index is therefore impossible. The final validation rejects every remaining contradiction and accepts only exact counts. Deep copying and insertion preserve the occurrence multiset and caller arrays. Finite sorting, insertion, and verification terminate.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.Objects;

public final class Solution {
    private Solution() {}
    private static int[][] copy(int[][] people) {
        Objects.requireNonNull(people, "people");
        if (people.length > 2_000) throw new IllegalArgumentException("too many people");
        int[][] sorted = new int[people.length][];
        for (int i = 0; i < people.length; i++) {
            Objects.requireNonNull(people[i], "person");
            if (people[i].length != 2 || people[i][0] < 0 || people[i][1] < 0 || people[i][1] >= people.length) {
                throw new IllegalArgumentException("expected [nonnegative height, k in 0..n-1]");
            }
            sorted[i] = people[i].clone();
        }
        return sorted;
    }
    private static boolean valid(int[][] queue) {
        for (int i = 0; i < queue.length; i++) {
            int count = 0;
            for (int j = 0; j < i; j++) if (queue[j][0] >= queue[i][0]) count++;
            if (count != queue[i][1]) return false;
        }
        return true;
    }
    public static int[][] reconstructQueue(int[][] people) {
        int[][] sorted = copy(people);
        Arrays.sort(sorted, Comparator.<int[]>comparingInt(p -> p[0]).reversed().thenComparingInt(p -> p[1]));
        List<int[]> queue = new ArrayList<>();
        for (int[] person : sorted) {
            if (person[1] > queue.size()) throw new IllegalArgumentException("infeasible constraints");
            queue.add(person[1], person);
        }
        int[][] result = queue.toArray(int[][]::new);
        if (!valid(result)) throw new IllegalArgumentException("infeasible constraints");
        return result;
    }
    // Enumerate input-occurrence permutations; factorial, tiny inputs only.
    public static int[][] baseline(int[][] people) {
        int[][] input = copy(people), result = new int[input.length][];
        if (!search(input, result, new boolean[input.length], 0)) throw new IllegalArgumentException("infeasible constraints");
        return result;
    }
    private static boolean search(int[][] input, int[][] result, boolean[] used, int at) {
        if (at == input.length) return valid(result);
        for (int i = 0; i < input.length; i++) if (!used[i]) {
            used[i] = true;
            result[at] = input[i];
            if (search(input, result, used, at + 1)) return true;
            used[i] = false;
        }
        return false;
    }
}

Read the meaningful blocks

Validate and deep-copy each occurrence

The size limit supports the intentional quadratic algorithm. Full signed-int nonnegative heights and bounded k values are checked without inventing a uniqueness promise.

Use the exact comparator and index

Height is descending, k ascending. Reversing the whole compound comparator would reverse the k tie too. The insertion index is the required count itself, with no +1 correction.

Verify the materialized queue

For each result row, count earlier rows whose height is >= its height. Equal-height inclusion is essential. Reject any mismatch, then return the fresh matrix; no caller row becomes reachable through the result.

Complexity

Sorting takes O(n log n), ArrayList insertions take O(n²) in the worst case, and final constraint verification takes O(n²). Overall time is O(n²). Private row copies, list storage, result references, and sorting workspace require O(n) space, including the returned O(n) matrix.

Permutation baseline time is bounded by O(n!·n²), with O(n) live search/used/row-reference storage plus copied input/output. Teaching insertion histories are additional visualization data, not part of the reference workspace.

Exact-state walkthroughs

Reveal normal and boundary traces

Insert shorter people without disturbing taller counts

Input: [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]] · Fresh queue / thrown outcome: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

Step 1 of 21: Sort private person occurrences by descending height, then ascending k.

Original occurrence indices identify teaching cards. The Java result promises fresh values, not original object identity.

Queue reconstruction — qualifying people become insertion positions

Phase: initial.

Private sorted occurrences — height descending, k ascending

  1. Position 0: [7, 0]Original occurrence 0; requires 0 earlier people of height ≥ 7
  2. Position 1: [7, 1]Original occurrence 2; requires 1 earlier people of height ≥ 7
  3. Position 2: [6, 1]Original occurrence 4; requires 1 earlier people of height ≥ 6
  4. Position 3: [5, 0]Original occurrence 3; requires 0 earlier people of height ≥ 5
  5. Position 4: [5, 2]Original occurrence 5; requires 2 earlier people of height ≥ 5
  6. Position 5: [4, 4]Original occurrence 1; requires 4 earlier people of height ≥ 4

Current constructed queue

Empty queue.

Later strictly shorter people may change positions without changing taller predecessor counts. Equal-height duplicates with the same k are contradictory. Occurrence indices explain card ownership; caller row references are never returned.

State after this step
VariableValue
input[[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
phase"initial"
sorted[{"index":0,"height":7,"k":0},{"index":2,"height":7,"k":1},{"index":4,"height":6,"k":1},{"index":3,"height":5,"k":0},{"index":5,"height":5,"k":2},{"index":1,"height":4,"k":4}]
queue[]
See the affected Java block
 1 import java.util.ArrayList;
 2 import java.util.Arrays;
 3 import java.util.Comparator;
 4 import java.util.List;
 5 import java.util.Objects;
 6 
 7 public final class Solution {
 8     private Solution() {}
 9     private static int[][] copy(int[][] people) {
10         Objects.requireNonNull(people, "people");
11         if (people.length > 2_000) throw new IllegalArgumentException("too many people");
12         int[][] sorted = new int[people.length][];
13         for (int i = 0; i < people.length; i++) {
14             Objects.requireNonNull(people[i], "person");
15             if (people[i].length != 2 || people[i][0] < 0 || people[i][1] < 0 || people[i][1] >= people.length) {
16                 throw new IllegalArgumentException("expected [nonnegative height, k in 0..n-1]");
17             }
18             sorted[i] = people[i].clone();
19         }
20         return sorted;
21     }
22     private static boolean valid(int[][] queue) {
23         for (int i = 0; i < queue.length; i++) {
24             int count = 0;
25             for (int j = 0; j < i; j++) if (queue[j][0] >= queue[i][0]) count++;
26             if (count != queue[i][1]) return false;
27         }
28         return true;
29     }
30     public static int[][] reconstructQueue(int[][] people) {
31         int[][] sorted = copy(people);
32         Arrays.sort(sorted, Comparator.<int[]>comparingInt(p -> p[0]).reversed().thenComparingInt(p -> p[1]));
33         List<int[]> queue = new ArrayList<>();
34         for (int[] person : sorted) {
35             if (person[1] > queue.size()) throw new IllegalArgumentException("infeasible constraints");
36             queue.add(person[1], person);
37         }
38         int[][] result = queue.toArray(int[][]::new);
39         if (!valid(result)) throw new IllegalArgumentException("infeasible constraints");
40         return result;
41     }
42     // Enumerate input-occurrence permutations; factorial, tiny inputs only.
43     public static int[][] baseline(int[][] people) {
44         int[][] input = copy(people), result = new int[input.length][];
45         if (!search(input, result, new boolean[input.length], 0)) throw new IllegalArgumentException("infeasible constraints");
46         return result;
47     }
48     private static boolean search(int[][] input, int[][] result, boolean[] used, int at) {
49         if (at == input.length) return valid(result);
50         for (int i = 0; i < input.length; i++) if (!used[i]) {
51             used[i] = true;
52             result[at] = input[i];
53             if (search(input, result, used, at + 1)) return true;
54             used[i] = false;
55         }
56         return false;
57     }
58 }
59

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace
  1. Sort private person occurrences by descending height, then ascending k.

    Original occurrence indices identify teaching cards. The Java result promises fresh values, not original object identity.

    input
    [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
    phase
    "initial"
    sorted
    [{"index":0,"height":7,"k":0},{"index":2,"height":7,"k":1},{"index":4,"height":6,"k":1},{"index":3,"height":5,"k":0},{"index":5,"height":5,"k":2},{"index":1,"height":4,"k":4}]
    queue
    []
  2. Every already inserted person is at least as tall.

    The required qualifying-predecessor count is a literal insertion index among the current people. Equal heights are processed by increasing k.

    input
    [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
    phase
    "candidate"
    sorted
    [{"index":0,"height":7,"k":0},{"index":2,"height":7,"k":1},{"index":4,"height":6,"k":1},{"index":3,"height":5,"k":0},{"index":5,"height":5,"k":2},{"index":1,"height":4,"k":4}]
    queue
    []
    order
    0
    person
    {"index":0,"height":7,"k":0}
  3. Insert the occurrence at its required index.

    Shorter future insertions do not count for taller people. Contradictory equal-height duplicates may still violate an earlier count and are caught by final verification.

    input
    [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
    phase
    "insert"
    sorted
    [{"index":0,"height":7,"k":0},{"index":2,"height":7,"k":1},{"index":4,"height":6,"k":1},{"index":3,"height":5,"k":0},{"index":5,"height":5,"k":2},{"index":1,"height":4,"k":4}]
    queue
    [{"index":0,"height":7,"k":0}]
    order
    0
    person
    {"index":0,"height":7,"k":0}
  4. Every already inserted person is at least as tall.

    The required qualifying-predecessor count is a literal insertion index among the current people. Equal heights are processed by increasing k.

    input
    [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
    phase
    "candidate"
    sorted
    [{"index":0,"height":7,"k":0},{"index":2,"height":7,"k":1},{"index":4,"height":6,"k":1},{"index":3,"height":5,"k":0},{"index":5,"height":5,"k":2},{"index":1,"height":4,"k":4}]
    queue
    [{"index":0,"height":7,"k":0}]
    order
    1
    person
    {"index":2,"height":7,"k":1}
  5. Insert the occurrence at its required index.

    Shorter future insertions do not count for taller people. Contradictory equal-height duplicates may still violate an earlier count and are caught by final verification.

    input
    [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
    phase
    "insert"
    sorted
    [{"index":0,"height":7,"k":0},{"index":2,"height":7,"k":1},{"index":4,"height":6,"k":1},{"index":3,"height":5,"k":0},{"index":5,"height":5,"k":2},{"index":1,"height":4,"k":4}]
    queue
    [{"index":0,"height":7,"k":0},{"index":2,"height":7,"k":1}]
    order
    1
    person
    {"index":2,"height":7,"k":1}
  6. Every already inserted person is at least as tall.

    The required qualifying-predecessor count is a literal insertion index among the current people. Equal heights are processed by increasing k.

    input
    [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
    phase
    "candidate"
    sorted
    [{"index":0,"height":7,"k":0},{"index":2,"height":7,"k":1},{"index":4,"height":6,"k":1},{"index":3,"height":5,"k":0},{"index":5,"height":5,"k":2},{"index":1,"height":4,"k":4}]
    queue
    [{"index":0,"height":7,"k":0},{"index":2,"height":7,"k":1}]
    order
    2
    person
    {"index":4,"height":6,"k":1}
  7. Insert the occurrence at its required index.

    Shorter future insertions do not count for taller people. Contradictory equal-height duplicates may still violate an earlier count and are caught by final verification.

    input
    [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
    phase
    "insert"
    sorted
    [{"index":0,"height":7,"k":0},{"index":2,"height":7,"k":1},{"index":4,"height":6,"k":1},{"index":3,"height":5,"k":0},{"index":5,"height":5,"k":2},{"index":1,"height":4,"k":4}]
    queue
    [{"index":0,"height":7,"k":0},{"index":4,"height":6,"k":1},{"index":2,"height":7,"k":1}]
    order
    2
    person
    {"index":4,"height":6,"k":1}
  8. Every already inserted person is at least as tall.

    The required qualifying-predecessor count is a literal insertion index among the current people. Equal heights are processed by increasing k.

    input
    [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
    phase
    "candidate"
    sorted
    [{"index":0,"height":7,"k":0},{"index":2,"height":7,"k":1},{"index":4,"height":6,"k":1},{"index":3,"height":5,"k":0},{"index":5,"height":5,"k":2},{"index":1,"height":4,"k":4}]
    queue
    [{"index":0,"height":7,"k":0},{"index":4,"height":6,"k":1},{"index":2,"height":7,"k":1}]
    order
    3
    person
    {"index":3,"height":5,"k":0}
  9. Insert the occurrence at its required index.

    Shorter future insertions do not count for taller people. Contradictory equal-height duplicates may still violate an earlier count and are caught by final verification.

    input
    [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
    phase
    "insert"
    sorted
    [{"index":0,"height":7,"k":0},{"index":2,"height":7,"k":1},{"index":4,"height":6,"k":1},{"index":3,"height":5,"k":0},{"index":5,"height":5,"k":2},{"index":1,"height":4,"k":4}]
    queue
    [{"index":3,"height":5,"k":0},{"index":0,"height":7,"k":0},{"index":4,"height":6,"k":1},{"index":2,"height":7,"k":1}]
    order
    3
    person
    {"index":3,"height":5,"k":0}
  10. Every already inserted person is at least as tall.

    The required qualifying-predecessor count is a literal insertion index among the current people. Equal heights are processed by increasing k.

    input
    [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
    phase
    "candidate"
    sorted
    [{"index":0,"height":7,"k":0},{"index":2,"height":7,"k":1},{"index":4,"height":6,"k":1},{"index":3,"height":5,"k":0},{"index":5,"height":5,"k":2},{"index":1,"height":4,"k":4}]
    queue
    [{"index":3,"height":5,"k":0},{"index":0,"height":7,"k":0},{"index":4,"height":6,"k":1},{"index":2,"height":7,"k":1}]
    order
    4
    person
    {"index":5,"height":5,"k":2}
  11. Insert the occurrence at its required index.

    Shorter future insertions do not count for taller people. Contradictory equal-height duplicates may still violate an earlier count and are caught by final verification.

    input
    [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
    phase
    "insert"
    sorted
    [{"index":0,"height":7,"k":0},{"index":2,"height":7,"k":1},{"index":4,"height":6,"k":1},{"index":3,"height":5,"k":0},{"index":5,"height":5,"k":2},{"index":1,"height":4,"k":4}]
    queue
    [{"index":3,"height":5,"k":0},{"index":0,"height":7,"k":0},{"index":5,"height":5,"k":2},{"index":4,"height":6,"k":1},{"index":2,"height":7,"k":1}]
    order
    4
    person
    {"index":5,"height":5,"k":2}
  12. Every already inserted person is at least as tall.

    The required qualifying-predecessor count is a literal insertion index among the current people. Equal heights are processed by increasing k.

    input
    [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
    phase
    "candidate"
    sorted
    [{"index":0,"height":7,"k":0},{"index":2,"height":7,"k":1},{"index":4,"height":6,"k":1},{"index":3,"height":5,"k":0},{"index":5,"height":5,"k":2},{"index":1,"height":4,"k":4}]
    queue
    [{"index":3,"height":5,"k":0},{"index":0,"height":7,"k":0},{"index":5,"height":5,"k":2},{"index":4,"height":6,"k":1},{"index":2,"height":7,"k":1}]
    order
    5
    person
    {"index":1,"height":4,"k":4}
  13. Insert the occurrence at its required index.

    Shorter future insertions do not count for taller people. Contradictory equal-height duplicates may still violate an earlier count and are caught by final verification.

    input
    [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
    phase
    "insert"
    sorted
    [{"index":0,"height":7,"k":0},{"index":2,"height":7,"k":1},{"index":4,"height":6,"k":1},{"index":3,"height":5,"k":0},{"index":5,"height":5,"k":2},{"index":1,"height":4,"k":4}]
    queue
    [{"index":3,"height":5,"k":0},{"index":0,"height":7,"k":0},{"index":5,"height":5,"k":2},{"index":4,"height":6,"k":1},{"index":1,"height":4,"k":4},{"index":2,"height":7,"k":1}]
    order
    5
    person
    {"index":1,"height":4,"k":4}
  14. Count actual qualifying predecessors in the completed queue.

    Use greater OR equal height. Final verification is part of the arbitrary-input contract, not an omitted feasibility promise.

    input
    [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
    phase
    "verify"
    sorted
    [{"index":0,"height":7,"k":0},{"index":2,"height":7,"k":1},{"index":4,"height":6,"k":1},{"index":3,"height":5,"k":0},{"index":5,"height":5,"k":2},{"index":1,"height":4,"k":4}]
    queue
    [{"index":3,"height":5,"k":0},{"index":0,"height":7,"k":0},{"index":5,"height":5,"k":2},{"index":4,"height":6,"k":1},{"index":1,"height":4,"k":4},{"index":2,"height":7,"k":1}]
    position
    0
    count
    0
    required
    0
  15. Count actual qualifying predecessors in the completed queue.

    Use greater OR equal height. Final verification is part of the arbitrary-input contract, not an omitted feasibility promise.

    input
    [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
    phase
    "verify"
    sorted
    [{"index":0,"height":7,"k":0},{"index":2,"height":7,"k":1},{"index":4,"height":6,"k":1},{"index":3,"height":5,"k":0},{"index":5,"height":5,"k":2},{"index":1,"height":4,"k":4}]
    queue
    [{"index":3,"height":5,"k":0},{"index":0,"height":7,"k":0},{"index":5,"height":5,"k":2},{"index":4,"height":6,"k":1},{"index":1,"height":4,"k":4},{"index":2,"height":7,"k":1}]
    position
    1
    count
    0
    required
    0
  16. Count actual qualifying predecessors in the completed queue.

    Use greater OR equal height. Final verification is part of the arbitrary-input contract, not an omitted feasibility promise.

    input
    [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
    phase
    "verify"
    sorted
    [{"index":0,"height":7,"k":0},{"index":2,"height":7,"k":1},{"index":4,"height":6,"k":1},{"index":3,"height":5,"k":0},{"index":5,"height":5,"k":2},{"index":1,"height":4,"k":4}]
    queue
    [{"index":3,"height":5,"k":0},{"index":0,"height":7,"k":0},{"index":5,"height":5,"k":2},{"index":4,"height":6,"k":1},{"index":1,"height":4,"k":4},{"index":2,"height":7,"k":1}]
    position
    2
    count
    2
    required
    2
  17. Count actual qualifying predecessors in the completed queue.

    Use greater OR equal height. Final verification is part of the arbitrary-input contract, not an omitted feasibility promise.

    input
    [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
    phase
    "verify"
    sorted
    [{"index":0,"height":7,"k":0},{"index":2,"height":7,"k":1},{"index":4,"height":6,"k":1},{"index":3,"height":5,"k":0},{"index":5,"height":5,"k":2},{"index":1,"height":4,"k":4}]
    queue
    [{"index":3,"height":5,"k":0},{"index":0,"height":7,"k":0},{"index":5,"height":5,"k":2},{"index":4,"height":6,"k":1},{"index":1,"height":4,"k":4},{"index":2,"height":7,"k":1}]
    position
    3
    count
    1
    required
    1
  18. Count actual qualifying predecessors in the completed queue.

    Use greater OR equal height. Final verification is part of the arbitrary-input contract, not an omitted feasibility promise.

    input
    [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
    phase
    "verify"
    sorted
    [{"index":0,"height":7,"k":0},{"index":2,"height":7,"k":1},{"index":4,"height":6,"k":1},{"index":3,"height":5,"k":0},{"index":5,"height":5,"k":2},{"index":1,"height":4,"k":4}]
    queue
    [{"index":3,"height":5,"k":0},{"index":0,"height":7,"k":0},{"index":5,"height":5,"k":2},{"index":4,"height":6,"k":1},{"index":1,"height":4,"k":4},{"index":2,"height":7,"k":1}]
    position
    4
    count
    4
    required
    4
  19. Count actual qualifying predecessors in the completed queue.

    Use greater OR equal height. Final verification is part of the arbitrary-input contract, not an omitted feasibility promise.

    input
    [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
    phase
    "verify"
    sorted
    [{"index":0,"height":7,"k":0},{"index":2,"height":7,"k":1},{"index":4,"height":6,"k":1},{"index":3,"height":5,"k":0},{"index":5,"height":5,"k":2},{"index":1,"height":4,"k":4}]
    queue
    [{"index":3,"height":5,"k":0},{"index":0,"height":7,"k":0},{"index":5,"height":5,"k":2},{"index":4,"height":6,"k":1},{"index":1,"height":4,"k":4},{"index":2,"height":7,"k":1}]
    position
    5
    count
    1
    required
    1
  20. Return a fresh outer array and fresh person rows.

    Sorting and insertion use only copied rows. The occurrence multiset is preserved and caller row identities remain unchanged.

    input
    [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
    phase
    "complete"
    sorted
    [{"index":0,"height":7,"k":0},{"index":2,"height":7,"k":1},{"index":4,"height":6,"k":1},{"index":3,"height":5,"k":0},{"index":5,"height":5,"k":2},{"index":1,"height":4,"k":4}]
    queue
    [{"index":3,"height":5,"k":0},{"index":0,"height":7,"k":0},{"index":5,"height":5,"k":2},{"index":4,"height":6,"k":1},{"index":1,"height":4,"k":4},{"index":2,"height":7,"k":1}]
    invalid
    false
  21. Return the documented outcome.

    The result follows the stated empty, failure, and mutation contract. Histories and original occurrence cards are teaching data rather than reference workspace.

    result
    [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

Equal heights need increasing counts

Input: [[5,1],[5,0]] · Fresh queue / thrown outcome: [[5,0],[5,1]]

Step 1 of 9: Sort private person occurrences by descending height, then ascending k.

Original occurrence indices identify teaching cards. The Java result promises fresh values, not original object identity.

Queue reconstruction — qualifying people become insertion positions

Phase: initial.

Private sorted occurrences — height descending, k ascending

  1. Position 0: [5, 0]Original occurrence 1; requires 0 earlier people of height ≥ 5
  2. Position 1: [5, 1]Original occurrence 0; requires 1 earlier people of height ≥ 5

Current constructed queue

Empty queue.

Later strictly shorter people may change positions without changing taller predecessor counts. Equal-height duplicates with the same k are contradictory. Occurrence indices explain card ownership; caller row references are never returned.

State after this step
VariableValue
input[[5,1],[5,0]]
phase"initial"
sorted[{"index":1,"height":5,"k":0},{"index":0,"height":5,"k":1}]
queue[]
See the affected Java block
 1 import java.util.ArrayList;
 2 import java.util.Arrays;
 3 import java.util.Comparator;
 4 import java.util.List;
 5 import java.util.Objects;
 6 
 7 public final class Solution {
 8     private Solution() {}
 9     private static int[][] copy(int[][] people) {
10         Objects.requireNonNull(people, "people");
11         if (people.length > 2_000) throw new IllegalArgumentException("too many people");
12         int[][] sorted = new int[people.length][];
13         for (int i = 0; i < people.length; i++) {
14             Objects.requireNonNull(people[i], "person");
15             if (people[i].length != 2 || people[i][0] < 0 || people[i][1] < 0 || people[i][1] >= people.length) {
16                 throw new IllegalArgumentException("expected [nonnegative height, k in 0..n-1]");
17             }
18             sorted[i] = people[i].clone();
19         }
20         return sorted;
21     }
22     private static boolean valid(int[][] queue) {
23         for (int i = 0; i < queue.length; i++) {
24             int count = 0;
25             for (int j = 0; j < i; j++) if (queue[j][0] >= queue[i][0]) count++;
26             if (count != queue[i][1]) return false;
27         }
28         return true;
29     }
30     public static int[][] reconstructQueue(int[][] people) {
31         int[][] sorted = copy(people);
32         Arrays.sort(sorted, Comparator.<int[]>comparingInt(p -> p[0]).reversed().thenComparingInt(p -> p[1]));
33         List<int[]> queue = new ArrayList<>();
34         for (int[] person : sorted) {
35             if (person[1] > queue.size()) throw new IllegalArgumentException("infeasible constraints");
36             queue.add(person[1], person);
37         }
38         int[][] result = queue.toArray(int[][]::new);
39         if (!valid(result)) throw new IllegalArgumentException("infeasible constraints");
40         return result;
41     }
42     // Enumerate input-occurrence permutations; factorial, tiny inputs only.
43     public static int[][] baseline(int[][] people) {
44         int[][] input = copy(people), result = new int[input.length][];
45         if (!search(input, result, new boolean[input.length], 0)) throw new IllegalArgumentException("infeasible constraints");
46         return result;
47     }
48     private static boolean search(int[][] input, int[][] result, boolean[] used, int at) {
49         if (at == input.length) return valid(result);
50         for (int i = 0; i < input.length; i++) if (!used[i]) {
51             used[i] = true;
52             result[at] = input[i];
53             if (search(input, result, used, at + 1)) return true;
54             used[i] = false;
55         }
56         return false;
57     }
58 }
59

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace
  1. Sort private person occurrences by descending height, then ascending k.

    Original occurrence indices identify teaching cards. The Java result promises fresh values, not original object identity.

    input
    [[5,1],[5,0]]
    phase
    "initial"
    sorted
    [{"index":1,"height":5,"k":0},{"index":0,"height":5,"k":1}]
    queue
    []
  2. Every already inserted person is at least as tall.

    The required qualifying-predecessor count is a literal insertion index among the current people. Equal heights are processed by increasing k.

    input
    [[5,1],[5,0]]
    phase
    "candidate"
    sorted
    [{"index":1,"height":5,"k":0},{"index":0,"height":5,"k":1}]
    queue
    []
    order
    0
    person
    {"index":1,"height":5,"k":0}
  3. Insert the occurrence at its required index.

    Shorter future insertions do not count for taller people. Contradictory equal-height duplicates may still violate an earlier count and are caught by final verification.

    input
    [[5,1],[5,0]]
    phase
    "insert"
    sorted
    [{"index":1,"height":5,"k":0},{"index":0,"height":5,"k":1}]
    queue
    [{"index":1,"height":5,"k":0}]
    order
    0
    person
    {"index":1,"height":5,"k":0}
  4. Every already inserted person is at least as tall.

    The required qualifying-predecessor count is a literal insertion index among the current people. Equal heights are processed by increasing k.

    input
    [[5,1],[5,0]]
    phase
    "candidate"
    sorted
    [{"index":1,"height":5,"k":0},{"index":0,"height":5,"k":1}]
    queue
    [{"index":1,"height":5,"k":0}]
    order
    1
    person
    {"index":0,"height":5,"k":1}
  5. Insert the occurrence at its required index.

    Shorter future insertions do not count for taller people. Contradictory equal-height duplicates may still violate an earlier count and are caught by final verification.

    input
    [[5,1],[5,0]]
    phase
    "insert"
    sorted
    [{"index":1,"height":5,"k":0},{"index":0,"height":5,"k":1}]
    queue
    [{"index":1,"height":5,"k":0},{"index":0,"height":5,"k":1}]
    order
    1
    person
    {"index":0,"height":5,"k":1}
  6. Count actual qualifying predecessors in the completed queue.

    Use greater OR equal height. Final verification is part of the arbitrary-input contract, not an omitted feasibility promise.

    input
    [[5,1],[5,0]]
    phase
    "verify"
    sorted
    [{"index":1,"height":5,"k":0},{"index":0,"height":5,"k":1}]
    queue
    [{"index":1,"height":5,"k":0},{"index":0,"height":5,"k":1}]
    position
    0
    count
    0
    required
    0
  7. Count actual qualifying predecessors in the completed queue.

    Use greater OR equal height. Final verification is part of the arbitrary-input contract, not an omitted feasibility promise.

    input
    [[5,1],[5,0]]
    phase
    "verify"
    sorted
    [{"index":1,"height":5,"k":0},{"index":0,"height":5,"k":1}]
    queue
    [{"index":1,"height":5,"k":0},{"index":0,"height":5,"k":1}]
    position
    1
    count
    1
    required
    1
  8. Return a fresh outer array and fresh person rows.

    Sorting and insertion use only copied rows. The occurrence multiset is preserved and caller row identities remain unchanged.

    input
    [[5,1],[5,0]]
    phase
    "complete"
    sorted
    [{"index":1,"height":5,"k":0},{"index":0,"height":5,"k":1}]
    queue
    [{"index":1,"height":5,"k":0},{"index":0,"height":5,"k":1}]
    invalid
    false
  9. Return the documented outcome.

    The result follows the stated empty, failure, and mutation contract. Histories and original occurrence cards are teaching data rather than reference workspace.

    result
    [[5,0],[5,1]]

Repeated constraints are impossible

Input: [[5,0],[5,0]] · Fresh queue / thrown outcome: "IllegalArgumentException"

Step 1 of 9: Sort private person occurrences by descending height, then ascending k.

Original occurrence indices identify teaching cards. The Java result promises fresh values, not original object identity.

Queue reconstruction — qualifying people become insertion positions

Phase: initial.

Private sorted occurrences — height descending, k ascending

  1. Position 0: [5, 0]Original occurrence 0; requires 0 earlier people of height ≥ 5
  2. Position 1: [5, 0]Original occurrence 1; requires 0 earlier people of height ≥ 5

Current constructed queue

Empty queue.

Later strictly shorter people may change positions without changing taller predecessor counts. Equal-height duplicates with the same k are contradictory. Occurrence indices explain card ownership; caller row references are never returned.

State after this step
VariableValue
input[[5,0],[5,0]]
phase"initial"
sorted[{"index":0,"height":5,"k":0},{"index":1,"height":5,"k":0}]
queue[]
See the affected Java block
 1 import java.util.ArrayList;
 2 import java.util.Arrays;
 3 import java.util.Comparator;
 4 import java.util.List;
 5 import java.util.Objects;
 6 
 7 public final class Solution {
 8     private Solution() {}
 9     private static int[][] copy(int[][] people) {
10         Objects.requireNonNull(people, "people");
11         if (people.length > 2_000) throw new IllegalArgumentException("too many people");
12         int[][] sorted = new int[people.length][];
13         for (int i = 0; i < people.length; i++) {
14             Objects.requireNonNull(people[i], "person");
15             if (people[i].length != 2 || people[i][0] < 0 || people[i][1] < 0 || people[i][1] >= people.length) {
16                 throw new IllegalArgumentException("expected [nonnegative height, k in 0..n-1]");
17             }
18             sorted[i] = people[i].clone();
19         }
20         return sorted;
21     }
22     private static boolean valid(int[][] queue) {
23         for (int i = 0; i < queue.length; i++) {
24             int count = 0;
25             for (int j = 0; j < i; j++) if (queue[j][0] >= queue[i][0]) count++;
26             if (count != queue[i][1]) return false;
27         }
28         return true;
29     }
30     public static int[][] reconstructQueue(int[][] people) {
31         int[][] sorted = copy(people);
32         Arrays.sort(sorted, Comparator.<int[]>comparingInt(p -> p[0]).reversed().thenComparingInt(p -> p[1]));
33         List<int[]> queue = new ArrayList<>();
34         for (int[] person : sorted) {
35             if (person[1] > queue.size()) throw new IllegalArgumentException("infeasible constraints");
36             queue.add(person[1], person);
37         }
38         int[][] result = queue.toArray(int[][]::new);
39         if (!valid(result)) throw new IllegalArgumentException("infeasible constraints");
40         return result;
41     }
42     // Enumerate input-occurrence permutations; factorial, tiny inputs only.
43     public static int[][] baseline(int[][] people) {
44         int[][] input = copy(people), result = new int[input.length][];
45         if (!search(input, result, new boolean[input.length], 0)) throw new IllegalArgumentException("infeasible constraints");
46         return result;
47     }
48     private static boolean search(int[][] input, int[][] result, boolean[] used, int at) {
49         if (at == input.length) return valid(result);
50         for (int i = 0; i < input.length; i++) if (!used[i]) {
51             used[i] = true;
52             result[at] = input[i];
53             if (search(input, result, used, at + 1)) return true;
54             used[i] = false;
55         }
56         return false;
57     }
58 }
59

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace
  1. Sort private person occurrences by descending height, then ascending k.

    Original occurrence indices identify teaching cards. The Java result promises fresh values, not original object identity.

    input
    [[5,0],[5,0]]
    phase
    "initial"
    sorted
    [{"index":0,"height":5,"k":0},{"index":1,"height":5,"k":0}]
    queue
    []
  2. Every already inserted person is at least as tall.

    The required qualifying-predecessor count is a literal insertion index among the current people. Equal heights are processed by increasing k.

    input
    [[5,0],[5,0]]
    phase
    "candidate"
    sorted
    [{"index":0,"height":5,"k":0},{"index":1,"height":5,"k":0}]
    queue
    []
    order
    0
    person
    {"index":0,"height":5,"k":0}
  3. Insert the occurrence at its required index.

    Shorter future insertions do not count for taller people. Contradictory equal-height duplicates may still violate an earlier count and are caught by final verification.

    input
    [[5,0],[5,0]]
    phase
    "insert"
    sorted
    [{"index":0,"height":5,"k":0},{"index":1,"height":5,"k":0}]
    queue
    [{"index":0,"height":5,"k":0}]
    order
    0
    person
    {"index":0,"height":5,"k":0}
  4. Every already inserted person is at least as tall.

    The required qualifying-predecessor count is a literal insertion index among the current people. Equal heights are processed by increasing k.

    input
    [[5,0],[5,0]]
    phase
    "candidate"
    sorted
    [{"index":0,"height":5,"k":0},{"index":1,"height":5,"k":0}]
    queue
    [{"index":0,"height":5,"k":0}]
    order
    1
    person
    {"index":1,"height":5,"k":0}
  5. Insert the occurrence at its required index.

    Shorter future insertions do not count for taller people. Contradictory equal-height duplicates may still violate an earlier count and are caught by final verification.

    input
    [[5,0],[5,0]]
    phase
    "insert"
    sorted
    [{"index":0,"height":5,"k":0},{"index":1,"height":5,"k":0}]
    queue
    [{"index":1,"height":5,"k":0},{"index":0,"height":5,"k":0}]
    order
    1
    person
    {"index":1,"height":5,"k":0}
  6. Count actual qualifying predecessors in the completed queue.

    Use greater OR equal height. Final verification is part of the arbitrary-input contract, not an omitted feasibility promise.

    input
    [[5,0],[5,0]]
    phase
    "verify"
    sorted
    [{"index":0,"height":5,"k":0},{"index":1,"height":5,"k":0}]
    queue
    [{"index":1,"height":5,"k":0},{"index":0,"height":5,"k":0}]
    position
    0
    count
    0
    required
    0
  7. Count actual qualifying predecessors in the completed queue.

    Use greater OR equal height. Final verification is part of the arbitrary-input contract, not an omitted feasibility promise.

    input
    [[5,0],[5,0]]
    phase
    "verify"
    sorted
    [{"index":0,"height":5,"k":0},{"index":1,"height":5,"k":0}]
    queue
    [{"index":1,"height":5,"k":0},{"index":0,"height":5,"k":0}]
    position
    1
    count
    1
    required
    0
  8. Reject the contradictory constraints.

    Sorting and insertion use only copied rows. The occurrence multiset is preserved and caller row identities remain unchanged.

    input
    [[5,0],[5,0]]
    phase
    "complete"
    sorted
    [{"index":0,"height":5,"k":0},{"index":1,"height":5,"k":0}]
    queue
    [{"index":1,"height":5,"k":0},{"index":0,"height":5,"k":0}]
    invalid
    true
  9. Return the documented outcome.

    The result follows the stated empty, failure, and mutation contract. Histories and original occurrence cards are teaching data rather than reference workspace.

    result
    "IllegalArgumentException"

Insertion requires enough qualifying people

Input: [[5,1],[4,0]] · Fresh queue / thrown outcome: "IllegalArgumentException"

Step 1 of 5: Sort private person occurrences by descending height, then ascending k.

Original occurrence indices identify teaching cards. The Java result promises fresh values, not original object identity.

Queue reconstruction — qualifying people become insertion positions

Phase: initial.

Private sorted occurrences — height descending, k ascending

  1. Position 0: [5, 1]Original occurrence 0; requires 1 earlier people of height ≥ 5
  2. Position 1: [4, 0]Original occurrence 1; requires 0 earlier people of height ≥ 4

Current constructed queue

Empty queue.

Later strictly shorter people may change positions without changing taller predecessor counts. Equal-height duplicates with the same k are contradictory. Occurrence indices explain card ownership; caller row references are never returned.

State after this step
VariableValue
input[[5,1],[4,0]]
phase"initial"
sorted[{"index":0,"height":5,"k":1},{"index":1,"height":4,"k":0}]
queue[]
See the affected Java block
 1 import java.util.ArrayList;
 2 import java.util.Arrays;
 3 import java.util.Comparator;
 4 import java.util.List;
 5 import java.util.Objects;
 6 
 7 public final class Solution {
 8     private Solution() {}
 9     private static int[][] copy(int[][] people) {
10         Objects.requireNonNull(people, "people");
11         if (people.length > 2_000) throw new IllegalArgumentException("too many people");
12         int[][] sorted = new int[people.length][];
13         for (int i = 0; i < people.length; i++) {
14             Objects.requireNonNull(people[i], "person");
15             if (people[i].length != 2 || people[i][0] < 0 || people[i][1] < 0 || people[i][1] >= people.length) {
16                 throw new IllegalArgumentException("expected [nonnegative height, k in 0..n-1]");
17             }
18             sorted[i] = people[i].clone();
19         }
20         return sorted;
21     }
22     private static boolean valid(int[][] queue) {
23         for (int i = 0; i < queue.length; i++) {
24             int count = 0;
25             for (int j = 0; j < i; j++) if (queue[j][0] >= queue[i][0]) count++;
26             if (count != queue[i][1]) return false;
27         }
28         return true;
29     }
30     public static int[][] reconstructQueue(int[][] people) {
31         int[][] sorted = copy(people);
32         Arrays.sort(sorted, Comparator.<int[]>comparingInt(p -> p[0]).reversed().thenComparingInt(p -> p[1]));
33         List<int[]> queue = new ArrayList<>();
34         for (int[] person : sorted) {
35             if (person[1] > queue.size()) throw new IllegalArgumentException("infeasible constraints");
36             queue.add(person[1], person);
37         }
38         int[][] result = queue.toArray(int[][]::new);
39         if (!valid(result)) throw new IllegalArgumentException("infeasible constraints");
40         return result;
41     }
42     // Enumerate input-occurrence permutations; factorial, tiny inputs only.
43     public static int[][] baseline(int[][] people) {
44         int[][] input = copy(people), result = new int[input.length][];
45         if (!search(input, result, new boolean[input.length], 0)) throw new IllegalArgumentException("infeasible constraints");
46         return result;
47     }
48     private static boolean search(int[][] input, int[][] result, boolean[] used, int at) {
49         if (at == input.length) return valid(result);
50         for (int i = 0; i < input.length; i++) if (!used[i]) {
51             used[i] = true;
52             result[at] = input[i];
53             if (search(input, result, used, at + 1)) return true;
54             used[i] = false;
55         }
56         return false;
57     }
58 }
59

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace
  1. Sort private person occurrences by descending height, then ascending k.

    Original occurrence indices identify teaching cards. The Java result promises fresh values, not original object identity.

    input
    [[5,1],[4,0]]
    phase
    "initial"
    sorted
    [{"index":0,"height":5,"k":1},{"index":1,"height":4,"k":0}]
    queue
    []
  2. Every already inserted person is at least as tall.

    The required qualifying-predecessor count is a literal insertion index among the current people. Equal heights are processed by increasing k.

    input
    [[5,1],[4,0]]
    phase
    "candidate"
    sorted
    [{"index":0,"height":5,"k":1},{"index":1,"height":4,"k":0}]
    queue
    []
    order
    0
    person
    {"index":0,"height":5,"k":1}
  3. There are too few qualifying people for this k.

    A feasible input cannot demand more prior qualifying people than have been processed. No insertion is attempted.

    input
    [[5,1],[4,0]]
    phase
    "reject-index"
    sorted
    [{"index":0,"height":5,"k":1},{"index":1,"height":4,"k":0}]
    queue
    []
    order
    0
    person
    {"index":0,"height":5,"k":1}
  4. Reject the contradictory constraints.

    Sorting and insertion use only copied rows. The occurrence multiset is preserved and caller row identities remain unchanged.

    input
    [[5,1],[4,0]]
    phase
    "complete"
    sorted
    [{"index":0,"height":5,"k":1},{"index":1,"height":4,"k":0}]
    queue
    []
    invalid
    true
  5. Return the documented outcome.

    The result follows the stated empty, failure, and mutation contract. Histories and original occurrence cards are teaching data rather than reference workspace.

    result
    "IllegalArgumentException"

Empty queue

Input: [] · Fresh queue / thrown outcome: []

Step 1 of 3: Sort private person occurrences by descending height, then ascending k.

Original occurrence indices identify teaching cards. The Java result promises fresh values, not original object identity.

Queue reconstruction — qualifying people become insertion positions

Phase: initial.

Private sorted occurrences — height descending, k ascending

Empty queue.

Current constructed queue

Empty queue.

Later strictly shorter people may change positions without changing taller predecessor counts. Equal-height duplicates with the same k are contradictory. Occurrence indices explain card ownership; caller row references are never returned.

State after this step
VariableValue
input[]
phase"initial"
sorted[]
queue[]
See the affected Java block
 1 import java.util.ArrayList;
 2 import java.util.Arrays;
 3 import java.util.Comparator;
 4 import java.util.List;
 5 import java.util.Objects;
 6 
 7 public final class Solution {
 8     private Solution() {}
 9     private static int[][] copy(int[][] people) {
10         Objects.requireNonNull(people, "people");
11         if (people.length > 2_000) throw new IllegalArgumentException("too many people");
12         int[][] sorted = new int[people.length][];
13         for (int i = 0; i < people.length; i++) {
14             Objects.requireNonNull(people[i], "person");
15             if (people[i].length != 2 || people[i][0] < 0 || people[i][1] < 0 || people[i][1] >= people.length) {
16                 throw new IllegalArgumentException("expected [nonnegative height, k in 0..n-1]");
17             }
18             sorted[i] = people[i].clone();
19         }
20         return sorted;
21     }
22     private static boolean valid(int[][] queue) {
23         for (int i = 0; i < queue.length; i++) {
24             int count = 0;
25             for (int j = 0; j < i; j++) if (queue[j][0] >= queue[i][0]) count++;
26             if (count != queue[i][1]) return false;
27         }
28         return true;
29     }
30     public static int[][] reconstructQueue(int[][] people) {
31         int[][] sorted = copy(people);
32         Arrays.sort(sorted, Comparator.<int[]>comparingInt(p -> p[0]).reversed().thenComparingInt(p -> p[1]));
33         List<int[]> queue = new ArrayList<>();
34         for (int[] person : sorted) {
35             if (person[1] > queue.size()) throw new IllegalArgumentException("infeasible constraints");
36             queue.add(person[1], person);
37         }
38         int[][] result = queue.toArray(int[][]::new);
39         if (!valid(result)) throw new IllegalArgumentException("infeasible constraints");
40         return result;
41     }
42     // Enumerate input-occurrence permutations; factorial, tiny inputs only.
43     public static int[][] baseline(int[][] people) {
44         int[][] input = copy(people), result = new int[input.length][];
45         if (!search(input, result, new boolean[input.length], 0)) throw new IllegalArgumentException("infeasible constraints");
46         return result;
47     }
48     private static boolean search(int[][] input, int[][] result, boolean[] used, int at) {
49         if (at == input.length) return valid(result);
50         for (int i = 0; i < input.length; i++) if (!used[i]) {
51             used[i] = true;
52             result[at] = input[i];
53             if (search(input, result, used, at + 1)) return true;
54             used[i] = false;
55         }
56         return false;
57     }
58 }
59

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace
  1. Sort private person occurrences by descending height, then ascending k.

    Original occurrence indices identify teaching cards. The Java result promises fresh values, not original object identity.

    input
    []
    phase
    "initial"
    sorted
    []
    queue
    []
  2. Return a fresh outer array and fresh person rows.

    Sorting and insertion use only copied rows. The occurrence multiset is preserved and caller row identities remain unchanged.

    input
    []
    phase
    "complete"
    sorted
    []
    queue
    []
    invalid
    false
  3. Return the documented outcome.

    The result follows the stated empty, failure, and mutation contract. Histories and original occurrence cards are teaching data rather than reference workspace.

    result
    []

Test the contract

  1. Input: people=[]
    Output: []

    Fresh empty result.

  2. Input: people=[[5,0],[5,1]]
    Output: [[5,0],[5,1]]

    Equal-height predecessors count.

  3. Input: people=[[0,1],[2147483647,0]]
    Output: [[2147483647,0],[0,1]]

    Full-width heights and >= counting.

  4. Input: people=[[1,1]]
    Output: IllegalArgumentException

    k is outside the singleton range.

  5. Input: people=[[5,1],[4,0]]
    Output: IllegalArgumentException

    The tall person cannot have a qualifying predecessor.

  6. Input: people=[[5,0],[5,0]]
    Output: IllegalArgumentException

    Final validation catches contradictory duplicates.

Common mistakes and counterexamples

Sort short people first and insert directly at k

Counterexample: A later taller insertion changes the number of qualifying predecessors of already placed short people.

Process heights descending so later shorter insertions are harmless.

Sort equal-height k values descending

Counterexample: [[5,0],[5,1]] cannot start by inserting k=1 into an empty queue.

Sort ties by increasing k.

Assume range-valid constraints are feasible

Counterexample: [[5,0],[5,0]] passes basic ranges but no queue satisfies both.

Check insertion capacity and verify the final predecessor counts.

Return input rows or count only strictly taller people

Counterexample: Mutating an aliased output would alter caller data; equal-height predecessors count.

Deep-copy rows and use >= in the final count.

Follow-ups

Optimize for a much larger queue.

An alternate ascending-height placement can choose the (k+1)-th remaining empty slot using an order-statistics structure such as a Fenwick tree. Equal-height ordering and infeasibility detection must be derived for that representation; replacing ArrayList with LinkedList alone leaves O(n²) traversal.

Return original person identities.

Attach an original index to each private row and return an index permutation or person records. Define deterministic ties and explain how infeasible duplicate equal-height k values are reported. Values-only row cloning does not preserve identity information.

Trust an explicit feasibility guarantee.

With a proven feasible-input promise, the final O(n²) verification can be omitted, though ArrayList insertion remains quadratic. The lesson keeps verification because its API explicitly accepts arbitrary range-valid constraints and promises to reject impossible inputs.

Related foundations

Keep practicing

Return to the lesson

AceYourInterviews · 2026-10-18 · Original teaching content and implementations authored for AceYourInterviews. Familiar interview problem names describe standard algorithmic tasks; no company-frequency or platform-difficulty claims are made.