Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
People labeled 1..n start sorted. Anyone can bribe the person directly in front to swap, at most twice each. Given the final order, count total bribes. If any person's label is more than 2 positions ahead of where it started (`q[i] − (i+1) > 2`), print 'Too chaotic'. Otherwise the bribe count for person `q[i]` is the number of larger labels sitting in front of them — and you only need to scan from index `max(0, q[i]−2)` to make it O(n).
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you spot that the '≤ 2 bribes each' cap bounds how far the inversion can reach, letting you shrink an O(n²) scan to a windowed O(n) one — and whether you handle the 1-indexed label math without off-by-one errors.
Where candidates slip
Checking `q[i] − i > 2` (forgetting the +1 for 1-indexing) or scanning from index 0, which is correct but O(n²) and may TLE on large inputs.
How to stand out
Derive the chaos check from 'forward moves ≤ 2', then explain why the scan can start at `q[i] − 2`: anyone who bribed past person `q[i]` moved forward at most 2, so they couldn't have begun before `q[i] − 2`.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewPerson q[i] at index iq[i] - (i+1) > 2 ?YesNoExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Brute Force — Full Inversion Scan
1Hint 1Explore hintHide hint
What does a single bribe do to the final array? It places a larger label in front of a smaller one — an inversion.
2Hint 2Explore hintHide hint
Before counting, guard the impossible case: how far forward can a label legally move, and what label position reveals a violation?
3Hint 3Explore hintHide hint
For each person, count how many larger labels appear before them. Summing those counts gives the total bribes.
A · Core idea
A bribe is an adjacent swap that pushes a bigger label one step forward. So the total number of bribes equals the total number of inversions where a larger label sits in front of a smaller one — but with one twist from the rules.
The chaos check comes first. Person q[i] started at 1-based position q[i] and now sits at 1-based position i + 1. The forward distance travelled is q[i] − (i + 1). Since each person can bribe at most twice, that distance can be at most 2. The instant any person exceeds it, the configuration is unreachable — print Too chaotic and stop. Note the direction: we only care about forward movement, because being pushed backward (a smaller q[i] than its index) is caused by others and is unlimited.
Counting from the bribed person's side. For person q[i], every larger label q[j] with j < i is someone who overtook them — one bribe. Summing over all i counts each bribe exactly once: the bribe that moved a big label past a small one is attributed to the small (bribed) label. Counting from the briber's side double-counts and is fiddly.
Why it's O(n²). The naive count scans all earlier indices for each person. For n = 10⁵ that's ~5 billion comparisons — too slow. The move cap is the lever to fix this.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
q = [2, 1, 5, 3, 4]Array state
person 1 at index 1
2 overtook 1 → +1
3C · Code with teaching comments
Reference implementation previewpublic String minimumBribes(int[] q) { int n = q.length; long bribes = 0; for (int i = 0; i < n; i++) { if (q[i] - (i + 1) > 2) {Explore the full codeHide the full code
D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
Counting bribes from the bribed person's perspective (larger labels in front) avoids the double-counting trap you fall into if you try to tally each briber's two moves directly.
ComplexityO(n²) time, O(1) space — For every index i you scan all j < i looking for larger labels — n(n−1)/2 comparisons, O(n²).
E · Edge cases and pitfalls5q = [1, 2, 3, 4, 5] — Already sorted, zero inversions → 0 bribes.Explore edge casesHide edge cases
Edge cases handled
q = [1, 2, 3, 4, 5]Already sorted, zero inversions → 0 bribes.q = [4, 1, 2, 3]Person 4 moved 4→1 = 3 forward → Too chaotic.
Pitfalls
- Writing q[i] − i > 2 and forgetting the +1 for 1-based positions.
- Counting from the briber's side and double-counting bribes.
- Accepting O(n²) on n = 10⁵ inputs and timing out.
Approach 2 of 2 · Optimal
Windowed Count — Greedy Bound (Optimal)
1Hint 1Explore hintHide hint
If person q[i] was overtaken by someone, how far forward did that someone move? At most 2. So how early could the overtaker have started?
2Hint 2Explore hintHide hint
An overtaker of q[i] can't have a starting position earlier than q[i] − 2 — so don't scan before index max(0, q[i] − 2).
3Hint 3Explore hintHide hint
The inner scan now covers at most a constant-width window per person, so the whole pass is linear.
A · Core idea
Same inversion count, but we exploit the move cap to shrink each person's scan to a tiny window.
Why the window starts at q[i] − 2. Suppose person q[j] (with q[j] > q[i]) is now in front of person q[i] — they overtook them. To get in front of q[i], label q[j] had to move forward, and it can move forward at most 2. Label q[j]'s original position is q[j] > q[i], so the furthest back an overtaker could have started is q[i] − 1… but using the safe, widely-accepted bound, anyone capable of sitting in front of q[i] started no earlier than position q[i] − 2 (1-based), i.e. index q[i] − 2 − 1 in 0-based — we use max(0, q[i] − 2) as the start of the scan to be safe. Scanning from index 0 would re-examine people who could never have overtaken q[i].
Why this stays correct. We're not changing what we count — still 'larger labels in front of q[i]'. We're only skipping a prefix of indices guaranteed to hold no overtaker, because those people started too far back to legally reach in front of q[i] under the 2-move cap.
Why it's O(n). The chaos check already guarantees no one travels forward more than 2. That same cap bounds how many people can crowd in front of any given person to a small constant, so each inner scan is short and the whole algorithm is linear — fast enough for n = 10⁵.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
q = [2, 1, 5, 3, 4]Array state
i=4, q=4
window = indices 2..3; 5 > 4 → +1
3C · Code with teaching comments
D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
The constraint is the algorithm. 'Each person bribes at most twice' isn't flavor text — it's the bound that collapses a global O(n²) inversion count into a local windowed O(n) scan. Whenever a permutation problem caps per-element movement, look for a windowed count.
ComplexityO(n) time, O(1) space — Each person's inner scan covers indices [max(0, q[i]−2), i). Because any overtaker moved forward ≤ 2, the window has bounded width, so total work across all persons is O(n).
E · Edge cases and pitfalls5q with a label exactly 2 ahead — q[i] − (i+1) == 2 is legal; only > 2 is chaotic.Explore edge casesHide edge cases
Edge cases handled
q with a label exactly 2 aheadq[i] − (i+1) == 2 is legal; only > 2 is chaotic.n = 1, q = [1]No inner scan runs → 0 bribes.
Pitfalls
- Starting the window at q[i] − 1 or 0 — one is risky, the other is slow; q[i] − 2 with a max(0, …) clamp is the safe, fast choice.
- Running the chaos check after counting — always guard before you count so a bad input returns early.
- Using int for the bribe accumulator — large n can overflow; use long in Java.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic String minimumBribes(int[] q) { int n = q.length; long bribes = 0; for (int i = 0; i < n; i++) { if (q[i] - (i + 1) > 2) {Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Off-by-one in the chaos check
q[i] is a 1-based label but i is a 0-based index. Comparing q[i] − i misjudges the forward distance by one and reports chaos too late or too early.
Explore the code comparisonHide the code comparison
Off-by-one in the chaos check
q[i] is a 1-based label but i is a 0-based index. Comparing q[i] − i misjudges the forward distance by one and reports chaos too late or too early.
Don't write this
if (q[i] - i > 2) {
return "Too chaotic";
}Write this instead
if (q[i] - (i + 1) > 2) {
return "Too chaotic";
}2Slow full scan on large input
Scanning from index 0 for every person is O(n²); with n up to 10⁵ it times out. Start at max(0, q[i] − 2).
Explore the code comparisonHide the code comparison
Slow full scan on large input
Scanning from index 0 for every person is O(n²); with n up to 10⁵ it times out. Start at max(0, q[i] − 2).
Don't write this
for j in range(i):
if q[j] > q[i]:
bribes += 1Write this instead
for j in range(max(0, q[i] - 2), i):
if q[j] > q[i]:
bribes += 13Integer overflow on the accumulator
Bribe totals can grow large across many inversions; an int can overflow in Java.
Explore the code comparisonHide the code comparison
Integer overflow on the accumulator
Bribe totals can grow large across many inversions; an int can overflow in Java.
Don't write this
int bribes = 0;Write this instead
long bribes = 0;Revise
Carry the pattern into the interview
Pattern to remember
Bounded inversion count with a greedy chaos check
Code pattern to memorize
for i in 0..n-1:
if q[i] - (i + 1) > 2: return "Too chaotic"
bribes += count of j in [max(0, q[i]-2), i) with q[j] > q[i]Rules to remember
- 1Labels are 1-indexed: original position of person
q[i]isq[i], current 1-indexed position isi + 1. - 2'Too chaotic' fires when
q[i] − (i + 1) > 2— a person can move forward at most 2, so being 3+ ahead is impossible. - 3A bribe is counted from the bribed person's view: how many higher labels overtook them and now sit in front.
- 4Start the inner scan at
max(0, q[i] − 2), not0. Anyone who passedq[i]moved forward ≤ 2, so they can't have started earlier thanq[i] − 2. - 5Bribes can only move you forward; a person never moves backward voluntarily, which is why we count larger labels ahead, not behind.
Use this pattern when
- A permutation built by adjacent swaps with a per-element move limit
- You need the minimum number of adjacent swaps to reach a given order
- Counting how far each element drifted from its sorted position, with a cap
Choose another pattern when
- No move cap and you need the exact total adjacent swaps for any permutation → merge-sort inversion count, O(n log n)
- Elements can move both directions freely → this greedy window doesn't apply
- You need the swap sequence itself, not the count → simulate or reconstruct
Interview takeaway
The move cap of 2 turns a global inversion-count problem into a local one: each person can only be overtaken by neighbors who started within 2 positions, so a bounded window gives the count in O(n) instead of O(n²) or O(n log n).
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternBounded inversion counting. A per-element movement cap converts a global O(n²)/O(n log n) inversion count into a local windowed O(n) scan. The chaos check is a greedy feasibility guard derived directly from the cap; the windowed count exploits the same cap.
Practice queueDirect variations and pattern siblings
Direct follow-ups