Rearrange 0 and 1
Ramayana — The Bridge to Lanka — Separating the Boulders
पृथक्त्वं योजनं चैव सेतुबन्धस्य कारणम्। शिलाः क्रमेण स्थापिताः समुद्रे पथि निर्मिताः॥
*Separation and union are both the cause of bridge-building. Stones placed in order create a path across the ocean.*
The Story
The roar of the ocean was deafening, but Nala's voice cut through like a blade. "This is chaos!" he shouted, gesturing at the mountainous pile of boulders the vanara army had gathered. "Look at this mess—floating stones mixed with sinking ones, all jumbled together!"
Hanuman landed beside him, his massive form casting a shadow over the shoreline. "What troubles you, architect? Rama awaits the bridge. Sita languishes in Lanka."
"The stones, Lord Hanuman. The blessed stones float—they bear Rama's name, and the ocean accepts them. But mixed among them are ordinary rocks that will sink and destroy our foundation." Nala pointed to the chaotic pile. "Floating stones are marked 0, sinking ones marked 1. I must separate them: all 0s to the left for the foundation, all 1s to the right to be discarded."
Jambavan, the ancient bear, shuffled forward. "Then separate them, Nala. Pick up each stone, examine it, place it in a new pile."
"That requires a second pile!" Nala exclaimed. "We have no space on this narrow shore. And moving each stone twice wastes precious time. There must be a way to rearrange them in place."
Hanuman's eyes narrowed. "In place? Without creating new piles?"
"Watch," said Nala, crouching before the line of stones. He marked the leftmost position with his left hand and the rightmost with his right. "I will use my two hands as scouts."
The stones were arranged: [1, 0, 1, 0, 0, 1, 0, 1, 1, 0]
"My left hand seeks 1s—stones that don't belong on the left. My right hand seeks 0s—stones that don't belong on the right." His left hand touched the first stone. "A 1. Wrong side." His right hand moved to the last stone. "A 0. Also wrong side. They belong to each other's positions."
With a swift motion, Nala swapped them.
The array became: [0, 0, 1, 0, 0, 1, 0, 1, 1, 1]
"Now my left hand advances until it finds another misplaced 1." His left hand moved past two 0s to find a 1 at position 2. "My right hand retreats until it finds a misplaced 0." His right hand moved left from position 9, past the 1, to find a 0 at position 6.
Another swap: [0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
"Continue until hands meet," Nala said. His left hand moved right, finding 1s. His right hand moved left, finding 0s. Swap after swap, the array organized itself.
When his hands finally crossed, the separation was complete: all 0s on the left, all 1s on the right.
Hanuman stared in wonder. "You touched each stone at most once. You used no extra space."
"Because I let the boundaries do the work," Nala explained. "The left boundary only cares about pushing 1s rightward. The right boundary only cares about pulling 0s leftward. They meet in the middle when all is sorted."
Jambavan stroked his grey muzzle. "But what if there were only 0s? Or only 1s?"
"Then one hand finds nothing to swap, and the other sweeps across harmlessly. The algorithm still works—it simply discovers that no swaps were needed."
That night, the vanara army began the great bridge construction. Nala's separation technique became legend—not just for bridges, but for any time elements must be partitioned into two groups without extra space.
"Remember," Nala told his apprentices, "when you have two categories and must separate them in place, let two pointers approach from opposite ends. One seeks elements that belong on the other side. When both find their targets, swap. When they cross, the deed is done."
This is the Two Pointer technique for rearranging binary elements.
Jambavan's First Instinct
Create a new array, iterate through the original, place 0s first then 1s. This uses O(n) extra space and requires two passes.
void segregateBruteForce(int[] arr) {
// Jambavan's approach: create new piles
int[] sorted = new int[arr.length];
int writePos = 0;
// First pass: collect all 0s
for (int stone : arr) {
if (stone == 0) {
sorted[writePos++] = 0;
}
}
// Second pass: fill remaining with 1s
while (writePos < arr.length) {
sorted[writePos++] = 1;
}
// Copy back to original (wastes more time)
System.arraycopy(sorted, 0, arr, 0, arr.length);
}Nala's Wisdom
void segregate0and1(int[] arr) {
// Nala's left hand: seeking 1s that don't belong
int left = 0;
// Nala's right hand: seeking 0s that don't belong
int right = arr.length - 1;
while (left < right) {
// Left hand advances while it sees 0s (correctly placed)
while (left < right && arr[left] == 0) {
left++;
}
// Right hand retreats while it sees 1s (correctly placed)
while (left < right && arr[right] == 1) {
right--;
}
// If hands haven't crossed, we found a misplaced pair
if (left < right) {
// Swap the misplaced stones
arr[left] = 0;
arr[right] = 1;
left++;
right--;
}
}
}
// Test with Nala's stones
public static void main(String[] args) {
int[] stones = {1, 0, 1, 0, 0, 1, 0, 1, 1, 0};
new Solution().segregate0and1(stones);
System.out.println(Arrays.toString(stones));
// Output: [0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
}Step-by-Step Walkthrough
Array: [1, 0, 1, 0, 0, 1, 0, 1]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Step 1: left=0, right=7
arr[0]=1 (left finds a 1 immediately)
arr[7]=1 (right sees 1, move left)
arr[6]=0 (right finds a 0!)
Swap arr[0] and arr[6]
[1, 0, 1, 0, 0, 1, 0, 1]
L R
↓ swap ↓
[0, 0, 1, 0, 0, 1, 1, 1]
L R
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Step 2: left=1, right=5
arr[1]=0 (left skips)
left=2, arr[2]=1 (left stops)
arr[5]=1 (right skips)
right=4, arr[4]=0 (right stops)
Swap arr[2] and arr[4]
[0, 0, 1, 0, 0, 1, 1, 1]
L R
↓ swap↓
[0, 0, 0, 0, 1, 1, 1, 1]
L R
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Step 3: left=3, right=3
arr[3]=0 (left skips)
left=4, arr[4]=1 (left stops)
But now left(4) > right(3)!
Pointers have crossed → DONE
[0, 0, 0, 0, 1, 1, 1, 1]
LR crossed
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
✅ Result: [0, 0, 0, 0, 1, 1, 1, 1]Deep Insight
**Why does this work?**
The invariant maintained throughout: - All elements before `left` are 0s - All elements after `right` are 1s - Elements between `left` and `right` are yet to be processed
**The partition guarantee:** Every swap places exactly one 0 in its correct region (left side) and exactly one 1 in its correct region (right side). We never undo progress.
**Edge cases:** - All 0s: Right pointer never finds a 0 to swap, left pointer sweeps through - All 1s: Left pointer never finds a 1 to swap initially (wait, it does at position 0!), right pointer sweeps - Single element: Pointers start equal or cross immediately - Already sorted: Minimal swaps (possibly zero)
**Why not use counting sort?** Counting sort (count 0s, overwrite) also works in O(n) time. But the two-pointer approach: 1. Does fewer writes (only swaps, not overwrites) 2. Generalizes to partitioning by any predicate 3. Is stable if implemented carefully
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n) | O(n) | Extra array doubles memory usage |
| Optimal | O(n) | O(1) | In-place with at most n/2 swaps |
Pattern Recognition
✅ Binary partition (two categories: 0/1, even/odd, negative/positive) ✅ In-place requirement (O(1) space) ✅ Rearrangement without changing relative counts ✅ "Segregate" or "partition" mentioned **LeetCode Trigger Phrases:** → "segregate 0s and 1s" → "move all X to one side" → "partition array around pivot"
Bhagavad Gita 13.28
समं सर्वेषु भूतेषु तिष्ठन्तं परमेश्वरम्। विनश्यत्स्वविनश्यन्तं यः पश्यति स पश्यति॥
One who sees the Supreme Lord dwelling equally in all beings, the imperishable within the perishable—that one truly sees.
Connection: Just as the algorithm sees all 0s as equivalent and all 1s as equivalent—not caring about individual stone identities, only their category—the wise see the underlying unity in apparent diversity. The two pointers don't discriminate between one 0 and another; they simply recognize the nature of each element and place it where it belongs.