Sort Colors (Dutch National Flag)

▶

Steps

setup

Initialize pointers

Set low and mid to 0, and high to the last index (5). The array is unsorted initially.

💡 Starting pointers define the boundaries for sorting: low and mid at the start, high at the end.

Line:

low, mid, high = 0, 0, len(nums) - 1

💡 Pointers mark the start of the unsorted region and boundaries for 0s and 2s.

compare

nums[mid] is 2, swap with nums[high]

nums[mid] is 2, so swap nums[mid] and nums[high]. Then decrement high.

💡 Swapping 2 to the end groups all blues at the right side.

Line:

if nums[mid] == 2:
    nums[mid], nums[high] = nums[high], nums[mid]
    high -= 1

💡 2s belong at the end, so we move them there immediately.

compare

nums[mid] is 0, swap with nums[low]

Now nums[mid] is 0, so swap nums[mid] and nums[low]. Increment low and mid.

💡 0s belong at the start, so we move them there and expand the 0s region.

Line:

if nums[mid] == 0:
    nums[low], nums[mid] = nums[mid], nums[low]
    low += 1
    mid += 1

💡 Swapping 0s forward builds the sorted 0s section at the front.

compare

nums[mid] is 2, swap with nums[high]

nums[mid] is 2 again, swap with nums[high] and decrement high.

💡 Move 2s to the right side to keep them grouped.

Line:

if nums[mid] == 2:
    nums[mid], nums[high] = nums[high], nums[mid]
    high -= 1

💡 2s are pushed to the end, shrinking the unsorted region.

compare

nums[mid] is 1, increment mid

nums[mid] is 1, so just increment mid to continue scanning.

💡 1s are in the middle, so no swap needed, just move forward.

Line:

elif nums[mid] == 1:
    mid += 1

💡 1s are naturally placed between 0s and 2s, so no action needed.

compare

nums[mid] is 1, increment mid

nums[mid] is 1 again, increment mid to continue scanning.

💡 Continue passing over 1s as they are already in correct position.

Line:

elif nums[mid] == 1:
    mid += 1

💡 1s do not require swaps, simplifying the process.

compare

nums[mid] is 1, increment mid

nums[mid] is 1, increment mid to move past the last 1.

💡 Mid pointer moves forward to finish scanning the unsorted region.

Line:

elif nums[mid] == 1:
    mid += 1

💡 All 1s are now confirmed in place.

traverse

Loop ends as mid > high

Mid pointer has passed high pointer, so the array is fully sorted.

💡 The condition mid <= high controls the loop; when false, sorting is complete.

Line:

while mid <= high:

💡 All elements are partitioned correctly into 0s, 1s, and 2s.

reconstruct

Final sorted array

The array is now sorted with all 0s, then 1s, then 2s in order.

💡 The algorithm completes in one pass with no extra space.

Line:

print(arr)

💡 The final array confirms the correctness of the sorting process.

finalize

Confirm final pointer positions

Pointers low, mid, and high have final positions after sorting completes.

💡 Understanding final pointer positions helps confirm the partition boundaries.

Line:

N/A

💡 Low points just after last 0, mid points just after last scanned element, high points just before first 2 region.

def sortColors(nums):
    low, mid, high = 0, 0, len(nums) - 1  # STEP 1
    while mid <= high:  # STEP 8
        if nums[mid] == 0:  # STEP 3
            nums[low], nums[mid] = nums[mid], nums[low]  # STEP 3
            low += 1  # STEP 3
            mid += 1  # STEP 3
        elif nums[mid] == 1:  # STEP 5,6,7
            mid += 1  # STEP 5,6,7
        else:  # nums[mid] == 2  # STEP 2,4
            nums[mid], nums[high] = nums[high], nums[mid]  # STEP 2,4
            high -= 1  # STEP 2,4

if __name__ == '__main__':
    arr = [2,0,2,1,1,0]
    sortColors(arr)
    print(arr)  # STEP 9

📊

Sort Colors (Dutch National Flag) - Watch the Algorithm Execute, Step by Step

Watching each pointer move and swap helps you understand how the algorithm partitions the array into three sections for 0s, 1s, and 2s without extra space.

setup

mid

2

0

0

1

2

2

1

3

1

4

high

0

5

swap

mid

0

0

0

1

2

2

1

3

high

1

4

2

5

swap

0

0

mid

0

1

2

2

1

3

high

1

4

2

5

swap

0

0

mid

0

1

1

2

high

1

3

2

4

2

5

move_right

0

0

low

0

1

mid

1

2

high

1

3

2

4

2

5

move_right

0

0

low

0

1

1

2

high

1

3

2

4

2

5

move_right

0

0

low

0

1

1

2

high

1

3

mid

2

4

2

5

traverse

0

0

low

0

1

1

2

high

1

3

mid

2

4

2

5

Result: [0,0,1,1,2,2]

record

0

0

low

0

1

1

2

high

1

3

mid

2

4

2

5

Result: [0,0,1,1,2,2]

finalize

0

0

0

1

low

1

2

high

1

3

2

4

2

5

Result: [0,0,1,1,2,2]

Key Takeaways

✓ The algorithm partitions the array into three regions using three pointers in one pass.

This is hard to see from code alone because the pointers move in a non-linear way and swaps happen conditionally.

✓ 0s are moved forward by swapping with low pointer, 2s are moved backward by swapping with high pointer, and 1s are skipped.

Visualizing the swaps and pointer increments clarifies why 1s require no action.

✓ When a 2 is swapped from mid to high, mid does not increment immediately to re-check the swapped element.

This subtlety ensures no elements are skipped and is easier to understand when watching the trace.

