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 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. Given the following code and input nums = [-4, -2, 2, 4], a = 1, b = 3, c = 5, what is the final returned array?

easy

A. [3, 9, 33, 15]

B. [33, 15, 9, 3]

C. [3, 9, 15, 33]

D. [15, 3, 9, 33]

Solution

1. Step 1: Compute transformed values

   For nums = [-4, -2, 2, 4], quad(x) = x² + 3x + 5: -4 -> 16 -12 + 5 = 9 -2 -> 4 -6 + 5 = 3 2 -> 4 + 6 + 5 = 15 4 -> 16 + 12 + 5 = 33

2. Step 2: Two pointers fill from end

   a >= 0, so fill result from end: Compare left_val=9 and right_val=33 -> 33 > 9, place 33 at result[3] Move right pointer left Next compare 9 and 15 -> 15 > 9, place 15 at result[2] Move right pointer left Next compare 9 and 3 -> 9 > 3, place 9 at result[1] Move left pointer right Finally place 3 at result[0] Result array is [3, 9, 15, 33]

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output is sorted ascending: [3, 9, 15, 33] [OK]

Hint: Two pointers fill output from end or start based on a sign [OK]

Common Mistakes:

• Confusing index direction for filling output
• Mixing up left and right pointer values

3. What is the time complexity of the optimal two-pointer approach for the Sort Transformed Array problem, and why might some candidates incorrectly think it is higher?

medium

A. O(n) for processing plus O(n) auxiliary space for the output array.

B. O(n log n) because sorting is required after transformation.

C. O(n²) because each element is compared with every other element during merging.

D. O(n) because each element is processed exactly once using two pointers.

Solution

1. Step 1: Identify loop iterations

   The two-pointer approach processes each element once, moving pointers inward until they meet, resulting in O(n) iterations.

2. Step 2: Understand no sorting needed

   Because the input is sorted and the parabola shape is leveraged, no sorting step is required, avoiding O(n log n).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Linear scan with two pointers, no nested loops [OK]

Hint: Two pointers scan array once -> O(n) time [OK]

Common Mistakes:

• Assuming sorting after transformation is needed
• Confusing auxiliary space with time complexity

4. Consider the following buggy implementation of wiggle sort. Which line contains the subtle bug that causes the algorithm to fail on inputs with duplicates?

medium

A. Line 9: def virtual_index(i): return (1 + 2 * i) % (n | 1)

B. Line 3: nums.sort()

C. Line 4: median = nums[n // 2]

D. Line 15: elif nums[vi] < median:

Solution

1. Step 1: Identify median calculation

   The median is incorrectly chosen as nums[n // 2], which is the upper median for even-length arrays, but the algorithm requires the lower median nums[(n - 1) // 2].

2. Step 2: Understand impact on partitioning

   Incorrect median causes wrong partitioning of elements equal to median, leading to clustering and violation of wiggle property especially with duplicates.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Correct median index is (n - 1) // 2, not n // 2 [OK]

Hint: Median index off-by-one breaks partitioning with duplicates [OK]

Common Mistakes:

• Using n//2 instead of (n-1)//2 for median
• Ignoring duplicates in partitioning
• Misusing virtual indexing

5. Suppose the input array can contain negative numbers and duplicates, and you want to wiggle sort it so that nums[0] < nums[1] > nums[2] < nums[3] > ... still holds. Which modification to the optimal algorithm is necessary to handle this variant correctly?

hard

A. Replace the median finding step with a linear-time median of medians algorithm to handle negatives efficiently.

B. Skip virtual indexing and rearrange elements directly by index after sorting to simplify handling negatives.

C. Use the same algorithm without changes since sorting and virtual indexing handle negatives and duplicates naturally.

D. Modify the partitioning to handle equal elements by grouping all medians in the middle to avoid clustering.

Solution

1. Step 1: Recognize challenges with negatives and duplicates

   Negative numbers do not affect sorting, but duplicates require careful partitioning to avoid clustering equal elements.

2. Step 2: Modify partitioning to handle duplicates

   Three-way partitioning must group all median elements in the middle to maintain strict inequalities and wiggle property.

3. Step 3: Confirm virtual indexing remains necessary

   Virtual indexing is still needed to place elements correctly; skipping it breaks the wiggle pattern.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Proper handling of duplicates in partitioning ensures wiggle property with negatives [OK]

Hint: Handle duplicates by grouping medians in partitioning [OK]

Common Mistakes:

• Assuming negatives break median finding
• Skipping virtual indexing
• Ignoring duplicates clustering