Linked List Random Node (LeetCode 382)
You will see how one walk and one random draw per node pick a uniform random node without knowing the length.
Build a class, Solution, around a singly linked list, that hands back the value of a node picked at random.
Solution(ListNode head)receives the first node of the list.int getRandom()returns the value of one node of the list, chosen so that every node has the same chance. Each call makes a new, independent choice.
Nodes may hold equal values, so a value stored in two nodes comes back twice as often as a value stored in one. Any value that is in the list is a correct single answer; long runs of calls are checked for an even spread over the nodes. LeetCode's follow-up asks what to do when the list is too long to store and its length is unknown, and whether you can pick with no extra space.
Worked Examples
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []][null, 1, 3, 2, 2, 3]⚖️Formal Constraints & Bounds
The number of nodes in the linked list will be in the range
[1, 104].-104 <= Node.val <= 104At most
104calls will be made togetRandom.
Why It Works & Core Invariant
Keep the i-th node with chance exactly 1/i. The new node gets in with 1/i, and each earlier node, which held the spot with 1/(i - 1), survives with (i - 1)/i, which is also 1/i: after the last node every node has chance 1/n, with no length and no copy.
Real-World Scenario & Production Applications
A log or metrics pipeline that keeps a uniform sample of events from a stream it can read only once and whose length it never knows, such as picking a random request to trace from millions that flow past, with one slot of memory per sample.
Subproblems & Recurrence Decomposition3 Phases
Establish 4-wall perimeter bounding (top, bottom, left, right) or binary exponent halving state x^n = (x^2)^(n/2).
top, bottom = 0, R - 1
left, right = 0, C - 1
res = []Step-by-Step Execution Trace Table
One call of getRandom() on 1 -> 2 -> 3, with the draws randrange(1) = 0, randrange(2) = 1, randrange(3) = 0:
| Step | Node | i | Draw random.randrange(i) | Kept? | result | Chance each node seen so far is result |
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 0 | yes (always, 1/1) | 1 | 1: 1 |
| 2 | 2 | 2 | 1 | no (chance 1/2) | 1 | 1: 1/2, 2: 1/2 |
| 3 | 3 | 3 | 0 | yes (chance 1/3) | 3 | 1: 1/3, 2: 1/3, 3: 1/3 |
The call returns 3. Another call makes new draws, and each of the three values comes back one time in three.
| 1 | The length is unknown until the walk ends, so decide as you go: keep one candidate `result`, and give each new node a chance to replace it. |
| 2 | Keep this true: after the walk has seen `i` nodes, each of them is `result` with the same chance, 1/i. |
| 3 | One pass over the list per call, counting the nodes; at each node one random draw decides whether it replaces `result`; return `result` after the last node. |
| 4 | The trap: count this node before the draw and keep it with chance exactly 1/i. A chance of 1/(i + 1) keeps the head only half the time and can return the starting 0. |
Target: Linked List Random Node (LeetCode 382). No copy of the values: every pick walks the list again, so the extra memory stays O(1).
Boundary pointers contract inward after each directional sweep; modular arithmetic bounds state cyclically.
while top <= bottom and left <= right: sweep right, down, left, up, contracting respective pointer.
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
The easy answer copies the values into an array and picks a random index, but that needs O(N) extra memory and the whole list up front; LeetCode's follow-up takes both away. Reservoir Sampling picks while it walks: keep one candidate, result, count the nodes with i, and let the i-th node replace result with chance exactly 1/i, drawn as random.randrange(i) == 0. When the walk ends, every node has had the same chance to be the one left in result.
🎟️ The Analogy: A Raffle Where Tickets Keep Arriving
People walk into a room one at a time, and one prize must end up with a random person, but nobody knows how many will come. The first person holds the prize. When the second arrives, a coin decides whether the prize moves to them. When the third arrives, a three-sided die decides; the i-th newcomer takes the prize with chance 1/i. Whoever holds it when the door closes won a fair raffle: each newcomer got in with 1/i, and everyone already in the room kept it with exactly the chance that makes all shares equal.
🪄 The Mathematical Harmony / Magic Trick
i += 1if random.randrange(i) == 0: result = node.val Claim: after i nodes, each of them is result with chance 1/i. It holds for i = 1, because randrange(1) is always 0. If it holds for i - 1, the new node gets in with 1/i, and each earlier node, result with chance 1/(i - 1), is not replaced with chance (i - 1)/i, so it stays with 1/(i - 1) · (i - 1)/i = 1/i. The counter must include the current node before the draw; randrange(i + 1) would give the head only a 1/2 chance and could leave result at its starting 0.
💡 Summary
One walk per call: i += 1, keep the node when random.randrange(i) == 0, and never stop early. time per getRandom, extra space, and no length needed.
The wrong chance: count this node before the draw and keep it when
random.randrange(i) == 0, a chance of exactly 1/i.randrange(i + 1)keeps[1, 2]'s 1 only a third of the time and returns the starting 0 another third.Stopping at the first hit: keep walking after a replacement. The first node's chance is 1/1, so returning at the first successful draw always returns the head.
Drawing once: draw inside
getRandom, on every call. An index chosen once in__init__returns the same value every time.Copying the list: an array plus
random.choicealso picks fairly, but needsO(N)extra memory and the length up front, which the follow-up's stream does not give.
4-Phase Thought Process Model
You will see how a senior engineer hears "every node has the same chance" plus "length unknown" and reaches for a reservoir.
Pattern Recognition Signals
The 10-second spot
"Every node has the same chance", "each call makes a new, independent choice", and the follow-up "the list is too long to store and its length is unknown" with "no extra space": a uniform pick from a sequence read once, front to back. That is the signal for Reservoir Sampling: keep one candidate and let the i-th item replace it with chance 1/i.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
After the walk has seen i nodes, each of them is result with chance exactly 1/i; the draw random.randrange(i) == 0 keeps the i-th node with chance 1/i, which is exactly what leaves every earlier node at 1/i too.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Count the node before the draw and keep it when
random.randrange(i) == 0:randrange(i + 1)keeps[1, 2]'s 1 only a third of the time and returns the starting 0 another third.Keep walking after a replacement: the first node's chance is 1/1, so returning at the first hit always returns the head.
Draw inside
getRandom, on every call: an index chosen once in__init__returns the same value every time.Don't copy the list: an array plus
random.choiceis fair, but usesO(N)extra memory and needs the length, which the follow-up takes away.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Reservoir Sampling. I don't know the length and I don't want to copy the list, so I pick while I walk. I keep one candidate, result, and a counter i. At each node I add one to i, and I replace result with this node's value when a random number from zero to i minus one is zero, so with chance exactly one over i. That's fair: the new node gets in with one over i, and every earlier node, which held the spot with one over i minus one, survives with i minus one over i, which leaves it at one over i as well. The trap is the counter: it has to include this node before the draw, otherwise the head only gets a half and the answer can stay at zero. And I never stop early. That's
O(N)time per call andO(1)extra space.
So: walk once per call, count the nodes, keep the i-th with chance 1/i, and never stop early.
Complexity & Mathematical Proof
O(N) per getRandom
__init__ only stores head: O(1). Each getRandom runs while node: once per node, N times, and each pass does one i += 1, one random.randrange(i) draw (O(1)), at most one assignment to result, and one step node = node.next. Nothing else loops, so a call costs O(N). A copy into an array would make each pick O(1) after an O(N) copy, but the win here is memory, not time.
O(1)
The object keeps one reference, self.head, and getRandom keeps result, i and node: O(1) extra space, whatever the length. The list itself is the input and is never copied.
T(N) = N · (one increment + one draw + one step) = O(N) per call
__init__ only stores head: O(1). Each getRandom runs while node: once per node, N times, and each pass does one i += 1, one random.randrange(i) draw (O(1)), at most one assignment to result, and one step node = node.next. Nothing else loops, so a call costs O(N). A copy into an array would make each pick O(1) after an O(N) copy, but the win here is memory, not time.
Derivation Progression
O(1)
__init__ keeps one reference and copies nothing.
N
while node: visits each node once and never stops early.
O(1)
i += 1, one random.randrange(i) draw, at most one assignment, and node = node.next.
O(N)
N constant-time steps; k calls cost O(k · N).
Variable Definitions
Number of nodes in the list (at most 10^4)
Memory Architecture & Bounds
O(1): no recursion
O(1): self.head, result, i, node
O(1): one integer per call
Boundary Best / Worst Cases
: every call walks the whole list
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "every node has the same chance", "each call makes a new, independent choice", "its length is unknown". A uniform pick from a sequence read once with no room to store it: Reservoir Sampling, keep the i-th item with chance 1/i.
Up to nodes and calls: one walk per call is up to steps in the worst case, the price of O(1) extra space. With memory to spare, an array of the values makes each pick O(1).
The draw must be unbiased for every i: rand() % i in C carries a small bias when RAND_MAX + 1 is not a multiple of i, so production code uses an unbiased bounded generator. Sampling k items instead of one keeps a reservoir of k and replaces a random slot with chance k/i. On a stream split across machines, each worker keeps its own reservoir with its count, and the reservoirs are merged by picking from each in proportion to its count.
Core Algorithmic State Invariants
`random.randrange(i) == 0` is true with chance exactly 1/i, and `i` already counts the current node, so the first node is always taken and every later one gets its fair share.
An item that was `result` with chance 1/(i - 1) survives the i-th draw with (i - 1)/i, so it stays with 1/i: the shares stay equal at every step, and the walk must never stop early.
One walk per call with three variables: no copy of the list and no length needed, at the cost of O(N) time per `getRandom`.
Linked List Random Node (LeetCode 382)
You will see how one walk and one random draw per node pick a uniform random node without knowing the length.
Build a class, Solution, around a singly linked list, that hands back the value of a node picked at random.
Solution(ListNode head)receives the first node of the list.int getRandom()returns the value of one node of the list, chosen so that every node has the same chance. Each call makes a new, independent choice.
Nodes may hold equal values, so a value stored in two nodes comes back twice as often as a value stored in one. Any value that is in the list is a correct single answer; long runs of calls are checked for an even spread over the nodes. LeetCode's follow-up asks what to do when the list is too long to store and its length is unknown, and whether you can pick with no extra space.
Worked Examples
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []][null, 1, 3, 2, 2, 3]⚖️Formal Constraints & Bounds
The number of nodes in the linked list will be in the range
[1, 104].-104 <= Node.val <= 104At most
104calls will be made togetRandom.
Why It Works & Core Invariant
Keep the i-th node with chance exactly 1/i. The new node gets in with 1/i, and each earlier node, which held the spot with 1/(i - 1), survives with (i - 1)/i, which is also 1/i: after the last node every node has chance 1/n, with no length and no copy.
Real-World Scenario & Production Applications
A log or metrics pipeline that keeps a uniform sample of events from a stream it can read only once and whose length it never knows, such as picking a random request to trace from millions that flow past, with one slot of memory per sample.
Subproblems & Recurrence Decomposition3 Phases
Establish 4-wall perimeter bounding (top, bottom, left, right) or binary exponent halving state x^n = (x^2)^(n/2).
top, bottom = 0, R - 1
left, right = 0, C - 1
res = []Step-by-Step Execution Trace Table
One call of getRandom() on 1 -> 2 -> 3, with the draws randrange(1) = 0, randrange(2) = 1, randrange(3) = 0:
| Step | Node | i | Draw random.randrange(i) | Kept? | result | Chance each node seen so far is result |
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 0 | yes (always, 1/1) | 1 | 1: 1 |
| 2 | 2 | 2 | 1 | no (chance 1/2) | 1 | 1: 1/2, 2: 1/2 |
| 3 | 3 | 3 | 0 | yes (chance 1/3) | 3 | 1: 1/3, 2: 1/3, 3: 1/3 |
The call returns 3. Another call makes new draws, and each of the three values comes back one time in three.
| 1 | The length is unknown until the walk ends, so decide as you go: keep one candidate `result`, and give each new node a chance to replace it. |
| 2 | Keep this true: after the walk has seen `i` nodes, each of them is `result` with the same chance, 1/i. |
| 3 | One pass over the list per call, counting the nodes; at each node one random draw decides whether it replaces `result`; return `result` after the last node. |
| 4 | The trap: count this node before the draw and keep it with chance exactly 1/i. A chance of 1/(i + 1) keeps the head only half the time and can return the starting 0. |
Target: Linked List Random Node (LeetCode 382). No copy of the values: every pick walks the list again, so the extra memory stays O(1).
Boundary pointers contract inward after each directional sweep; modular arithmetic bounds state cyclically.
while top <= bottom and left <= right: sweep right, down, left, up, contracting respective pointer.
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
The easy answer copies the values into an array and picks a random index, but that needs O(N) extra memory and the whole list up front; LeetCode's follow-up takes both away. Reservoir Sampling picks while it walks: keep one candidate, result, count the nodes with i, and let the i-th node replace result with chance exactly 1/i, drawn as random.randrange(i) == 0. When the walk ends, every node has had the same chance to be the one left in result.
🎟️ The Analogy: A Raffle Where Tickets Keep Arriving
People walk into a room one at a time, and one prize must end up with a random person, but nobody knows how many will come. The first person holds the prize. When the second arrives, a coin decides whether the prize moves to them. When the third arrives, a three-sided die decides; the i-th newcomer takes the prize with chance 1/i. Whoever holds it when the door closes won a fair raffle: each newcomer got in with 1/i, and everyone already in the room kept it with exactly the chance that makes all shares equal.
🪄 The Mathematical Harmony / Magic Trick
i += 1if random.randrange(i) == 0: result = node.val Claim: after i nodes, each of them is result with chance 1/i. It holds for i = 1, because randrange(1) is always 0. If it holds for i - 1, the new node gets in with 1/i, and each earlier node, result with chance 1/(i - 1), is not replaced with chance (i - 1)/i, so it stays with 1/(i - 1) · (i - 1)/i = 1/i. The counter must include the current node before the draw; randrange(i + 1) would give the head only a 1/2 chance and could leave result at its starting 0.
💡 Summary
One walk per call: i += 1, keep the node when random.randrange(i) == 0, and never stop early. time per getRandom, extra space, and no length needed.
The wrong chance: count this node before the draw and keep it when
random.randrange(i) == 0, a chance of exactly 1/i.randrange(i + 1)keeps[1, 2]'s 1 only a third of the time and returns the starting 0 another third.Stopping at the first hit: keep walking after a replacement. The first node's chance is 1/1, so returning at the first successful draw always returns the head.
Drawing once: draw inside
getRandom, on every call. An index chosen once in__init__returns the same value every time.Copying the list: an array plus
random.choicealso picks fairly, but needsO(N)extra memory and the length up front, which the follow-up's stream does not give.
4-Phase Thought Process Model
You will see how a senior engineer hears "every node has the same chance" plus "length unknown" and reaches for a reservoir.
Pattern Recognition Signals
The 10-second spot
"Every node has the same chance", "each call makes a new, independent choice", and the follow-up "the list is too long to store and its length is unknown" with "no extra space": a uniform pick from a sequence read once, front to back. That is the signal for Reservoir Sampling: keep one candidate and let the i-th item replace it with chance 1/i.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
After the walk has seen i nodes, each of them is result with chance exactly 1/i; the draw random.randrange(i) == 0 keeps the i-th node with chance 1/i, which is exactly what leaves every earlier node at 1/i too.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Count the node before the draw and keep it when
random.randrange(i) == 0:randrange(i + 1)keeps[1, 2]'s 1 only a third of the time and returns the starting 0 another third.Keep walking after a replacement: the first node's chance is 1/1, so returning at the first hit always returns the head.
Draw inside
getRandom, on every call: an index chosen once in__init__returns the same value every time.Don't copy the list: an array plus
random.choiceis fair, but usesO(N)extra memory and needs the length, which the follow-up takes away.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Reservoir Sampling. I don't know the length and I don't want to copy the list, so I pick while I walk. I keep one candidate, result, and a counter i. At each node I add one to i, and I replace result with this node's value when a random number from zero to i minus one is zero, so with chance exactly one over i. That's fair: the new node gets in with one over i, and every earlier node, which held the spot with one over i minus one, survives with i minus one over i, which leaves it at one over i as well. The trap is the counter: it has to include this node before the draw, otherwise the head only gets a half and the answer can stay at zero. And I never stop early. That's
O(N)time per call andO(1)extra space.
So: walk once per call, count the nodes, keep the i-th with chance 1/i, and never stop early.
Complexity & Mathematical Proof
O(N) per getRandom
__init__ only stores head: O(1). Each getRandom runs while node: once per node, N times, and each pass does one i += 1, one random.randrange(i) draw (O(1)), at most one assignment to result, and one step node = node.next. Nothing else loops, so a call costs O(N). A copy into an array would make each pick O(1) after an O(N) copy, but the win here is memory, not time.
O(1)
The object keeps one reference, self.head, and getRandom keeps result, i and node: O(1) extra space, whatever the length. The list itself is the input and is never copied.
T(N) = N · (one increment + one draw + one step) = O(N) per call
__init__ only stores head: O(1). Each getRandom runs while node: once per node, N times, and each pass does one i += 1, one random.randrange(i) draw (O(1)), at most one assignment to result, and one step node = node.next. Nothing else loops, so a call costs O(N). A copy into an array would make each pick O(1) after an O(N) copy, but the win here is memory, not time.
Derivation Progression
O(1)
__init__ keeps one reference and copies nothing.
N
while node: visits each node once and never stops early.
O(1)
i += 1, one random.randrange(i) draw, at most one assignment, and node = node.next.
O(N)
N constant-time steps; k calls cost O(k · N).
Variable Definitions
Number of nodes in the list (at most 10^4)
Memory Architecture & Bounds
O(1): no recursion
O(1): self.head, result, i, node
O(1): one integer per call
Boundary Best / Worst Cases
: every call walks the whole list
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "every node has the same chance", "each call makes a new, independent choice", "its length is unknown". A uniform pick from a sequence read once with no room to store it: Reservoir Sampling, keep the i-th item with chance 1/i.
Up to nodes and calls: one walk per call is up to steps in the worst case, the price of O(1) extra space. With memory to spare, an array of the values makes each pick O(1).
The draw must be unbiased for every i: rand() % i in C carries a small bias when RAND_MAX + 1 is not a multiple of i, so production code uses an unbiased bounded generator. Sampling k items instead of one keeps a reservoir of k and replaces a random slot with chance k/i. On a stream split across machines, each worker keeps its own reservoir with its count, and the reservoirs are merged by picking from each in proportion to its count.
Core Algorithmic State Invariants
`random.randrange(i) == 0` is true with chance exactly 1/i, and `i` already counts the current node, so the first node is always taken and every later one gets its fair share.
An item that was `result` with chance 1/(i - 1) survives the i-th draw with (i - 1)/i, so it stays with 1/i: the shares stay equal at every step, and the walk must never stop early.
One walk per call with three variables: no copy of the list and no length needed, at the cost of O(N) time per `getRandom`.
| Canonical Invariant | Concrete Code | Engineering Rationale |
|---|---|---|
| Keep only a pointer to the stream | self.head = head | No copy of the values: every pick walks the list again, so the extra memory stays O(1). |
| One candidate and a counter | result, i = 0, 0
node = self.head | `result` is the pick so far and `i` counts the nodes seen; the first node always replaces the starting 0. |
| Count the node before the draw | i += 1 | `node` is now the i-th value, so its chance must be 1/i. |
| Keep it with chance exactly 1/i (the trap) | if random.randrange(i) == 0:
result = node.val | `randrange(i)` is one of `0..i - 1`, so it is 0 with chance 1/i; every earlier node then keeps its share, 1/i. |
| Walk the whole stream, then answer | node = node.next
return result | Never stop at the first hit: the first node is always a hit. Only after the last node does every node have chance 1/n. |