Sort Colors (Dutch National Flag)

🎯

Sort Colors (Dutch National Flag)

mediumSORT_SEARCHAmazonFacebookGoogle

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.

💡 This problem is about sorting an array with only three distinct values efficiently. Beginners often struggle because they try to use general sorting algorithms instead of leveraging the limited range of values to optimize.

📋

Problem Statement

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

💡

Example

Input"[2,0,2,1,1,0]"

Output[0,0,1,1,2,2]

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

• All elements are the same color → array remains unchanged
• Array of length 1 → no sorting needed
• Array with only two colors present → sort those two correctly
• Array with colors already sorted → minimal operations

⚠️

Common Mistakes

Swapping incorrectly causing infinite loops

Algorithm gets stuck or produces wrong order

✅ Ensure pointers are updated correctly after swaps

Using extra space unnecessarily

Higher space complexity than needed

✅ Use in-place partitioning with pointers instead of extra arrays or counters

Not handling edge cases like empty or single-element arrays

Runtime errors or incorrect output

✅ Add checks or ensure loops handle small arrays gracefully

Confusing pointer roles (low, mid, high)

Colors get misplaced, final array incorrect

✅ Clearly define and track pointer responsibilities during implementation

🧠

Brute Force (Counting Sort with Extra Space)

💡 This approach exists to build intuition by counting occurrences first, which is straightforward but uses extra space and two passes. It helps beginners understand the problem structure before optimizing.

Intuition

Count how many 0s, 1s, and 2s are in the array, then overwrite the array with the counted numbers in order.

Algorithm

1. Initialize counters for 0, 1, and 2 to zero.
2. Traverse the array once to count the occurrences of each color.
3. Overwrite the array with 0s, then 1s, then 2s based on the counts.
4. Return the sorted array.

💡 This approach is easy to visualize but requires two passes and extra space for counters, which is acceptable for understanding but not optimal.

</>

Code

def sortColors(nums):
    count0, count1, count2 = 0, 0, 0
    for num in nums:
        if num == 0:
            count0 += 1
        elif num == 1:
            count1 += 1
        else:
            count2 += 1
    index = 0
    for _ in range(count0):
        nums[index] = 0
        index += 1
    for _ in range(count1):
        nums[index] = 1
        index += 1
    for _ in range(count2):
        nums[index] = 2
        index += 1

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

Line Notes

count0, count1, count2 = 0, 0, 0Initialize counters for each color to zero to track occurrences

for num in nums:Traverse the array to count each color's frequency

if num == 0:Increment count for color 0 (red)

elif num == 1:Increment count for color 1 (white)

else:Increment count for color 2 (blue)

index = 0Start overwriting the array from the beginning

for _ in range(count0):Overwrite all positions with 0s first

nums[index] = 0Place color 0 at current index

index += 1Move to next index for placement

for _ in range(count1):Overwrite next positions with 1s

for _ in range(count2):Overwrite remaining positions with 2s

import java.util.Arrays;
public class SortColors {
    public static void sortColors(int[] nums) {
        int count0 = 0, count1 = 0, count2 = 0;
        for (int num : nums) {
            if (num == 0) count0++;
            else if (num == 1) count1++;
            else count2++;
        }
        int index = 0;
        for (int i = 0; i < count0; i++) nums[index++] = 0;
        for (int i = 0; i < count1; i++) nums[index++] = 1;
        for (int i = 0; i < count2; i++) nums[index++] = 2;
    }
    public static void main(String[] args) {
        int[] arr = {2,0,2,1,1,0};
        sortColors(arr);
        System.out.println(Arrays.toString(arr));
    }
}

Line Notes

int count0 = 0, count1 = 0, count2 = 0;Initialize counters for each color to zero

for (int num : nums)Iterate over array to count colors

if (num == 0) count0++;Count color 0 occurrences

else if (num == 1) count1++;Count color 1 occurrences

