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. You are given an array of integers and need to rearrange it so that no two adjacent elements are the same. Which approach guarantees an optimal solution for this problem?

easy

A. Count frequencies, then use a max heap to greedily place the most frequent elements first, ensuring spacing.

B. Use backtracking to generate all permutations and check for valid arrangements.

C. Sort the array and then swap adjacent elements to avoid duplicates.

D. Use dynamic programming to track valid sequences avoiding adjacent duplicates.

Solution

1. Step 1: Understand problem constraints

   The problem requires rearranging elements so no two adjacent are equal, which demands careful placement of frequent elements.

2. Step 2: Identify approach that handles frequency and spacing

   Using a max heap to always pick the most frequent element available and placing it ensures no two identical elements are adjacent, which brute force or simple sorting cannot guarantee efficiently.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Max heap approach handles frequency and spacing correctly [OK]

Hint: Max heap ensures spacing of frequent elements [OK]

Common Mistakes:

• Thinking sorting alone avoids adjacent duplicates
• Assuming DP solves this without frequency tracking

2. You are given an unsorted array of integers and need to find the maximum difference between successive elements in its sorted form, but you want to avoid sorting the entire array explicitly if possible. Which approach guarantees an optimal solution that leverages the problem's constraints?

easy

A. Use a dynamic programming approach to build up maximum gaps incrementally.

B. Apply the pigeonhole principle by distributing numbers into buckets to find the maximum gap between buckets.

C. Use a greedy algorithm that picks the largest and smallest elements repeatedly to find the maximum gap.

D. Sort the array fully and then scan to find the maximum gap between adjacent elements.

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding the maximum gap between sorted adjacent elements without necessarily sorting the entire array explicitly.

2. Step 2: Identify the approach that leverages problem properties

   The pigeonhole principle approach distributes elements into buckets based on min and max values, ensuring the maximum gap lies between buckets, not inside them, enabling O(n) time complexity.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Pigeonhole principle buckets capture gaps efficiently [OK]

Hint: Maximum gap lies between buckets, not inside [OK]

Common Mistakes:

• Assuming sorting is always necessary
• Using greedy without sorting or bucketing
• Confusing DP with sorting problems

3. Consider the following Python function that finds the minimum time difference between time points. What is the returned value when the input is ["01:01", "02:01", "01:02"]?

def findMinDifference(timePoints):
    seen = [False] * 1440
    for t in timePoints:
        h, m = map(int, t.split(':'))
        total = h * 60 + m
        if seen[total]:
            return 0
        seen[total] = True
    prev = -1
    first = -1
    min_diff = 1440
    for i in range(1440):
        if seen[i]:
            if prev != -1:
                min_diff = min(min_diff, i - prev)
            else:
                first = i
            prev = i
    min_diff = min(min_diff, 1440 - prev + first)
    return min_diff

easy

A. 59

B. 0

C. 60

D. 1

Solution

1. Step 1: Convert times to minutes and mark seen

   "01:01" -> 61, "02:01" -> 121, "01:02" -> 62; all unique, so no early return 0.

2. Step 2: Iterate over seen array to find minimum adjacent difference

   Adjacent times are 61 and 62 (diff 1), 62 and 121 (diff 59). Minimum difference is 1.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Minimum adjacent difference found is 1 minute [OK]

Hint: Check adjacent differences after sorting times [OK]

Common Mistakes:

• Confusing difference between 61 and 121 as minimum
• Forgetting to check circular difference
• Returning 0 incorrectly when no duplicates

4. Consider this modified h-index code snippet. Which line contains a subtle bug that can cause incorrect h-index results?

medium

A. Line 12: updating low to mid + 1 when count >= mid

B. Line 6: initializing count to zero inside the loop

C. Line 1: sorting citations in ascending order instead of descending

D. Line 9: breaking the loop when c < mid

Solution

1. Step 1: Identify sorting order impact

   Sorting ascending breaks the assumption that citations are in descending order, so the early break in counting fails.

2. Step 2: Check other lines

   Count initialization, break condition, and binary search updates are correct given descending order.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Ascending sort causes incorrect early break and wrong counts [OK]

Hint: Descending sort is critical for early break in counting [OK]

Common Mistakes:

• Sorting ascending by mistake
• Not breaking early
• Off-by-one in binary search updates

5. The following code attempts to sort a matrix diagonally using min-heaps keyed by (row - col). Identify the line containing the subtle bug that causes incorrect sorting or corrupted output.

from typing import List
import collections
import heapq

def diagonalSort(mat: List[List[int]]) -> List[List[int]]:
    m, n = len(mat), len(mat[0])
    diagonals = collections.defaultdict(list)
    for i in range(m):
        for j in range(n):
            heapq.heappush(diagonals[i + j], mat[i][j])  # Line X
    for i in range(m):
        for j in range(n):
            mat[i][j] = heapq.heappop(diagonals[i - j])  # Line Y
    return mat

medium

A. Line X: Using i + j as diagonal key instead of i - j.

B. Line Y: Popping from diagonals keyed by i - j instead of i + j.

C. Line X: Using heapq.heappush instead of sorting the diagonal list first.

D. Line Y: Assigning popped element directly without checking if heap is empty.

Solution

1. Step 1: Check diagonal key consistency

   The diagonal key must be consistent for both pushing and popping. Here, push uses i + j, pop uses i - j, causing mismatch.

2. Step 2: Identify impact of key mismatch

   Elements pushed into one diagonal heap are popped from a different key, leading to empty heaps or incorrect elements assigned.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Diagonal keys must match exactly for correct sorting [OK]

Hint: Diagonal key must be consistent for push and pop [OK]

Common Mistakes:

• Mixing i + j and i - j keys
• Forgetting to check heap emptiness
• Using reverse sorting but popping incorrectly