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. Consider the following code snippet implementing the 3Sum problem. What is the final returned list when the input is [-1, 0, 1]?

easy

A. []

B. [[0, 1, -1]]

C. [[-1, 0, 1]]

D. [[-1, -1, 2]]

Solution

1. Step 1: Sort input and initialize

   Sorted input is [-1, 0, 1]. Start with i=0 (nums[i]=-1), seen = {}.

2. Step 2: Iterate j and check complements

   j=1 (nums[j]=0), complement=1. 1 not in seen, add 0 to seen. j=2 (nums[j]=1), complement=0 in seen -> triplet [-1,0,1] added.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Triplet [-1,0,1] found correctly [OK]

Hint: Sorted input and complement check find correct triplet [OK]

Common Mistakes:

• Confusing order of triplet
• Missing complement in seen
• Off-by-one in loops

2. You are given an array representing heights of vertical lines on the x-axis. You want to find two lines that together with the x-axis form a container, such that the container holds the maximum amount of water. Which algorithmic approach guarantees finding the optimal solution in O(n) time?

easy

A. Two pointers starting at opposite ends, moving the pointer at the shorter line inward.

B. Brute force by checking all pairs of lines and calculating their container area.

C. Dynamic programming to store maximum areas for subproblems of line pairs.

D. Greedy approach moving the pointer at the taller line inward to maximize area.

Solution

1. Step 1: Understand problem constraints

   The problem requires finding two lines that maximize the container area, which depends on the minimum height and the distance between lines.

2. Step 2: Analyze algorithmic approaches

   Brute force (checking all pairs) is O(n²), dynamic programming is unnecessary and inefficient here, and moving the pointer at the taller line can miss optimal solutions. The two-pointer approach moving the pointer at the shorter line inward guarantees checking all promising pairs efficiently in O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two-pointer approach with shorter line pointer movement -> O(n) optimal [OK]

Hint: Two pointers move inward from ends, shorter line pointer moves [OK]

Common Mistakes:

• Moving pointer at taller line instead of shorter line
• Using DP unnecessarily
• Assuming greedy on taller line pointer works

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

4. Consider the following Python code that reverses a list of characters recursively using two pointers. What will be the final output printed by the program?

def reverseString(s):
    def helper(left, right):
        if left >= right:
            return
        s[left], s[right] = s[right], s[left]
        helper(left + 1, right - 1)

if __name__ == "__main__":
    s = ['a', 'b', 'c', 'd']
    reverseString(s)
    print(s)

easy

A. ['d', 'b', 'c', 'a']

B. ['d', 'c', 'b', 'a']

C. ['a', 'b', 'c', 'd']

D. ['c', 'b', 'a', 'd']

Solution

1. Step 1: Trace helper calls and swaps

   Initial call helper(0,3): swap s[0] and s[3] -> ['d','b','c','a'] Next call helper(1,2): swap s[1] and s[2] -> ['d','c','b','a'] Next call helper(2,1): left >= right, stop recursion.

2. Step 2: Final array state

   The array after all swaps is ['d','c','b','a'], which is the reversed input.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   All pairs swapped correctly, final reversed array matches ['d', 'c', 'b', 'a'] [OK]

Hint: Recursive swaps from ends reverse array correctly [OK]

Common Mistakes:

• Off-by-one errors in recursion base case
• Swapping wrong indices
• Not swapping at all

5. If the input array can contain negative heights (representing below ground level), which modification to the two pointers approach is necessary to correctly compute trapped water?

hard

A. Adjust max height updates to consider negative values and allow water to be trapped below zero level.

B. Ignore negative heights as they cannot trap water and run original algorithm unchanged.

C. Use prefix and suffix max arrays instead of two pointers to handle negative heights.

D. Add an offset to all heights to make them non-negative before running the original two pointers algorithm.

Solution

1. Step 1: Understand negative heights impact

   Negative heights mean bars can be below zero, so trapped water can be below ground level.

2. Step 2: Modify max updates

   Max heights must track actual maximums including negatives, and water calculation must allow negative values to accumulate trapped water correctly.

3. Step 3: Why other options fail

   Ignoring negatives misses trapped water; prefix/suffix arrays don't inherently solve negative values; offsetting changes relative heights and can distort results.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Max updates must handle negatives to compute trapped water correctly [OK]

Hint: Max updates must handle negative heights properly [OK]

Common Mistakes:

• Ignoring negative heights leads to wrong results
• Offsetting heights breaks relative trapping logic
• Assuming prefix/suffix arrays fix negative values automatically