else count2++;Count color 2 occurrences

int index = 0;Index to overwrite array from start

for (int i = 0; i < count0; i++) nums[index++] = 0;Overwrite 0s first

for (int i = 0; i < count1; i++) nums[index++] = 1;Overwrite 1s next

for (int i = 0; i < count2; i++) nums[index++] = 2;Overwrite 2s last

System.out.println(Arrays.toString(arr));Print sorted array for verification

#include <iostream>
#include <vector>
using namespace std;

void sortColors(vector<int>& nums) {
    int count0 = 0, count1 = 0, count2 = 0;
    for (int num : nums) {
        if (num == 0) count0++;
        else if (num == 1) count1++;
        else count2++;
    }
    int index = 0;
    for (int i = 0; i < count0; i++) nums[index++] = 0;
    for (int i = 0; i < count1; i++) nums[index++] = 1;
    for (int i = 0; i < count2; i++) nums[index++] = 2;
}

int main() {
    vector<int> arr = {2,0,2,1,1,0};
    sortColors(arr);
    for (int num : arr) cout << num << ' ';
    cout << endl;
    return 0;
}

Line Notes

int count0 = 0, count1 = 0, count2 = 0;Initialize counters for each color

for (int num : nums)Count occurrences of each color

if (num == 0) count0++;Increment count for 0

else if (num == 1) count1++;Increment count for 1

else count2++;Increment count for 2

int index = 0;Index to overwrite the array

for (int i = 0; i < count0; i++) nums[index++] = 0;Overwrite 0s first

for (int i = 0; i < count1; i++) nums[index++] = 1;Overwrite 1s next

for (int i = 0; i < count2; i++) nums[index++] = 2;Overwrite 2s last

for (int num : arr) cout << num << ' ';Print the sorted array

function sortColors(nums) {
    let count0 = 0, count1 = 0, count2 = 0;
    for (let num of nums) {
        if (num === 0) count0++;
        else if (num === 1) count1++;
        else count2++;
    }
    let index = 0;
    for (let i = 0; i < count0; i++) nums[index++] = 0;
    for (let i = 0; i < count1; i++) nums[index++] = 1;
    for (let i = 0; i < count2; i++) nums[index++] = 2;
}

// Test
const arr = [2,0,2,1,1,0];
sortColors(arr);
console.log(arr);

Line Notes

let count0 = 0, count1 = 0, count2 = 0;Initialize counters for each color

for (let num of nums)Count each color in the array

if (num === 0) count0++;Increment count for 0

else if (num === 1) count1++;Increment count for 1

else count2++;Increment count for 2

let index = 0;Start index for overwriting array

for (let i = 0; i < count0; i++) nums[index++] = 0;Overwrite 0s first

for (let i = 0; i < count1; i++) nums[index++] = 1;Overwrite 1s next

for (let i = 0; i < count2; i++) nums[index++] = 2;Overwrite 2s last

console.log(arr);Output the sorted array

⏱

Complexity

TimeO(n)

SpaceO(1)

We do two passes over the array: one to count and one to overwrite, each O(n). The counters use constant space.

💡 For n=100,000, this means about 200,000 operations, which is efficient but not optimal since we traverse twice.

Interview Verdict: Accepted but not optimal

This approach works but is not the best because it requires two passes and does not sort in a single traversal.

🧠

Two-Pass Partitioning with Two Pointers

💡 This approach improves by using two passes but modifies the array in place without extra counters, helping understand partitioning techniques.

Intuition

First move all 0s to the front, then move all 1s after the 0s, leaving 2s at the end.

Algorithm

1. Use a pointer to move all 0s to the front in the first pass.
2. Use a second pointer to move all 1s after the 0s in the second pass.
3. 2s will naturally be at the end after these two passes.
4. Return the sorted array.

💡 This approach is more intuitive than counting but still requires two passes and careful pointer management.

</>

Code

