Loading…

easyArraysSometimes asked

Dynamic Array

Q: How do you solve Dynamic Array using the Baseline — Single Flat Log, Reconstruct on Read approach?

When to use it: Show it as the tempting 'just store everything' idea, then explain why reconstructing a sequence per read is quadratic. Store every append as a `(idx, value)` pair in one global list. To serve a type-2 query, walk that list, collect the values whose `idx` matches, then index into the collected list with `y % size`. **Why someone reaches for this.** It feels simpler to have one container than to manage `n` separate ones, and it sidesteps thinking about how to size the per-sequence lists up front. **Why it's quadratic.** A type-2 query has to *reconstruct* the target sequence by filtering the whole log every time — there's no direct handle on 'sequence idx'. With up to `q` appends and `q` reads, that's `O(q)` work per read and `O(q²)` overall. For `q = 10⁵` that's ten billion operations — far too slow. **The fix.** The sequences are independent and addressed by index, so give each its own list. Then 'append to sequence idx' and 'read position j of sequence idx' are both direct O(1) operations, no scanning. Time complexity: O(q²). Space complexity: O(q).

Q: How do you solve Dynamic Array using the Array of Lists — Direct Simulation (Optimal) approach?

When to use it: The intended answer: n separate growable lists, O(1) append and read, O(q) total. Hold `n` independent growable lists in an array and a single `lastAnswer` initialized to 0. Process queries one by one, deriving the target index from `lastAnswer` each time. **Why the index formula is the crux.** Every query computes `idx = (x ^ lastAnswer) % n`. The XOR couples each query to the *result of the previous type-2 query*, so you can't precompute indices or reorder queries — you must step through them in order, carrying state. Dropping the XOR (using `x % n`) targets the wrong sequence and produces wrong output that still 'looks plausible', which is why it's such a common silent bug. **Why an array of lists.** The sequences are addressed by a small integer `idx in [0, n)`, so an array gives O(1) access to the right list. Appending to a growable list (`ArrayList` / Python `list`) is amortized O(1), and reading position `y % size` is O(1). No scanning, no reconstruction — exactly the cost you'd hope for. **Why `y % size` for reads.** The read index `y` can exceed the current length of the chosen sequence, so it's wrapped with `% size`. Since the problem guarantees the target sequence is non-empty on a type-2 query, the modulo is always well-defined (no division by zero). **Why only type-2 emits output.** Type-1 mutates state silently; type-2 both updates `lastAnswer` (affecting all future indices) and appends to the answer list. Keeping that distinction straight is the last piece of faithfully reproducing the spec. Time complexity: O(q). Space complexity: O(n + total appends).

Arrays & Hashing · 46 of 83 · 6 min

Declare n empty sequences and a variable lastAnswer = 0. Process q queries; each query has a type and two integers x and y.

For every query, compute idx = (x XOR lastAnswer) % n.

Type 1 1 x y: append integer y to the sequence at index idx.
Type 2 2 x y: assign lastAnswer = seq[idx][y % size(seq[idx])] and record lastAnswer.

Return the list of all values recorded by type-2 queries, in order.

In plain English

You maintain n growing lists and a single carried value lastAnswer. Each query first derives which list it touches via (x XOR lastAnswer) % n. Type-1 appends; type-2 reads a wrapped position, updates lastAnswer, and emits it. The output is exactly the sequence of type-2 reads.

Examples

Example 1

Input: n = 2, queries = [[1,0,5],[1,1,7],[1,0,3],[2,1,0],[2,1,1]]
Output: [7, 3]
Note: Appends build seq0=[5,3], seq1=[7]. Query [2,1,0]: idx=(1^0)%2=1 → seq1[0]=7, lastAnswer=7. Query [2,1,1]: idx=(1^7)%2=0 → seq0[1%2=1]=3.

Example 2

Input: n = 1, queries = [[1,0,100],[2,5,0]]
Output: [100]
Note: Only sequence 0 exists. Append 100, then idx=(5^0)%1=0, read seq0[0%1=0]=100.

Constraints

1 ≤ n, q ≤ 10⁵
0 ≤ x, y ≤ 10⁹
Each type-2 query targets a sequence with at least one element
lastAnswer starts at 0

Clarifying questions4First question: What is lastAnswer before the first query?Explore questions

