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. You are given a sorted array of integers and a quadratic function f(x) = ax² + bx + c. You need to return a sorted array of the values f(x) applied to each element x in the input array. Which approach guarantees an optimal O(n) time solution?

easy

A. Use two pointers at the start and end of the input array and fill the output array from the end or start depending on the sign of a, leveraging the parabola shape.

B. Use dynamic programming to store intermediate results and build the sorted transformed array incrementally.

C. Apply the quadratic function to each element and then sort the resulting array using a standard sorting algorithm.

D. Use a max-heap to insert transformed values and then extract them in sorted order.

Solution

1. Step 1: Understand the parabola shape

   The quadratic function forms a parabola. If a >= 0, the largest values are at the ends of the input array; if a < 0, the smallest values are at the ends.

2. Step 2: Use two pointers to fill output

   By comparing transformed values at both ends, we can fill the output array from the appropriate end in O(n) time without sorting.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two pointers leverage sorted input and parabola shape for linear time [OK]

Hint: Two pointers exploit parabola shape for O(n) [OK]

Common Mistakes:

• Assuming sorting is always needed after transformation
• Trying DP without leveraging input order

2. Consider the following buggy code snippet for finding missing ranges. Which line contains the subtle bug that causes missing ranges at the start of the interval to be ignored?

medium

A. Line with condition 'if pointer <= curr:' should be 'if pointer < curr:'

B. Line updating pointer to 'curr + 1' should be 'curr' instead

C. Line checking 'if idx == len(nums):' should check 'if idx > len(nums):'

D. Line appending missing range should format single numbers as 'start->end' always

Solution

1. Step 1: Identify condition for missing range detection

   The condition 'if pointer <= curr:' incorrectly includes the case pointer == curr, causing no gap detection before first element if pointer equals first number.

2. Step 2: Correct condition to 'if pointer < curr:'

   This ensures missing ranges are detected only when pointer is strictly less than current number, capturing missing numbers before first element.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing to '<' fixes missing start ranges [OK]

Hint: Check strict inequality when detecting gaps [OK]

Common Mistakes:

• Using <= instead of <
• Incorrect pointer update
• Wrong formatting of single numbers

3. Suppose the input array can contain negative integers and duplicates, and you want to find the maximum gap between successive unique elements in sorted order. Which modification to the bucket sort / pigeonhole approach correctly handles this scenario without sorting the entire array explicitly?

hard

A. Sort the array fully to handle negatives and duplicates, then scan for maximum gap.

B. Use buckets sized to cover only positive numbers and skip negatives during bucketing.

C. Ignore duplicates by using a set before bucketing, then apply the standard bucket approach on unique values.

D. Modify bucket size to be the difference between max and min ignoring duplicates, but keep duplicates in buckets.

Solution

1. Step 1: Handle duplicates

   Duplicates do not affect maximum gap between unique elements, so remove duplicates first.

2. Step 2: Apply bucket approach on unique values

   After deduplication, apply pigeonhole principle buckets over full range including negatives.

3. Step 3: Avoid sorting entire array

   This approach avoids full sorting and correctly handles negatives and duplicates.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Deduplication before bucketing preserves correctness [OK]

Hint: Remove duplicates first, then bucket over full range including negatives [OK]

Common Mistakes:

• Ignoring negatives in bucket sizing
• Keeping duplicates causing incorrect gaps
• Sorting entire array defeats bucket approach

4. Suppose the input array can contain duplicate elements and negative numbers. Which modification to the optimal approach ensures correct minimum absolute difference calculation?

hard

A. Sort the array and scan adjacent pairs, but use absolute difference instead of subtraction.

B. Sort the array and scan adjacent pairs using subtraction as is, since sorting orders negatives correctly.

C. Use nested loops to compare all pairs because sorting fails with negatives.

D. Ignore duplicates and negatives since they don't affect minimum difference.

Solution

1. Step 1: Understand sorting with negatives

   Sorting places negative numbers in ascending order correctly.

2. Step 2: Adjacent subtraction works for minimum difference

   Difference between adjacent sorted elements is always non-negative or zero; no need for absolute value.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sorting handles negatives; subtraction suffices [OK]

Hint: Sorting handles negatives; no abs needed on adjacent pairs [OK]

Common Mistakes:

• Using abs unnecessarily
• Thinking sorting fails with negatives

5. Suppose the problem is modified so that time points can repeat multiple times and you want to find the minimum difference between any two occurrences, but the input size is very large (up to 10^7). Which approach is best suited to handle this efficiently?

hard

A. Use the brute force nested loops approach to check all pairs for minimum difference.

B. Use the bucket sort approach with a boolean array to detect duplicates and find minimum difference in O(n) time.

C. Use a hash map to count occurrences and then sort unique times to find minimum difference.

D. Use a balanced binary search tree to insert times and find minimum difference on the fly.

Solution

1. Step 1: Consider input size and duplicates

   With up to 10^7 times and possible duplicates, brute force is infeasible.

2. Step 2: Bucket sort with boolean array is optimal

   Using a fixed-size 1440-length boolean array detects duplicates instantly and scans once for minimum difference in O(n) time.

3. Step 3: Other approaches are less efficient

   Sorting or balanced trees add overhead and cannot beat fixed-size bucket scanning for this problem.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Bucket sort approach handles large inputs and duplicates efficiently [OK]

Hint: Fixed 1440 bucket array handles duplicates and large inputs efficiently [OK]

Common Mistakes:

• Trying brute force on large inputs
• Sorting large inputs with duplicates is costly
• Using trees adds unnecessary overhead