def sortColors(nums):
    n = len(nums)
    zero_pos = 0
    for i in range(n):
        if nums[i] == 0:
            nums[i], nums[zero_pos] = nums[zero_pos], nums[i]
            zero_pos += 1
    one_pos = zero_pos
    for i in range(zero_pos, n):
        if nums[i] == 1:
            nums[i], nums[one_pos] = nums[one_pos], nums[i]
            one_pos += 1

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

Line Notes

n = len(nums)Store length of array for iteration

zero_pos = 0Pointer to place next 0 at the front

for i in range(n):Traverse entire array to find 0s

if nums[i] == 0:When a 0 is found, swap it to the front

nums[i], nums[zero_pos] = nums[zero_pos], nums[i]Swap current 0 with element at zero_pos

zero_pos += 1Increment zero_pos to next position

one_pos = zero_posPointer to place next 1 after all 0s

for i in range(zero_pos, n):Traverse remaining array to find 1s

if nums[i] == 1:When a 1 is found, swap it after 0s

nums[i], nums[one_pos] = nums[one_pos], nums[i]Swap current 1 with element at one_pos

one_pos += 1Increment one_pos to next position

import java.util.Arrays;
public class SortColors {
    public static void sortColors(int[] nums) {
        int zeroPos = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                int temp = nums[i];
                nums[i] = nums[zeroPos];
                nums[zeroPos] = temp;
                zeroPos++;
            }
        }
        int onePos = zeroPos;
        for (int i = zeroPos; i < nums.length; i++) {
            if (nums[i] == 1) {
                int temp = nums[i];
                nums[i] = nums[onePos];
                nums[onePos] = temp;
                onePos++;
            }
        }
    }
    public static void main(String[] args) {
        int[] arr = {2,0,2,1,1,0};
        sortColors(arr);
        System.out.println(Arrays.toString(arr));
    }
}

Line Notes

int zeroPos = 0;Pointer to place next 0 at front

for (int i = 0; i < nums.length; i++)Traverse array to find 0s

if (nums[i] == 0)Check if current element is 0

int temp = nums[i];Swap current 1 with element at onePos

nums[i] = nums[zeroPos];Part of swap operation

nums[zeroPos] = temp;Part of swap operation

zeroPos++;Move zeroPos forward

int onePos = zeroPos;Pointer to place next 1 after 0s

for (int i = zeroPos; i < nums.length; i++)Traverse remaining array to find 1s

if (nums[i] == 1)Check if current element is 1

nums[i] = nums[onePos];Part of swap operation

nums[onePos] = temp;Part of swap operation

onePos++;Move onePos forward

#include <iostream>
#include <vector>
using namespace std;

void sortColors(vector<int>& nums) {
    int zeroPos = 0;
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] == 0) {
            swap(nums[i], nums[zeroPos]);
            zeroPos++;
        }
    }
    int onePos = zeroPos;
    for (int i = zeroPos; i < nums.size(); i++) {
        if (nums[i] == 1) {
            swap(nums[i], nums[onePos]);
            onePos++;
        }
    }
}

int main() {
    vector<int> arr = {2,0,2,1,1,0};
    sortColors(arr);
    for (int num : arr) cout << num << ' ';
    cout << endl;
    return 0;
}

Line Notes

int zeroPos = 0;Pointer to place next 0 at front

for (int i = 0; i < nums.size(); i++)Traverse array to find 0s

if (nums[i] == 0)Check if current element is 0

swap(nums[i], nums[zeroPos]);Swap current 0 with element at zeroPos

zeroPos++;Move zeroPos forward

int onePos = zeroPos;Pointer to place next 1 after 0s

for (int i = zeroPos; i < nums.size(); i++)Traverse remaining array to find 1s

if (nums[i] == 1)Check if current element is 1

swap(nums[i], nums[onePos]);Swap current 1 with element at onePos

onePos++;Move onePos forward