Q1.What is lastAnswer before the first query?
0. It seeds the first index computation and is updated by each type-2 query.
Q2.How is the target sequence chosen?
idx = (x XOR lastAnswer) % n. The XOR with the previous answer is the defining twist — using x % n alone is wrong.
Q3.What index inside the sequence does type 2 read?
y % size of that sequence, so y wraps around the current length.
Q4.Do type-1 queries produce output?
No. Only type-2 queries append to the result list.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

You simulate q operations over n initially-empty sequences while carrying a running `lastAnswer` (starts at 0). For each query, the target sequence index is `(x ^ lastAnswer) % n`. Type 1 appends y to that sequence; type 2 reads element `y % size` of that sequence, sets `lastAnswer` to it, and records it. Keep n separate growable lists so append and indexed read are O(1) — the whole thing runs in O(q).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can read a precise operational spec and reproduce it exactly — correct state carry-over, the XOR-then-mod index, and the right output for only type-2 queries.

Where candidates slip

Forgetting to XOR with lastAnswer (using x % n directly), not initializing lastAnswer to 0, or storing all appends in one flat list and scanning to reconstruct a sequence, turning O(q) into O(q²).

How to stand out

Restate the index formula out loud before coding, and pick a structure (array of lists) that gives O(1) append and read so you can state O(q) confidently.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Baseline — Single Flat Log, Reconstruct on Read	`O(q²)`	`O(q)`	Show it as the tempting 'just store everything' idea, then explain why reconstructing a sequence per read is quadratic.	Read
2	Array of Lists — Direct Simulation (Optimal)Optimal	`O(q)`	`O(n + total appends)`	The intended answer: n separate growable lists, O(1) append and read, O(q) total.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewQuery (type, x, y)type?12Explore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Baseline — Single Flat Log, Reconstruct on Read

TimeO(q²)SpaceO(q)

Show it as the tempting 'just store everything' idea, then explain why reconstructing a sequence per read is quadratic.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You could record every append as a (sequenceIndex, value) pair in one list. How would you answer a type-2 read?

2Hint 2Explore hint

To read element j of sequence idx, you'd filter the log for that idx and then index into the filtered result. What does that filter cost?

3Hint 3Explore hint

If every type-2 query rescans the full log, how does total time grow with q?

A · Core idea

Store every append as a (idx, value) pair in one global list. To serve a type-2 query, walk that list, collect the values whose idx matches, then index into the collected list with y % size.

Why someone reaches for this. It feels simpler to have one container than to manage n separate ones, and it sidesteps thinking about how to size the per-sequence lists up front.

Why it's quadratic. A type-2 query has to reconstruct the target sequence by filtering the whole log every time — there's no direct handle on 'sequence idx'. With up to q appends and q reads, that's O(q) work per read and O(q²) overall. For q = 10⁵ that's ten billion operations — far too slow.

The fix. The sequences are independent and addressed by index, so give each its own list. Then 'append to sequence idx' and 'read position j of sequence idx' are both direct O(1) operations, no scanning.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 2, queries = [[1,0,5],[1,1,7],[2,1,0]]

Array state

read idx 1

keep entries with idx == 1

(0,5)

[0]

(1,7)

[1]

(0,3)

[2]

Current pointerResolved stateNot processed

Final result[7]

C · Code with teaching comments