Practice

1. Consider the following code snippet that partitions an array by parity in-place. What is the value of insertPos after the loop completes when the input is [3, 1, 2, 4]?

easy

A. 3

B. 2

C. 4

D. 1

Solution

1. Step 1: Trace insertPos updates

   Initially insertPos=0. Iteration i=0: nums[0]=3 (odd), no change. i=1: nums[1]=1 (odd), no change. i=2: nums[2]=2 (even), swap nums[2] and nums[0], insertPos=1. i=3: nums[3]=4 (even), swap nums[3] and nums[1], insertPos=2.

2. Step 2: Final value of insertPos

   After loop, insertPos=2 because two even numbers were placed at front.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two evens found, insertPos increments twice [OK]

Hint: insertPos increments once per even element [OK]

Common Mistakes:

• Counting odd elements as increments
• Off-by-one errors in insertPos after last iteration
• Confusing insertPos with current index i

2. Consider the following buggy code for merging two sorted arrays in-place. Which line contains the subtle bug that causes missing elements in the final merged array?

def merge(nums1, m, nums2, n):
    i = m - 1
    j = n - 1
    k = m + n - 1
    while i >= 0 and j >= 0:
        if nums1[i] > nums2[j]:
            nums1[k] = nums1[i]
            i -= 1
        else:
            nums1[k] = nums2[j]
            j -= 1
        k -= 1
    # Missing copying remaining nums2 elements

nums1 = [1,2,3,0,0,0]
m = 3
nums2 = [2,5,6]
n = 3
merge(nums1, m, nums2, n)
print(nums1)

medium

A. Line 12: Missing while loop to copy remaining nums2 elements

B. Line 9: nums1[k] = nums2[j]

C. Line 4: i = m - 1

D. Line 7: if nums1[i] > nums2[j]:

Solution

1. Step 1: Analyze the main merging loop

   The main loop merges elements from the back correctly but stops when either i or j is negative.

2. Step 2: Identify missing step

   There is no loop copying remaining elements from nums2 if any remain, causing missing elements in nums1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Without copying leftover nums2 elements, final array is incomplete [OK]

Hint: Always copy leftover nums2 elements after main loop [OK]

Common Mistakes:

• Forgetting leftover nums2 copy
• Overwriting nums1 elements too early

3. What is the space complexity of the recursive two-pointer approach to reverse a string of length n, and why might some candidates incorrectly think it is O(1)?

medium

A. O(1) because the swaps are done in-place without extra arrays.

B. O(log n) because recursion divides the problem in half each call.

C. O(n) because the recursion stack can grow up to n/2 calls.

D. O(n) because a new array is created to hold reversed characters.

Solution

1. Step 1: Analyze recursion stack usage

   Each recursive call processes one pair of characters, so maximum recursion depth is about n/2, leading to O(n) stack space.

2. Step 2: Understand why O(1) is incorrect

   Although swaps are in-place, recursion adds call frames on the stack, which consume O(n) space.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Recursion stack depth proportional to input size, so space is O(n) [OK]

Hint: Recursion stack adds O(n) space despite in-place swaps [OK]

Common Mistakes:

• Ignoring recursion stack space
• Confusing in-place with constant space
• Assuming recursion halves problem size each call

4. Suppose the 3Sum problem is modified so that elements can be reused multiple times in a triplet (e.g., triplet [0,0,0] is valid if zeros exist). Which modification to the optimal hash set approach correctly handles this variant?

hard

A. Remove the duplicate skipping for fixed element i and inner pointer j, allowing repeated elements.

B. Use three nested loops to allow repeated indices and check sums directly.

C. Keep the same code but remove the sorting step to allow duplicates naturally.

D. Modify the hash set approach to not skip duplicates and allow complement to be equal to nums[j].

Solution

1. Step 1: Understand reuse means duplicates allowed in triplets

   Allowing reuse means complement can be equal to nums[j], so skipping duplicates must be adjusted.

2. Step 2: Modify hash set approach accordingly

   Do not skip duplicates; allow complement == nums[j]; sorting still needed to avoid unordered duplicates.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Allowing complement == nums[j] and no skipping duplicates handles reuse correctly [OK]

Hint: Allow complement == nums[j] and no skipping duplicates for reuse [OK]

Common Mistakes:

• Removing sorting breaks uniqueness
• Using triple loops is inefficient
• Removing duplicate skipping blindly causes duplicates

5. Suppose the problem is modified so that you can reuse the same line multiple times to form containers (i.e., pairs can include the same index twice). Which of the following statements about adapting the two-pointer approach is correct?

hard

A. The two-pointer approach still works without changes because pointers can point to the same index.

B. The problem reduces to finding the maximum height line squared, so just return height[i] * 0 for some i.

C. A new approach is needed because the two-pointer method relies on distinct indices and cannot handle reuse.

D. You must switch to a brute force approach checking all pairs including identical indices to handle reuse.

Solution

1. Step 1: Understand reuse implication

   Allowing reuse means pairs can be (i, i), which the original two-pointer approach does not consider.

2. Step 2: Analyze two-pointer limitations

   The two-pointer method relies on distinct indices moving inward; it cannot handle pairs with the same index, so it must be modified or replaced.

3. Step 3: Evaluate options

   Brute force can handle reuse but is inefficient; simply returning height[i]*0 is incorrect; two-pointer without changes fails.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Two-pointer requires distinct indices -> reuse breaks original approach [OK]

Hint: Two-pointer needs distinct indices; reuse breaks this assumption [OK]

Common Mistakes:

• Assuming two-pointer works unchanged
• Ignoring reuse pairs with same index
• Thinking reuse reduces problem complexity