function sortColors(nums) {
    let zeroPos = 0;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === 0) {
            [nums[i], nums[zeroPos]] = [nums[zeroPos], nums[i]];
            zeroPos++;
        }
    }
    let onePos = zeroPos;
    for (let i = zeroPos; i < nums.length; i++) {
        if (nums[i] === 1) {
            [nums[i], nums[onePos]] = [nums[onePos], nums[i]];
            onePos++;
        }
    }
}

// Test
const arr = [2,0,2,1,1,0];
sortColors(arr);
console.log(arr);

Line Notes

let zeroPos = 0;Pointer to place next 0 at front

for (let i = 0; i < nums.length; i++)Traverse array to find 0s

if (nums[i] === 0)Check if current element is 0

[nums[i], nums[zeroPos]] = [nums[zeroPos], nums[i]];Swap current 0 with element at zeroPos

zeroPos++;Move zeroPos forward

let onePos = zeroPos;Pointer to place next 1 after 0s

for (let i = zeroPos; i < nums.length; i++)Traverse remaining array to find 1s

if (nums[i] === 1)Check if current element is 1

[nums[i], nums[onePos]] = [nums[onePos], nums[i]];Swap current 1 with element at onePos

onePos++;Move onePos forward

⏱

Complexity

TimeO(n)

SpaceO(1)

Two passes over the array, each O(n), with constant extra space for pointers.

💡 For n=100,000, this means about 200,000 operations, still efficient but not single pass.

Interview Verdict: Accepted but not optimal

Better than brute force but still requires two passes; good stepping stone to optimal.

🧠

Optimal One-Pass Dutch National Flag Algorithm

💡 This is the classic optimal solution that sorts the array in one pass using three pointers, minimizing operations and space.

Intuition

Use three pointers to partition the array into four sections: all 0s before low, all 1s between low and mid, unknown between mid and high, and all 2s after high.

Algorithm

1. Initialize three pointers: low = 0, mid = 0, high = n-1.
2. Traverse the array with mid pointer until it passes high.
3. If nums[mid] == 0, swap with nums[low], increment low and mid.
4. If nums[mid] == 1, just increment mid.
5. If nums[mid] == 2, swap with nums[high], decrement high.
6. Continue until mid > high.

💡 This approach is tricky at first but ensures all colors are sorted in one pass without extra space.

</>

Code

def sortColors(nums):
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:  # nums[mid] == 2
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1

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

Line Notes

low, mid, high = 0, 0, len(nums) - 1Initialize pointers for partitioning the array into zones

while mid <= high:Process elements until mid pointer passes high pointer

if nums[mid] == 0:If current element is 0, swap it to the front zone

nums[low], nums[mid] = nums[mid], nums[low]Swap 0 to the low pointer position

low += 1Move low pointer forward as 0 zone grows

mid += 1Move mid pointer forward

elif nums[mid] == 1:If current element is 1, it's in correct middle zone, just move mid

else: # nums[mid] == 2If current element is 2, swap it to the end zone

nums[mid], nums[high] = nums[high], nums[mid]Swap 2 to the high pointer position

high -= 1Move high pointer backward as 2 zone grows

import java.util.Arrays;
public class SortColors {
    public static void sortColors(int[] nums) {
        int low = 0, mid = 0, high = nums.length - 1;
        while (mid <= high) {
            if (nums[mid] == 0) {
                int temp = nums[low];
                nums[low] = nums[mid];
                nums[mid] = temp;
                low++;
                mid++;
            } else if (nums[mid] == 1) {
                mid++;
            } else {
                int temp = nums[mid];
                nums[mid] = nums[high];
                nums[high] = temp;
                high--;
            }
        }
    }
    public static void main(String[] args) {
        int[] arr = {2,0,2,1,1,0};
        sortColors(arr);
        System.out.println(Arrays.toString(arr));
    }
}

Line Notes

