Minimum Moves to Sort Binary Array (Amazon OA)
Given an array of binary digits, 0 and 1, sort the array so that all zeros are at one end and all ones are at the other. Which end does not matter. To sort the array, swap any two adjacent elements. Determine the minimum number of swaps to sort the array.
Worked Examples
arr = [0, 1, 0, 1]1arr = [1, 1, 1, 1, 0, 0, 0, 0]0arr = [1, 1, 1, 1, 0, 1, 0, 1]3⚖️Formal Constraints & Bounds
1 <= n <= 105arr[i]is in the set{0, 1}
Core Insight
Adjacent swaps change inversion count by unit distance: bubbling an element from reader to writer takes exactly reader - writer moves.
Real-World Scenario & Production Applications
Sorting network packet buffers, minimal-energy bit-shuffling in memory controllers, and quantum gate scheduling where adjacent exchanges have unit cost.
Subproblems & Recurrence Decomposition3 Phases
Skip initial zeros already in place at index 0. For each subsequent 0 discovered at reader, accumulate reader - writer adjacent swaps and advance writer by 1.
zero_left = 0
w = 0
while w < len(arr) and arr[w] == 0: w += 1
for r in range(w, len(arr)):
if arr[r] == 0:
zero_left += r - w
w += 1Step-by-Step Execution Trace Table
| Pass | Reader | arr[reader] | Condition / Action | Writer | Delta (reader - writer) | Cumulative Moves |
|---|---|---|---|---|---|---|
| 0s Left | 4 | 0 | Match! Bubble to writer=0 | 1 | 4 | |
| 0s Left | 6 | 0 | Match! Bubble to writer=1 | 2 | 9 (Total 0s) | |
| 1s Left | 5 | 1 | Match! Bubble to writer=4 | 5 | 1 | |
| 1s Left | 7 | 1 | Match! Bubble to writer=5 | 6 | 3 (Total 1s) | |
| Final | — | — | Return | — | — | 3 |
| 1 | zero_left = ones_left = 0 |
| 2 | w0 = 0 |
| 3 | while w0 < n and arr[w0] == 0: |
| 4 | w0 += 1 |
| 5 | for r in range(w0, n): |
| 6 | if arr[r] == 0: |
| 7 | zero_left += r - w0 |
| 8 | w0 += 1 |
| 9 | w1 = 0 |
| 10 | while w1 < n and arr[w1] == 1: |
| 11 | w1 += 1 |
| 12 | for r in range(w1, n): |
| 13 | if arr[r] == 1: |
| 14 | ones_left += r - w1 |
| 15 | w1 += 1 |
| 16 | return min(zero_left, ones_left) |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Sorting a binary array using only adjacent swaps is equivalent to counting the number of inversions required to separate the 0s and 1s. While general inversion counting on arbitrary sequences requires with a Fenwick tree or Merge Sort, binary elements allow an two-pointer reader-writer technique.
🏟️ The Analogy: The Conveyor Belt Sorter
Picture an inspection belt where items of two categories pass by. You have a target collection dock on the far left. The writer pointer marks the next open slot at the dock. The reader pointer walks down the belt. When it discovers a target item, passing it hand-to-hand back to the dock takes exactly reader - writer adjacent swaps. As the item docks, writer advances by 1.
🔑 Why It Works
Because every adjacent swap exchanges two neighboring items, shifting an item leftwards by 1 position decrements its distance to writer by 1 and shifts every intervening item rightwards by 1 position. The relative order of the intervening items is preserved without increasing their future distances!
Assuming 0s must always go to the left: The problem specifies 'Which end does not matter.' Sorting to [1, 1, ..., 0, 0] may require fewer adjacent swaps than [0, 0, ..., 1, 1]. Always compute both directions and take the minimum.
Resetting writer to 0 instead of maintaining frontier: The writer index marks where the next matching element must land. Each time a target element is shifted, incrementing
writer += 1is mandatory to avoid computing swaps to already-occupied slots.Overcomplicating with Fenwick tree or Merge Sort: Inversion count algorithms for arbitrary values take time and space. Because all values are binary {0, 1}, two-pointer reader-writer simulation solves this in time and space.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Binary digits {0, 1} + adjacent swaps only + move all 0s to one end and 1s to other end.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: arr[0..writer-1] holds compacted target prefix. Next target at reader requires exactly reader - writer adjacent swaps to reach writer.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Assuming 0s must always move left: the prompt states 'which end does not matter', requiring evaluation of both zeros-left and ones-left configurations.
Forgetting to skip leading elements already settled at the destination frontier before beginning reader scan.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"Because only adjacent swaps are allowed, moving a target digit from index reader to index writer across intervening digits takes exactly reader - writer moves. I run two linear passes: one computing swaps to bring all 0s to the left, and one computing swaps to bring all 1s to the left. Returning min(zeros_left, ones_left) runs in
O(N)time andO(1)space."
Complexity & Mathematical Proof
O(N)
Look at the execution steps: The array of length N is traversed twice (once for zeros-left, once for ones-left). Each pass visits each index at most once with O(1) arithmetic. Total time is 2N = O(N).
O(1) Auxiliary
Look at memory allocations: Only integer pointer variables (writer, reader, zero_left_counter, ones_left_counter) are maintained. No auxiliary arrays or recursive stacks are allocated.
T(N) = O(N)
Derivation Progression
Scans array accumulating reader - writer for all 0s.
Scans array accumulating reader - writer for all 1s.
N + N = 2N = O(N)
Strictly linear time with zero dynamic allocation.
Variable Definitions
Length of the binary input array
Memory Architecture & Bounds
O(1) Iterative
O(1) No heap allocation
O(1) Scalar integer return
Boundary Best / Worst Cases
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "binary digits 0 and 1", "swap any two adjacent elements", "all zeros at one end and all ones at the other", "minimum number of swaps". The restriction to adjacent swaps means each move changes the inversion count by exactly 1. Moving a target element from index reader to index writer across adjacent elements requires exactly reader - writer swaps.
, . Requires strictly time and auxiliary space.
Skipping dual-polarity check: the prompt states 'which end does not matter', so evaluating both zeros-to-left and ones-to-left is required to obtain the true minimum.
Minimum Moves to Sort Binary Array (Amazon OA)
Given an array of binary digits, 0 and 1, sort the array so that all zeros are at one end and all ones are at the other. Which end does not matter. To sort the array, swap any two adjacent elements. Determine the minimum number of swaps to sort the array.
Worked Examples
arr = [0, 1, 0, 1]1arr = [1, 1, 1, 1, 0, 0, 0, 0]0arr = [1, 1, 1, 1, 0, 1, 0, 1]3⚖️Formal Constraints & Bounds
1 <= n <= 105arr[i]is in the set{0, 1}
Core Insight
Adjacent swaps change inversion count by unit distance: bubbling an element from reader to writer takes exactly reader - writer moves.
Real-World Scenario & Production Applications
Sorting network packet buffers, minimal-energy bit-shuffling in memory controllers, and quantum gate scheduling where adjacent exchanges have unit cost.
Subproblems & Recurrence Decomposition3 Phases
Skip initial zeros already in place at index 0. For each subsequent 0 discovered at reader, accumulate reader - writer adjacent swaps and advance writer by 1.
zero_left = 0
w = 0
while w < len(arr) and arr[w] == 0: w += 1
for r in range(w, len(arr)):
if arr[r] == 0:
zero_left += r - w
w += 1Step-by-Step Execution Trace Table
| Pass | Reader | arr[reader] | Condition / Action | Writer | Delta (reader - writer) | Cumulative Moves |
|---|---|---|---|---|---|---|
| 0s Left | 4 | 0 | Match! Bubble to writer=0 | 1 | 4 | |
| 0s Left | 6 | 0 | Match! Bubble to writer=1 | 2 | 9 (Total 0s) | |
| 1s Left | 5 | 1 | Match! Bubble to writer=4 | 5 | 1 | |
| 1s Left | 7 | 1 | Match! Bubble to writer=5 | 6 | 3 (Total 1s) | |
| Final | — | — | Return | — | — | 3 |
| 1 | zero_left = ones_left = 0 |
| 2 | w0 = 0 |
| 3 | while w0 < n and arr[w0] == 0: |
| 4 | w0 += 1 |
| 5 | for r in range(w0, n): |
| 6 | if arr[r] == 0: |
| 7 | zero_left += r - w0 |
| 8 | w0 += 1 |
| 9 | w1 = 0 |
| 10 | while w1 < n and arr[w1] == 1: |
| 11 | w1 += 1 |
| 12 | for r in range(w1, n): |
| 13 | if arr[r] == 1: |
| 14 | ones_left += r - w1 |
| 15 | w1 += 1 |
| 16 | return min(zero_left, ones_left) |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Sorting a binary array using only adjacent swaps is equivalent to counting the number of inversions required to separate the 0s and 1s. While general inversion counting on arbitrary sequences requires with a Fenwick tree or Merge Sort, binary elements allow an two-pointer reader-writer technique.
🏟️ The Analogy: The Conveyor Belt Sorter
Picture an inspection belt where items of two categories pass by. You have a target collection dock on the far left. The writer pointer marks the next open slot at the dock. The reader pointer walks down the belt. When it discovers a target item, passing it hand-to-hand back to the dock takes exactly reader - writer adjacent swaps. As the item docks, writer advances by 1.
🔑 Why It Works
Because every adjacent swap exchanges two neighboring items, shifting an item leftwards by 1 position decrements its distance to writer by 1 and shifts every intervening item rightwards by 1 position. The relative order of the intervening items is preserved without increasing their future distances!
Assuming 0s must always go to the left: The problem specifies 'Which end does not matter.' Sorting to [1, 1, ..., 0, 0] may require fewer adjacent swaps than [0, 0, ..., 1, 1]. Always compute both directions and take the minimum.
Resetting writer to 0 instead of maintaining frontier: The writer index marks where the next matching element must land. Each time a target element is shifted, incrementing
writer += 1is mandatory to avoid computing swaps to already-occupied slots.Overcomplicating with Fenwick tree or Merge Sort: Inversion count algorithms for arbitrary values take time and space. Because all values are binary {0, 1}, two-pointer reader-writer simulation solves this in time and space.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Binary digits {0, 1} + adjacent swaps only + move all 0s to one end and 1s to other end.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: arr[0..writer-1] holds compacted target prefix. Next target at reader requires exactly reader - writer adjacent swaps to reach writer.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Assuming 0s must always move left: the prompt states 'which end does not matter', requiring evaluation of both zeros-left and ones-left configurations.
Forgetting to skip leading elements already settled at the destination frontier before beginning reader scan.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"Because only adjacent swaps are allowed, moving a target digit from index reader to index writer across intervening digits takes exactly reader - writer moves. I run two linear passes: one computing swaps to bring all 0s to the left, and one computing swaps to bring all 1s to the left. Returning min(zeros_left, ones_left) runs in
O(N)time andO(1)space."
Complexity & Mathematical Proof
O(N)
Look at the execution steps: The array of length N is traversed twice (once for zeros-left, once for ones-left). Each pass visits each index at most once with O(1) arithmetic. Total time is 2N = O(N).
O(1) Auxiliary
Look at memory allocations: Only integer pointer variables (writer, reader, zero_left_counter, ones_left_counter) are maintained. No auxiliary arrays or recursive stacks are allocated.
T(N) = O(N)
Derivation Progression
Scans array accumulating reader - writer for all 0s.
Scans array accumulating reader - writer for all 1s.
N + N = 2N = O(N)
Strictly linear time with zero dynamic allocation.
Variable Definitions
Length of the binary input array
Memory Architecture & Bounds
O(1) Iterative
O(1) No heap allocation
O(1) Scalar integer return
Boundary Best / Worst Cases
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "binary digits 0 and 1", "swap any two adjacent elements", "all zeros at one end and all ones at the other", "minimum number of swaps". The restriction to adjacent swaps means each move changes the inversion count by exactly 1. Moving a target element from index reader to index writer across adjacent elements requires exactly reader - writer swaps.
, . Requires strictly time and auxiliary space.
Skipping dual-polarity check: the prompt states 'which end does not matter', so evaluating both zeros-to-left and ones-to-left is required to obtain the true minimum.