Sort Colors (Dutch National Flag)

📋

Problem

Imagine you are organizing colored balls in a line, and you want all red balls first, then white, then blue - just like the Dutch flag's colors.

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue. We will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively. Input: An integer array nums of length n where each element is 0, 1, or 2. Output: The same array nums sorted in-place with all 0s first, then all 1s, then all 2s.

1 ≤ n ≤ 10^5nums[i] ∈ {0, 1, 2} for all valid i

Edge cases: All elements are the same color → array remains unchangedArray of length 1 → no sorting neededArray with only two colors present → sort those two correctly

</>

IDE

def sortColors(nums: list[int]) -> None:public void sortColors(int[] nums)void sortColors(vector<int>& nums)function sortColors(nums)

def sortColors(nums):
    # Write your solution here
    pass

class Solution {
    public void sortColors(int[] nums) {
        // Write your solution here
    }
}

#include <vector>
using namespace std;

void sortColors(vector<int>& nums) {
    // Write your solution here
}

function sortColors(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [0,1,2,2,1,0]Incorrect swapping logic causing some elements to remain unsorted.✅ Implement the three-pointer Dutch National Flag algorithm with careful pointer updates after each swap.

Wrong: [2,2,2,1,1,1]Greedy approach that only moves 0s to front but does not sort 1s and 2s properly.✅ Use a full three-way partitioning approach instead of partial sorting.

Wrong: [0,0,0,0,0]Code crashes or modifies empty input or single-element arrays incorrectly.✅ Add guard clauses for empty and single-element arrays to avoid unnecessary operations.

Wrong: [0,0,1,1,2,2,2]Off-by-one errors causing extra elements or missing swaps.✅ Carefully update pointers and loop conditions to cover all elements exactly once.

✓

Test Cases

Focus on handling small and empty inputs correctly before moving on.

Review your pointer updates and swapping logic to avoid partial sorting.

Ensure your solution is linear time to handle large inputs efficiently.

t1_01basic

Input{"nums":[0,0,1,1,2,2]}

Expectednull

⏱ Performance - must finish in 2000ms

After sorting, all 0s come first, then 1s, then 2s, preserving the order of colors.

💡 Think about partitioning the array into three parts for 0, 1, and 2.

💡 Use the Dutch National Flag algorithm with three pointers to sort in one pass.

💡 Maintain pointers for next positions of 0 and 2, swap elements accordingly.

Why it failed: Basic case failed - likely incorrect partitioning or swapping logic. Fix by correctly implementing the three-pointer approach ensuring all 0s before 1s and all 2s after 1s.

✓ Core logic for three-way partitioning is correct.

t1_02basic

Input{"nums":[0,0,1,1,2,2]}

Expectednull

⏱ Performance - must finish in 2000ms

Sorting the array places all 0s first, then 1s, then 2s.

💡 Count occurrences of each color or use pointers to reorder in-place.

💡 Check boundary conditions when swapping elements between partitions.

💡 Ensure no elements are skipped or overwritten during swaps.

Why it failed: Basic case failed - possibly missed updating pointers after swaps. Fix by carefully updating pointers after each swap to maintain correct partitions.

✓ Correctly handles mixed order with multiple occurrences.

t2_01edge

Input{"nums":[]}

Expectednull

⏱ Performance - must finish in 2000ms

Empty array remains unchanged.

💡 Consider what happens when the input array is empty.

💡 Your code should handle n=0 without errors or changes.

💡 Add a condition to return immediately if array length is zero.

Why it failed: Edge case failed - code crashes or modifies empty input. Fix by adding a guard clause for empty arrays.

✓ Handles empty input gracefully.

t2_02edge

Input{"nums":[1]}

Expectednull

⏱ Performance - must finish in 2000ms

Single element array requires no sorting.

💡 Check behavior when array length is one.

💡 No swaps or changes should be made for single-element arrays.

💡 Ensure your loop conditions handle small arrays correctly.

Why it failed: Edge case failed - code incorrectly modifies or crashes on single element. Fix by ensuring loops handle n=1 correctly.

✓ Correctly handles single-element arrays.

t2_03edge

Input{"nums":[0,0,0,0,0]}

Expectednull

⏱ Performance - must finish in 2000ms

All elements are the same color; array remains unchanged.

💡 Test arrays where all elements are identical.

💡 Your algorithm should recognize no swaps are needed.

💡 Verify that your pointers do not cause unnecessary swaps.

Why it failed: Edge case failed - unnecessary swaps or pointer errors on uniform arrays. Fix by ensuring no swaps occur when elements are already in correct partition.

✓ Efficiently handles uniform color arrays.

t3_01corner

Input{"nums":[0,0,1,1,2,2]}

Expectednull

⏱ Performance - must finish in 2000ms

Array with colors in reverse order tests correct full partitioning.

💡 Beware of greedy approaches that only partially sort the array.

💡 Use the three-pointer approach to correctly reorder all colors in one pass.

💡 Swap elements carefully to avoid leaving any color misplaced.

Why it failed: Corner case failed - greedy partial sorting leaves some elements unsorted. Fix by implementing full three-way partitioning with correct pointer updates.

✓ Correctly sorts reverse ordered colors.

t3_02corner

Input{"nums":[0,0,0,1,1,1,2,2,2]}

Expectednull

⏱ Performance - must finish in 2000ms

Mixed array tests correct handling of multiple swaps and pointer movements.

💡 Check that your algorithm does not confuse 0/1/2 boundaries.

💡 Ensure that each swap moves elements closer to their correct partition.

💡 Update pointers after each swap to maintain partition integrity.

Why it failed: Corner case failed - off-by-one errors or pointer mismanagement cause incorrect final order. Fix by carefully updating pointers after swaps.

✓ Handles complex mixed inputs correctly.

t3_03corner

Input{"nums":[0,0,0,0,1,1,1,1]}

Expectednull

⏱ Performance - must finish in 2000ms

Array with only two colors tests correct partitioning without 2s.

💡 Your algorithm should handle arrays missing one color gracefully.

💡 Verify that the absence of 2s does not break pointer logic.

💡 Partition 0s and 1s correctly even if 2s are absent.

Why it failed: Corner case failed - code assumes presence of all three colors causing pointer errors. Fix by handling missing colors in pointer logic.

✓ Correctly partitions arrays with two colors.

t4_01performance

Input{"nums":[0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0]}

Expectednull

⏱ Performance - must finish in 2000ms

Large input with n=100 to test O(n) time complexity; must complete within 2 seconds.

💡 Use an O(n) one-pass algorithm to avoid timeouts.

💡 Avoid nested loops or sorting algorithms with higher complexity.

💡 Implement the Dutch National Flag algorithm with three pointers.

Why it failed: Performance test failed - algorithm exceeds time limit due to O(n^2) or higher complexity. Fix by using the one-pass three-pointer approach.

✓ Algorithm runs within time limits confirming O(n) complexity.

Practice

1. Given the following code snippet, what is the output when calling two_sum_binary_search([1,3,5,7], 8)?

easy

A. [1, 4]

B. [3, 4]

C. [1, 3]

D. [2, 3]

Solution

1. Step 1: Trace first iteration with i=0 (numbers[i]=1)

   Complement = 8 - 1 = 7; binary_search searches indices 1 to 3 for 7; finds at index 3.

2. Step 2: Return indices 1-based: i+1=1, j+1=4

   Returns [1, 4]. No further iterations needed.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Complement found at last index, output matches [1,4] [OK]

Hint: Trace binary search complement index carefully [OK]

Common Mistakes:

• Off-by-one in indices
• Wrong complement calculation
• Misunderstanding binary search bounds

2. What is the time complexity of the in-place two-pointer partition algorithm for partitioning an array by parity, and why?

medium

A. O(n) because each element is visited once and swapped at most once

B. O(n log n) because of the swaps involved

C. O(n^2) because swapping elements inside the loop can be costly

D. O(n) but with O(n) auxiliary space due to recursion stack

Solution

1. Step 1: Analyze loop iterations

   The algorithm iterates over the array once, visiting each element exactly once.

2. Step 2: Analyze swaps and space

   Swaps occur only when an even element is found, at most once per element. No recursion or extra space is used.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass with constant swaps -> O(n) time and O(1) space [OK]

Hint: Single pass with constant swaps -> O(n) time [OK]

Common Mistakes:

• Assuming swaps cause O(n^2) complexity
• Confusing with sorting complexity O(n log n)
• Thinking recursion or extra space is involved

3. 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

4. Suppose now the second array nums2 can contain negative numbers and the first array nums1 has no extra space at the end. Which of the following approaches correctly merges nums2 into nums1 while maintaining sorted order?

hard

A. Create a new array of size m+n, merge nums1 and nums2 into it, then copy back to nums1.

B. Use the two-pointer backward in-place merge as before, ignoring extra space constraints.

C. Sort nums1 and nums2 separately, then concatenate and sort the combined array.

D. Use a two-pointer forward approach merging into nums1 in-place without extra space.

Solution

1. Step 1: Understand constraints

   nums1 has no extra space at the end, so in-place backward merge is impossible.

2. Step 2: Identify correct approach

   Using extra space to merge into a new array and then copying back is necessary to maintain sorted order.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Extra space is required when nums1 lacks buffer space [OK]

Hint: No extra space in nums1 means new array needed [OK]

Common Mistakes:

• Trying in-place merge without space
• Sorting combined array wastes time

5. Suppose the input array can contain negative integers and zeros, and you want to partition the array so that all even numbers (including negative evens and zero) come before all odd numbers. Which modification to the original two-pointer algorithm is necessary to handle this correctly?

hard

A. Change the parity check to use abs(nums[i]) % 2 == 0 to handle negative numbers

B. Use a sorting-based approach since parity is ambiguous with negative numbers

C. No change needed; the original parity check nums[i] % 2 == 0 works correctly for negatives and zero

D. Add a separate pass to move zeros to the front before partitioning evens and odds

Solution

1. Step 1: Understand parity with negatives and zero

   In Python, num % 2 == 0 correctly identifies even numbers including negatives and zero.

2. Step 2: Confirm no algorithm change needed

   The original two-pointer approach works unchanged since parity check is valid for all integers.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Modulo operator handles negative evens and zero correctly [OK]

Hint: Modulo operator works for negative evens and zero [OK]

Common Mistakes:

• Thinking abs() is needed for parity check
• Assuming zeros need special handling
• Believing sorting is required for negatives