int low = 0, mid = 0, high = nums.length - 1;Initialize pointers for partitioning the array

while (mid <= high)Process elements until mid passes high

if (nums[mid] == 0)If current element is 0, swap to front zone

int temp = nums[low];Swap operation part 1

nums[low] = nums[mid];Swap operation part 2

nums[mid] = temp;Swap operation part 3

low++;Move low pointer forward

mid++;Move mid pointer forward

else if (nums[mid] == 1)If current element is 1, just move mid

elseIf current element is 2, swap to end zone

int temp = nums[mid];Swap operation part 1

nums[mid] = nums[high];Swap operation part 2

nums[high] = temp;Swap operation part 3

high--;Move high pointer backward

#include <iostream>
#include <vector>
using namespace std;

void sortColors(vector<int>& nums) {
    int low = 0, mid = 0, high = nums.size() - 1;
    while (mid <= high) {
        if (nums[mid] == 0) {
            swap(nums[low], nums[mid]);
            low++;
            mid++;
        } else if (nums[mid] == 1) {
            mid++;
        } else {
            swap(nums[mid], nums[high]);
            high--;
        }
    }
}

int main() {
    vector<int> arr = {2,0,2,1,1,0};
    sortColors(arr);
    for (int num : arr) cout << num << ' ';
    cout << endl;
    return 0;
}

Line Notes

int low = 0, mid = 0, high = nums.size() - 1;Initialize pointers for partitioning the array

while (mid <= high)Process elements until mid passes high

if (nums[mid] == 0)If current element is 0, swap to front zone

swap(nums[low], nums[mid]);Swap 0 to low pointer position

low++;Move low pointer forward

mid++;Move mid pointer forward

else if (nums[mid] == 1)If current element is 1, just move mid

elseIf current element is 2, swap to end zone

swap(nums[mid], nums[high]);Swap 2 to high pointer position

high--;Move high pointer backward

function sortColors(nums) {
    let low = 0, mid = 0, high = nums.length - 1;
    while (mid <= high) {
        if (nums[mid] === 0) {
            [nums[low], nums[mid]] = [nums[mid], nums[low]];
            low++;
            mid++;
        } else if (nums[mid] === 1) {
            mid++;
        } else {
            [nums[mid], nums[high]] = [nums[high], nums[mid]];
            high--;
        }
    }
}

// Test
const arr = [2,0,2,1,1,0];
sortColors(arr);
console.log(arr);

Line Notes

let low = 0, mid = 0, high = nums.length - 1;Initialize pointers for partitioning the array

while (mid <= high)Process elements until mid passes high

if (nums[mid] === 0)If current element is 0, swap to front zone

[nums[low], nums[mid]] = [nums[mid], nums[low]];Swap 0 to low pointer position

low++;Move low pointer forward

mid++;Move mid pointer forward

else if (nums[mid] === 1)If current element is 1, just move mid

elseIf current element is 2, swap to end zone

[nums[mid], nums[high]] = [nums[high], nums[mid]];Swap 2 to high pointer position

high--;Move high pointer backward

⏱

Complexity

TimeO(n)

SpaceO(1)

Single pass through the array with constant extra space using three pointers.

💡 For n=100,000, this means about 100,000 operations, the most efficient approach.

Interview Verdict: Accepted and optimal

This is the best approach to implement in interviews due to its efficiency and elegance.

📊

All Approaches - One-Glance Tradeoffs

💡 The optimal one-pass approach is preferred in interviews for its efficiency and elegance; others are useful for understanding.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n)	O(1)	No	N/A	Mention only - never code
2. Two-Pass Partitioning	O(n)	O(1)	No	N/A	Good stepping stone, mention or code if stuck
3. One-Pass Dutch National Flag	O(n)	O(1)	No	N/A	Code this approach in 95% of interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and know when and how to present them in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force counting approach to show understanding.Step 3: Explain the two-pass partitioning as an improvement.Step 4: Present the optimal one-pass Dutch National Flag algorithm.Step 5: Code the optimal solution carefully and test with examples.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your problem understanding, ability to optimize, code correctness, and handling edge cases.

