LC Patterns — Probability & Randomness

The primitives (Python)

import random
random.random()            # uniform float in [0, 1)
random.randint(a, b)       # uniform int in [a, b]  — INCLUSIVE both ends
random.randrange(n)        # uniform int in [0, n)  — the off-by-one-safe choice
random.shuffle(lst)        # in-place Fisher–Yates (know what it does inside)
random.choice(lst)         # uniform element

randint inclusivity vs randrange exclusivity causes real interview bugs — pick one idiom (randrange) and stick to it.

Facts to have loaded

• Geometric distribution: independent trials with success probability p → expected trials = 1/p. This is the running-time analysis of every rejection sampler; compute it aloud (470: p = 40/49, E ≈ 1.22 rounds ≈ 2.45 calls).
• Expected value of DP on probabilities: transition probabilities multiply along a path, sum over paths — i.e., new[s'] += old[s] · P(s→s'). Probability DP is weighted path counting: same table shapes as the DP files, values in [0,1].
• Conditional probability / Bayes appear on LC only inside proofs (rejection sampling's "conditional on acceptance"), not as computations — know the phrase, don't over-prepare the math.
• Floats are fine here (answers accepted within 10⁻⁵) — the one topic in this series where float discipline relaxes. Still: sum probabilities in a consistent order, and never test == 1.0.

Universal pitfalls

1. Producing randomness without proving its distribution. "It looks shuffled" is not an argument. If you can't prove it, assume it's biased — most plausible-looking random code is (see 384's classic bug below).
2. Arithmetic remapping of rejected samples — taking x % 10 on a uniform 1..49 without rejecting 41..49 overweights some outputs. Rejection means throw away and retry, never "fix up".
3. Modulo bias in general: big_uniform % n is only uniform when the range divides evenly. State it; it's the same bug as #2 in different clothes.
4. Confusing "equally likely elements" with "equally likely outcomes" — 497 (random point in rectangles) weights by integer point count (w+1)(h+1), not by area w·h; the +1 fencepost is the whole problem.
5. Simulating what has a closed form — Monte Carlo is never the intended LC answer; if you catch yourself proposing simulation, look for the DP or the symmetry.

What it is: You have a fair random tool that produces one shape of output, but you need a fair (uniform) result of a different shape. The move: generate over a bigger space you can hit evenly, keep the sample if it lands in a "good" region, and if it lands in a "bad" region, throw it away and roll again — never try to patch or reuse a bad sample.

Intuition: the whole idea rests on one fact — if you start fair and only keep the samples that land in a subset, what's left is still fair inside that subset. That's also why patching rejects breaks things: a patch squeezes many thrown-away values onto a few outputs, unevenly, which is the exact bias you're avoiding. rand10 from rand7 (470): roll twice to build a fair number 1..49 ((r1−1)·7 + r2, a 7×7 grid); keep ≤ 40 and output x % 10 + 1. Since 40 = 4×10, exactly 4 of the kept values map to each output (a clean 4-to-1 map) → fair. Random point in a circle (478): pick a fair point in the square around the circle; keep it if it's inside the circle, otherwise resample (you keep about π/4 ≈ 78.5% of the time). The tempting shortcut for 478 — pick a random angle and random radius directly — is biased: area grows with radius², so a plain uniform radius crowds points near the center. Fixing it needs r = R·√u; rejection sampling avoids that math entirely.

Approach: loop until you get a keeper; make sure your final map is even — every output must come from the same number of kept inputs (say this check out loud). Cost: if you keep a sample with probability p, you expect 1/p rolls (§0). Follow-up for 470 ("use fewer rand7 calls"): the rejected 41..49 is itself a free fair 1..9 — reuse it with another rand7 to build 1..63, keep ≤ 60, and recurse on the leftovers. Know the idea, don't memorize the exact numbers.

What it is: Pick index i with a chance proportional to its weight w[i] — heavier items get picked more often. Lay all the weights end-to-end on a number line (that's the prefix sums), throw one random dart at the whole line, and binary-search to find which segment it landed in.

Intuition: item i takes up a length-w[i] chunk of a line of total length W, so a random dart lands in it with chance w[i]/W — building it this way is the proof, nothing more to show. Finding "which segment did the dart hit" is just find-the-first-prefix-sum-≥-dart — the same binary search as Pattern 2 of binary search. Rectangles (497) is the 2-D version: weight each rectangle by how many integer points it contains, (w+1)·(h+1) (§0 pitfall 4), dart-pick which rectangle, then pick a random point inside it with divmod — two random picks combining into one fair pick over all the rectangles (this needs the rectangles not to overlap, which the problem guarantees — note that you're relying on it).

Approach: build the prefix array once in the constructor (each query must be O(log n) — the problem is set up to punish an O(n) scan per query). Dart: target = random.randint(1, total); answer is bisect_left(prefix, target). Integer dart + bisect_left fit together cleanly; if you throw a float dart with random.random()·total instead, you need bisect_right-style reasoning — pick one convention and hand-check it on weights = [1] and [1, 3] (the two go-to test cases: a single item must always be picked; the second must come up ~75% of the time).

What it is: Pick one random element, each equally likely, from a sequence whose length you don't know ahead of time — in a single pass using O(1) memory. Keep just one candidate; when the i-th element arrives, replace the candidate with probability 1/i.

Intuition: for every element to be equally likely after seeing i of them, the newest one must win with chance 1/i — and each earlier winner must survive with chance (i−1)/i, which the same rule gives you for free. The proof is a chain of fractions that cancel: P(element j is the final pick) = (1/j) · (j/(j+1)) · ((j+1)/(j+2)) ⋯ ((n−1)/n) = 1/n — every numerator cancels the next denominator; practice saying it in one breath, it is the interview. Random pick index (398): same trick, but only on elements equal to the target — count matches m as you scan and replace with chance 1/m; picks fairly among duplicates without ever storing their positions.

Approach: if random.randrange(i) == 0: keep = current (i is the 1-based count — randrange(1) is always 0, so the first element is kept automatically with no special case: the elegant part). Worth mentioning: to pick k elements, keep the first k, then replace a random one of them with chance k/i (LC 382's follow-up). Trade-off to name in 398: a hashmap of value → list of indices gives O(1) queries but O(n) memory; reservoir gives O(n) queries but O(1) memory — which is better depends on how often you query, and naming that trade-off is the senior answer.

What it is: Produce a fully random shuffle (every ordering equally likely), or pick without repeats from a huge or partly-blocked range of indices — using the swap trick: pick a random element from the not-yet-touched part, swap it to the edge, and shrink the untouched part by one. When the array is too big to actually build, run the same steps virtually in a hashmap.

Intuition: Fisher–Yates (384): for i from n−1 down to 0, swap a[i] with a[j] where j is random in [0, i] — position i gets each remaining element with equal chance, so every ordering ends up with chance exactly 1/n! (there are n · (n−1) ⋯ 1 equally likely sequences of choices, one for each ordering — that one-to-one match is the proof). The famous broken version — j random in [0, n−1] every time — makes nⁿ equally likely sequences, and nⁿ can't split evenly into n! orderings (it isn't divisible by n!), so it's biased. Know this counterexample cold; it's the most-asked follow-up. Random flip matrix (519): pick without repeats from n·m virtual cells — draw r = randrange(remaining), and a hashmap fakes "swap r with the last remaining cell" via map[r] = map.get(last, last) — Fisher–Yates where only the touched cells actually exist. Blacklist pick (710): split [0, n) so the allowed indices fill a front block of size n−b — remap each blocked index sitting in the front block to an allowed index in the tail (a one-time hashmap); then just pick randomly in the front block, O(1) per query, O(b) memory.

Approach: 384: keep the original array for reset(); shuffle a copy backward with randrange(i+1). 519: remaining -= 1 after each flip; the two-sided get handles chains of earlier swaps — trace one collision by hand before you trust it. 710: build the remap by walking the blocked-in-front indices against the allowed-in-tail ones (a two-pointer sweep over the sorted blacklist, or a set-difference walk); a query is map.get(randrange(n − b), itself).

What it is: "What's the probability that ⟨process⟩ ends up in ⟨state⟩ after ⟨k steps / when it stops⟩?" Model it as a set of states plus the chances of moving between them, then fill in a probability table step by step — it's just a DP table with fractions in it.

Intuition: P(in a state after t steps) = sum over every state that could lead here of P(was there at t−1) · P(made that move) — the exact same shape as counting-paths DP, only the weights are fractions; every DP habit (designing the state, choosing direction, rolling arrays) carries over unchanged. Knight (688): state = (moves made so far, square); each of the 8 moves has weight 1/8; probability that walks off the board just disappears (that's what "chance the knight is still on the board" means — you add up whatever's left in the table). New 21 game (837): P(reaching total s) = the average of the previous maxPts reachable values → a sliding-window sum turns O(n·maxPts) into O(n), the same window trick from the DP files applied to probabilities; once a total hits K the player stops drawing, which controls which states keep going. Soup servings (808): memoize P over (a, b) with the four ¼-weighted moves; the twist here is a bit of math, not the structure — the servings tend to empty soup A first, so for large n the answer gets very close to 1, and a cutoff (n above ~a few thousand → return 1.0) is required because the state space blows up and the 10⁻⁵ tolerance explicitly allows it. Divide all portions by 25 first (everything is a multiple of 25 — this shrinks the state space, and say why it loses nothing).

Approach: it's literally your DP checklist: define the state so the future depends only on it (add "moves used so far" when the number of steps is capped); pick push-forward or pull-backward; start with probability 1 at the starting state; weight each move by its probability (each row sums to ≤ 1 — some probability may leak out when the process stops); the answer is the sum over the states you care about. Use a rolling 2-layer table when only step t−1 feeds step t (688). Sanity check to run while deriving: total probability is either kept or drains away — it never grows; if your table adds up to more than 1, some move is being counted twice.

What it is: Problems that look like they need heavy case analysis or simulation but fall apart once you spot a symmetry: two outcomes that mirror each other must be equally likely, and a detail that doesn't change the answer can be thrown away. The code ends up trivial; the argument is the whole point.

Intuition: airplane seats (1227): the bumped passenger's chain of displacements can only end at seat 1 or seat n — and nothing in the process treats those two seats differently (every choice along the way handles them identically) → by symmetry each is the final seat with chance ½; answer: 1.0 for n = 1, otherwise exactly 0.5. Working small cases by hand (n = 2, 3) shows the answer is always ½, and then you go find the symmetry that explains it — discovering it in that order is fine, present it that way. Ants on a plank (1503): when two ants collide and both turn around, just relabel them — two ants bouncing off each other looks exactly like two ants passing straight through — so the last fall time is simply the longest solo walk: max(max(left positions), max(n − right positions)). All the collision bookkeeping disappears. Robots (2731): same pass-through trick, with one catch — the positions ignore which robot is which, but the sorted order of the robots is preserved, and that's what the distance-sum needs; erase identities, compute, then re-sort.

Approach: there's no template, there's a method: (1) work tiny cases by hand; (2) notice the answer is suspiciously simple (a constant, a max, a sum); (3) look for the symmetry or "these are interchangeable" fact that explains it; (4) present it as claim → argument → two lines of code. The two reusable symmetry shapes on LC: swappable endpoints (1227's seat 1 vs seat n) and relabelable colliding particles (1503/2731 — also the key to several physics-flavored puzzles).