Reference implementation previewpublic List<Integer> dynamicArray(int n, int[][] queries) { List<int[]> log = new ArrayList<>(); List<Integer> answers = new ArrayList<>(); int lastAnswer = 0; for (int[] q : queries) {Explore the full code

solution.javaJava

Baseline — Single Flat Log, Reconstruct on Read — reference

2 teaching notes

1
public List<Integer> dynamicArray(int n, int[][] queries) {
2
    List<int[]> log = new ArrayList<>();
3
    List<Integer> answers = new ArrayList<>();
4
    int lastAnswer = 0;
5
    for (int[] q : queries) {
6
        int idx = (q[1] ^ lastAnswer) % n;
7
        if (q[0] == 1) {
8
            log.add(new int[]{idx, q[2]});
9
        } else {
10
            List<Integer> seq = new ArrayList<>();
11
            // Rescans the entire append log on every type-2 query — the source of the
12
            // O(q²) cost.
13
            for (int[] entry : log) {
14
                if (entry[0] == idx) seq.add(entry[1]);
15
            }
16
            // Correct read, but only after an expensive reconstruction.
17
            lastAnswer = seq.get(q[2] % seq.size());
18
            answers.add(lastAnswer);
19
        }
20
    }
21
    return answers;
22
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.22 lines

D · Why it works and complexityO(q²) timeO(q) spaceOpen the invariant and proofExplore the proof

Whenever you find yourself filtering a flat log to recover a sub-collection on every query, that's the signal to key the data by that sub-collection up front — here, an array of lists indexed directly by sequence number.

ComplexityO(q²) time, O(q) space — Each type-2 read scans the entire append log to gather one sequence's elements: O(q) per read, up to q reads → O(q²).

E · Edge cases and pitfalls5many type-2 queries — Each triggers a full log scan, exposing the O(q²) blowup.Explore edge cases

Edge cases handled

many type-2 queriesEach triggers a full log scan, exposing the O(q²) blowup.
n = 1All appends land in one logical sequence; the filter returns everything.

Pitfalls

Rescanning the log per read — quadratic on large q.
Forgetting the XOR and using x % n directly.
Not seeding lastAnswer to 0 before the loop.

03.2

Approach 2 of 2 · Optimal

Array of Lists — Direct Simulation (Optimal)

TimeO(q)SpaceO(n + total appends)

The intended answer: n separate growable lists, O(1) append and read, O(q) total.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The sequences are addressed by an integer index. What structure gives O(1) access to the idx-th collection?

2Hint 2Explore hint

Make an array of n lists. Append pushes to seq[idx]; read indexes into seq[idx] directly.

3Hint 3Explore hint

Carry lastAnswer across iterations and recompute idx each time as (x XOR lastAnswer) % n.

A · Core idea

Hold n independent growable lists in an array and a single lastAnswer initialized to 0. Process queries one by one, deriving the target index from lastAnswer each time.

Why the index formula is the crux. Every query computes idx = (x ^ lastAnswer) % n. The XOR couples each query to the result of the previous type-2 query, so you can't precompute indices or reorder queries — you must step through them in order, carrying state. Dropping the XOR (using x % n) targets the wrong sequence and produces wrong output that still 'looks plausible', which is why it's such a common silent bug.

Why an array of lists. The sequences are addressed by a small integer idx in [0, n), so an array gives O(1) access to the right list. Appending to a growable list (ArrayList / Python list) is amortized O(1), and reading position y % size is O(1). No scanning, no reconstruction — exactly the cost you'd hope for.

Why `y % size` for reads. The read index y can exceed the current length of the chosen sequence, so it's wrapped with % size. Since the problem guarantees the target sequence is non-empty on a type-2 query, the modulo is always well-defined (no division by zero).

Why only type-2 emits output. Type-1 mutates state silently; type-2 both updates lastAnswer (affecting all future indices) and appends to the answer list. Keeping that distinction straight is the last piece of faithfully reproducing the spec.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 2, queries = [[1,0,5],[1,1,7],[1,0,3],[2,1,0],[2,1,1]]

Array state

seq0

holds [5, 3]

[0]

[1]

Current pointerResolved stateNot processed

Final result[7, 3]

C · Code with teaching comments

solution.javaJava

Array of Lists — Direct Simulation (Optimal) — optimal

3 teaching notes

1
public List<Integer> dynamicArray(int n, int[][] queries) {
2
    List<List<Integer>> seq = new ArrayList<>();
3
    for (int i = 0; i < n; i++) {
4
        seq.add(new ArrayList<>());
5
    }
6
    List<Integer> answers = new ArrayList<>();
7
    int lastAnswer = 0;
8
    for (int[] q : queries) {
9
        // The defining formula — XOR x with the carried lastAnswer, then mod n.
10
        int idx = (q[1] ^ lastAnswer) % n;
11
        if (q[0] == 1) {
12
            // Amortized O(1) append to the chosen sequence.
13
            seq.get(idx).add(q[2]);
14
        } else {
15
            List<Integer> target = seq.get(idx);
16
            // Wrap y into the sequence length and update the carried answer.
17
            lastAnswer = target.get(q[2] % target.size());
18
            answers.add(lastAnswer);
19
        }
20
    }
21
    return answers;
22
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.22 lines

D · Why it works and complexityO(q) timeO(n + total appends) spaceOpen the invariant and proofExplore the proof

There's no asymptotic cleverness to chase here — the win is choosing the data structure that matches how the data is addressed. 'Indexed by a small integer' ⇒ array; 'grows over time' ⇒ growable list. Match the structure to the access pattern and the O(q) bound falls out.

ComplexityO(q) time, O(n + total appends) space — Each query does O(1) work: one index computation, then either an amortized-O(1) append or an O(1) positional read. Across q queries that's O(q). Space is O(n) for the outer array plus the total number of appended elements.

E · Edge cases and pitfalls5n = 1 — idx is always 0; all appends and reads hit the single sequence.Explore edge cases

Edge cases handled

n = 1idx is always 0; all appends and reads hit the single sequence.
y larger than sequence lengthy % size wraps it into a valid position.

Pitfalls

Initializing the lists with [[]] * n in Python — that aliases one shared list across all indices.
Using x % n instead of (x ^ lastAnswer) % n.
Forgetting to update lastAnswer on type-2, breaking every later index.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic List<Integer> dynamicArray(int n, int[][] queries) { List<List<Integer>> seq = new ArrayList<>(); for (int i = 0; i < n; i++) { seq.add(new ArrayList<>()); }Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Dropping the XOR

The index must couple to the previous answer; using x alone targets the wrong sequence and silently produces wrong output.

Explore the code comparison

Don't write this

int idx = q[1] % n;

Write this instead

int idx = (q[1] ^ lastAnswer) % n;

Aliased sequences in Python

[[]] * n creates n references to the SAME inner list, so an append to one shows up in all of them.

Explore the code comparison

Don't write this

seq = [[]] * n

Write this instead

seq = [[] for _ in range(n)]

Stale lastAnswer

If a type-2 query reads the value but doesn't update lastAnswer, every subsequent index is computed from the wrong base.

Explore the code comparison

Don't write this

answers.append(target[y % len(target)])

Write this instead

last_answer = target[y % len(target)]
answers.append(last_answer)

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Stateful simulation with a carried lastAnswer index

Code pattern to memorize

idx = (x ^ lastAnswer) % n
type 1: seq[idx].append(y)
type 2: lastAnswer = seq[idx][y % len(seq[idx])]; record lastAnswer

Rules to remember

1Initialize lastAnswer = 0 before the first query — it seeds the very first index computation.
2The target index is (x XOR lastAnswer) % n, not just x % n — the XOR with the previous answer is the whole gimmick.
3Type-2 reads use y % size(target), wrapping the index into the chosen sequence's current length.
4Keep n separate lists so append is amortized O(1) and indexed read is O(1) — don't store everything in one flat log.
5Only type-2 queries produce output; type-1 queries silently mutate state.

Use this pattern when

A problem describes an exact procedure and asks you to reproduce its outputs
Operations carry forward state (here, lastAnswer) that affects later steps
You need O(1) append and O(1) positional read on several growing collections

Choose another pattern when

There's a closed-form or pattern you can derive instead of stepping through every op
State doesn't carry between operations → each query is independent and you can batch
You need range queries over the sequences → a segment tree / Fenwick, not plain lists

Interview takeaway

Simulation problems are graded on faithfully translating the spec, not on cleverness. The two traps here are seeding `lastAnswer = 0` and computing the index as `(x ^ lastAnswer) % n` — get those right and the rest is O(1) list operations.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternStateful simulation. Faithfully reproduce the spec's procedure, carrying lastAnswer between steps and matching the data structure (array of lists) to the access pattern (index-addressed, append-grown). The output bound O(q) follows from O(1) append and read.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern

←

Bill Division (Bon Appétit)

Continue · Next problem

Maximum Hourglass Sum

easyArraysSometimes asked

Dynamic Array

Arrays & Hashing · 46 of 83 · 6 min

Declare n empty sequences and a variable lastAnswer = 0. Process q queries; each query has a type and two integers x and y.

For every query, compute idx = (x XOR lastAnswer) % n.

Type 1 1 x y: append integer y to the sequence at index idx.
Type 2 2 x y: assign lastAnswer = seq[idx][y % size(seq[idx])] and record lastAnswer.

Return the list of all values recorded by type-2 queries, in order.

In plain English

Examples

Example 1

Input: n = 2, queries = [[1,0,5],[1,1,7],[1,0,3],[2,1,0],[2,1,1]]
Output: [7, 3]
Note: Appends build seq0=[5,3], seq1=[7]. Query [2,1,0]: idx=(1^0)%2=1 → seq1[0]=7, lastAnswer=7. Query [2,1,1]: idx=(1^7)%2=0 → seq0[1%2=1]=3.

Example 2

Input: n = 1, queries = [[1,0,100],[2,5,0]]
Output: [100]
Note: Only sequence 0 exists. Append 100, then idx=(5^0)%1=0, read seq0[0%1=0]=100.

Constraints

1 ≤ n, q ≤ 10⁵
0 ≤ x, y ≤ 10⁹
Each type-2 query targets a sequence with at least one element
lastAnswer starts at 0

Clarifying questions4First question: What is lastAnswer before the first query?Explore questions

Q1.What is lastAnswer before the first query?
0. It seeds the first index computation and is updated by each type-2 query.
Q2.How is the target sequence chosen?
idx = (x XOR lastAnswer) % n. The XOR with the previous answer is the defining twist — using x % n alone is wrong.
Q3.What index inside the sequence does type 2 read?
y % size of that sequence, so y wraps around the current length.
Q4.Do type-1 queries produce output?
No. Only type-2 queries append to the result list.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can read a precise operational spec and reproduce it exactly — correct state carry-over, the XOR-then-mod index, and the right output for only type-2 queries.

Where candidates slip

Forgetting to XOR with lastAnswer (using x % n directly), not initializing lastAnswer to 0, or storing all appends in one flat list and scanning to reconstruct a sequence, turning O(q) into O(q²).

How to stand out

Restate the index formula out loud before coding, and pick a structure (array of lists) that gives O(1) append and read so you can state O(q) confidently.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Baseline — Single Flat Log, Reconstruct on Read	`O(q²)`	`O(q)`	Show it as the tempting 'just store everything' idea, then explain why reconstructing a sequence per read is quadratic.	Read
2	Array of Lists — Direct Simulation (Optimal)Optimal	`O(q)`	`O(n + total appends)`	The intended answer: n separate growable lists, O(1) append and read, O(q) total.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Baseline — Single Flat Log, Reconstruct on Read

TimeO(q²)SpaceO(q)

Show it as the tempting 'just store everything' idea, then explain why reconstructing a sequence per read is quadratic.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You could record every append as a (sequenceIndex, value) pair in one list. How would you answer a type-2 read?

2Hint 2Explore hint

To read element j of sequence idx, you'd filter the log for that idx and then index into the filtered result. What does that filter cost?

3Hint 3Explore hint

If every type-2 query rescans the full log, how does total time grow with q?

A · Core idea

Store every append as a (idx, value) pair in one global list. To serve a type-2 query, walk that list, collect the values whose idx matches, then index into the collected list with y % size.

Why someone reaches for this. It feels simpler to have one container than to manage n separate ones, and it sidesteps thinking about how to size the per-sequence lists up front.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 2, queries = [[1,0,5],[1,1,7],[2,1,0]]

Array state

read idx 1

keep entries with idx == 1

(0,5)

[0]

(1,7)

[1]

(0,3)

[2]

Current pointerResolved stateNot processed

Final result[7]

C · Code with teaching comments

solution.javaJava

Baseline — Single Flat Log, Reconstruct on Read — reference

2 teaching notes

1
public List<Integer> dynamicArray(int n, int[][] queries) {
2
    List<int[]> log = new ArrayList<>();
3
    List<Integer> answers = new ArrayList<>();
4
    int lastAnswer = 0;
5
    for (int[] q : queries) {
6
        int idx = (q[1] ^ lastAnswer) % n;
7
        if (q[0] == 1) {
8
            log.add(new int[]{idx, q[2]});
9
        } else {
10
            List<Integer> seq = new ArrayList<>();
11
            // Rescans the entire append log on every type-2 query — the source of the
12
            // O(q²) cost.
13
            for (int[] entry : log) {
14
                if (entry[0] == idx) seq.add(entry[1]);
15
            }
16
            // Correct read, but only after an expensive reconstruction.
17
            lastAnswer = seq.get(q[2] % seq.size());
18
            answers.add(lastAnswer);
19
        }
20
    }
21
    return answers;
22
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.22 lines

D · Why it works and complexityO(q²) timeO(q) spaceOpen the invariant and proofExplore the proof

ComplexityO(q²) time, O(q) space — Each type-2 read scans the entire append log to gather one sequence's elements: O(q) per read, up to q reads → O(q²).

E · Edge cases and pitfalls5many type-2 queries — Each triggers a full log scan, exposing the O(q²) blowup.Explore edge cases

Edge cases handled

many type-2 queriesEach triggers a full log scan, exposing the O(q²) blowup.
n = 1All appends land in one logical sequence; the filter returns everything.

Pitfalls

Rescanning the log per read — quadratic on large q.
Forgetting the XOR and using x % n directly.
Not seeding lastAnswer to 0 before the loop.

03.2

Approach 2 of 2 · Optimal

Array of Lists — Direct Simulation (Optimal)

TimeO(q)SpaceO(n + total appends)

The intended answer: n separate growable lists, O(1) append and read, O(q) total.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The sequences are addressed by an integer index. What structure gives O(1) access to the idx-th collection?

2Hint 2Explore hint

Make an array of n lists. Append pushes to seq[idx]; read indexes into seq[idx] directly.

3Hint 3Explore hint

Carry lastAnswer across iterations and recompute idx each time as (x XOR lastAnswer) % n.

A · Core idea

Hold n independent growable lists in an array and a single lastAnswer initialized to 0. Process queries one by one, deriving the target index from lastAnswer each time.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 2, queries = [[1,0,5],[1,1,7],[1,0,3],[2,1,0],[2,1,1]]

Array state

seq0

holds [5, 3]

[0]

[1]

Current pointerResolved stateNot processed

Final result[7, 3]

C · Code with teaching comments

solution.javaJava

Array of Lists — Direct Simulation (Optimal) — optimal

3 teaching notes

1
public List<Integer> dynamicArray(int n, int[][] queries) {
2
    List<List<Integer>> seq = new ArrayList<>();
3
    for (int i = 0; i < n; i++) {
4
        seq.add(new ArrayList<>());
5
    }
6
    List<Integer> answers = new ArrayList<>();
7
    int lastAnswer = 0;
8
    for (int[] q : queries) {
9
        // The defining formula — XOR x with the carried lastAnswer, then mod n.
10
        int idx = (q[1] ^ lastAnswer) % n;
11
        if (q[0] == 1) {
12
            // Amortized O(1) append to the chosen sequence.
13
            seq.get(idx).add(q[2]);
14
        } else {
15
            List<Integer> target = seq.get(idx);
16
            // Wrap y into the sequence length and update the carried answer.
17
            lastAnswer = target.get(q[2] % target.size());
18
            answers.add(lastAnswer);
19
        }
20
    }
21
    return answers;
22
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.22 lines

D · Why it works and complexityO(q) timeO(n + total appends) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls5n = 1 — idx is always 0; all appends and reads hit the single sequence.Explore edge cases

Edge cases handled

n = 1idx is always 0; all appends and reads hit the single sequence.
y larger than sequence lengthy % size wraps it into a valid position.

Pitfalls

Initializing the lists with [[]] * n in Python — that aliases one shared list across all indices.
Using x % n instead of (x ^ lastAnswer) % n.
Forgetting to update lastAnswer on type-2, breaking every later index.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Dropping the XOR

The index must couple to the previous answer; using x alone targets the wrong sequence and silently produces wrong output.

Explore the code comparison

Don't write this

int idx = q[1] % n;

Write this instead

int idx = (q[1] ^ lastAnswer) % n;

Aliased sequences in Python

[[]] * n creates n references to the SAME inner list, so an append to one shows up in all of them.

Explore the code comparison

Don't write this

seq = [[]] * n

Write this instead

seq = [[] for _ in range(n)]

Stale lastAnswer

If a type-2 query reads the value but doesn't update lastAnswer, every subsequent index is computed from the wrong base.

Explore the code comparison

Don't write this

answers.append(target[y % len(target)])

Write this instead

last_answer = target[y % len(target)]
answers.append(last_answer)

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Stateful simulation with a carried lastAnswer index

Code pattern to memorize

idx = (x ^ lastAnswer) % n
type 1: seq[idx].append(y)
type 2: lastAnswer = seq[idx][y % len(seq[idx])]; record lastAnswer

Rules to remember

1Initialize lastAnswer = 0 before the first query — it seeds the very first index computation.
2The target index is (x XOR lastAnswer) % n, not just x % n — the XOR with the previous answer is the whole gimmick.
3Type-2 reads use y % size(target), wrapping the index into the chosen sequence's current length.
4Keep n separate lists so append is amortized O(1) and indexed read is O(1) — don't store everything in one flat log.
5Only type-2 queries produce output; type-1 queries silently mutate state.

Use this pattern when

A problem describes an exact procedure and asks you to reproduce its outputs
Operations carry forward state (here, lastAnswer) that affects later steps
You need O(1) append and O(1) positional read on several growing collections

Choose another pattern when

There's a closed-form or pattern you can derive instead of stepping through every op
State doesn't carry between operations → each query is independent and you can batch
You need range queries over the sequences → a segment tree / Fenwick, not plain lists

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern

←

Bill Division (Bon Appétit)

Continue · Next problem

Maximum Hourglass Sum