Common Follow-ups

• What if the array contains more than three colors? → Use counting or generalized partitioning.
• Can you do it without using extra space? → Yes, the Dutch National Flag algorithm does it in-place.

💡 These follow-ups test your ability to generalize and optimize your solution further.

🔍

Pattern Recognition

When to Use

1) Input array with only three distinct values; 2) Need to sort or partition by these values; 3) In-place sorting preferred; 4) Linear time required.

Signature Phrases

sort colorsDutch National Flagthree-way partition

NOT This Pattern When

General sorting problems with many distinct values or no in-place constraints

Similar Problems

Sort an Array of 0s, 1s and 2s - same problem with different wordingPartition Labels - partitioning string into parts with unique chars

Practice

1. You are given a sorted array of integers and a value K. You need to count the number of pairs (i, j) with i < j such that the absolute difference between the elements at these indices is at most K. Which algorithmic approach guarantees the most efficient solution for this problem?

easy

A. Use binary search to find the upper bound for each element and count pairs accordingly.

B. Use a brute force nested loop to check all pairs and count those with difference ≤ K.

C. Use dynamic programming to store counts of valid pairs up to each index.

D. Use a two-pointer sliding window approach to find pairs with difference ≤ K in O(n) time.

Solution

1. Step 1: Understand problem constraints and sorted input

   The array is sorted, so for each element, pairs with difference ≤ K lie within a contiguous range to the right.

2. Step 2: Identify optimal approach

   A two-pointer sliding window approach can find pairs with difference ≤ K in O(n) time by expanding and contracting the window efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Two pointers leverage sorted order for linear time counting [OK]

Hint: Two-pointer sliding window exploits sorted array for O(n) counting [OK]

Common Mistakes:

• Assuming binary search is always better than two pointers
• Using DP which is unnecessary and inefficient
• Choosing brute force due to simplicity

2. Consider the following code snippet for removing duplicates from a sorted array allowing at most two duplicates. What is the value of write_index after processing the input [1,1,2]?

easy

A. 2

B. 1

C. 3

D. 0

Solution

1. Step 1: Trace write_index and read_index for input [1,1,2]

   Initially, write_index=0. Iteration 0: write_index<2, write 1, write_index=1. Iteration 1: write_index=1<2, write 1, write_index=2. Iteration 2: nums[2]=2 != nums[0]=1, write 2, write_index=3.

2. Step 2: Final write_index value

   After processing all elements, write_index=3, indicating the length of the modified array.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   All elements allowed, write_index matches array length [OK]

Hint: write_index increments for allowed duplicates [OK]

Common Mistakes:

• Off-by-one errors in write_index
• Confusing read_index with write_index
• Not handling first two elements separately

3. You are given a sorted array and need to remove duplicates in-place such that each element appears only once, returning the new length. Which approach guarantees an optimal O(n) time and O(1) space solution?

easy

A. Use two pointers moving in the same direction: one to track unique elements and one to scan through the array.

B. Use a nested loop to compare each element with all others and shift elements to remove duplicates.

C. Use a hash set to track seen elements and build a new array with unique values.

D. Use dynamic programming to store the length of unique subsequences ending at each index.

Solution

1. Step 1: Understand problem constraints

   The array is sorted, so duplicates are consecutive, enabling a linear scan with two pointers.

2. Step 2: Identify optimal approach

   Two pointers moving forward: one to track last unique element, one to scan and overwrite duplicates, achieves O(n) time and O(1) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two pointers approach is standard for in-place duplicate removal in sorted arrays [OK]

Hint: Sorted array allows two-pointer linear scan [OK]

Common Mistakes:

• Using extra space like hash sets when in-place is required

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

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