Jobs

Interviews

Discussions

Sort Colors #20 Most Asked

Medium

Capgemini

1 view

Topics:

ArraysTwo Pointers

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.

You must solve this problem without using the library's sort function.

Example 1:

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Example 2:

Input: nums = [2,0,1]
Output: [0,1,2]

Constraints:

n == nums.length
1 <= n <= 300
nums[i] is either 0, 1, or 2.

Follow up: Could you come up with a one-pass algorithm using only constant extra space?

Try coding it in LeetCode

Sort Colors #20 Most Asked

Medium

Capgemini

1 view

Topics:

ArraysTwo Pointers

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.

You must solve this problem without using the library's sort function.

Example 1:

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Example 2:

Input: nums = [2,0,1]
Output: [0,1,2]

Constraints:

n == nums.length
1 <= n <= 300
nums[i] is either 0, 1, or 2.

Follow up: Could you come up with a one-pass algorithm using only constant extra space?

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What should I do if the input array is empty or contains only a single element?
Is it guaranteed that the array will only contain the integers 0, 1, and 2, or could there be other values present that require special handling?
The problem states sorting should be done 'in-place'. Does this strictly mean I should not use any auxiliary data structures whose space complexity depends on the input size?
Can the input array `nums` be null or undefined? If so, how should I handle that case?
Just to confirm the sorting order, the final arrangement should be all 0s, followed by all 1s, and then all 2s, correct?

Brute Force Solution

Approach

The simplest way to solve this is to first count how many of each color you have. Once you know the counts, you can rebuild the entire collection from scratch in the correct order: all the reds, then all the whites, followed by all the blues.

Here's how the algorithm would work step-by-step:

First, go through the entire collection of colored items one by one.
Keep three separate tallies: one for red, one for white, and one for blue.
For each item you look at, add one to the correct color's tally.
After you've looked at every single item, you'll know the total number of reds, whites, and blues.
Now, imagine you have a new, empty collection.
Fill the beginning of this new collection with the number of red items you counted.
Next, right after the reds, fill it with the number of white items you counted.
Finally, fill the remaining spots with the number of blue items you counted.
The collection is now sorted by color.

Code Implementation

class Solution:
    def sortColors(self, nums: list[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # This approach uses two passes: one to count the colors and another to overwrite the array.
        red_count = 0
        white_count = 0
        blue_count = 0

        for color in nums:
            if color == 0:
                red_count += 1
            elif color == 1:
                white_count += 1
            else:
                blue_count += 1

        # Overwrite the original array with the correct number of 0s (reds).
        for index in range(red_count):
            nums[index] = 0

        # Continue overwriting where the reds left off with the 1s (whites).
        for index in range(red_count, red_count + white_count):
            nums[index] = 1

        # Finally, fill the remaining part of the array with 2s (blues).
        for index in range(red_count + white_count, len(nums)):
            nums[index] = 2

Big(O) Analysis

Time Complexity

O(n) – The time complexity is determined by two separate passes over the input array, where 'n' is the number of elements. The first pass iterates through all 'n' elements to count the occurrences of each color, which takes O(n) time. The second pass iterates through the array again, also 'n' times in total, to overwrite it with the sorted colors based on the counts. Since these two passes are sequential, not nested, the total operations are approximately n + n, which simplifies to O(n).

Space Complexity

O(1) – The space complexity is constant because the algorithm only uses a fixed number of auxiliary variables to solve the problem. Specifically, it requires three integer variables to store the tallies for the red, white, and blue items. The amount of memory used by these three counters does not change, regardless of the number of items (N) in the input collection.

Optimal Solution

Approach

The most efficient strategy is to sort the items in a single pass without using any extra storage. We do this by imagining three sections for red, white, and blue, and then moving items to their correct section one by one.

Here's how the algorithm would work step-by-step:

Imagine the collection is divided into three areas: a 'red' section at the beginning, a 'blue' section at the end, and an 'unknown' section in the middle.
Start by looking at the first item in the 'unknown' area.
If the item you're looking at is red, swap it with the first item right after the 'red' section and then expand the 'red' section by one.
If the item is blue, swap it with the last item right before the 'blue' section and then shrink the 'unknown' area from the end.
If the item is white, it's already in the right place for now, so just leave it and move on to inspect the next 'unknown' item.
Keep repeating this process of checking and swapping until the 'unknown' section completely disappears.
By the end, all the reds will have been moved to the front, all the blues to the back, and the whites will naturally end up in the middle, resulting in a sorted collection.

Code Implementation

def sort_colors(colors):
    red_section_end = 0
    blue_section_start = len(colors) - 1
    current_index = 0

    while current_index <= blue_section_start:
        # If the current element is red (0), it belongs in the front partition.

        if colors[current_index] == 0:
            colors[current_index], colors[red_section_end] = colors[red_section_end], colors[current_index]
            red_section_end += 1
            current_index += 1

        # If the current element is blue (2), it must be moved to the end partition.

        elif colors[current_index] == 2:
            colors[current_index], colors[blue_section_start] = colors[blue_section_start], colors[current_index]
            blue_section_start -= 1

        # If the element is white (1), it's in the correct middle partition, so we just advance.

        else:
            current_index += 1

Big(O) Analysis

Time Complexity

O(n) – The time complexity is determined by the number of times we inspect an element in the input array of size n. The provided single-pass approach uses a pointer to traverse the 'unknown' section of the array. This pointer starts at the beginning and moves towards the end, with each element being examined exactly once before it is placed in its correct section (red, white, or blue). Since every element is visited and processed a constant number of times, the total number of operations is directly proportional to n. Therefore, the algorithm has a linear time complexity, which simplifies to O(n).

Space Complexity

O(1) – The algorithm sorts the array in-place, meaning it rearranges the elements within the original array without creating any new data structures. It only requires a few variables to keep track of the boundaries of the red, white, and blue sections. Since the number of these pointer variables does not change regardless of the input array's size (N), the auxiliary space complexity is constant.

Edge Cases

Case	How to Handle
Input array is null or empty	The algorithm should handle this gracefully by simply returning without modification as there is nothing to sort.
Input array has only one element	The array is already sorted by definition, so the algorithm should terminate immediately without making any changes.
Input array contains only one or two distinct colors	The one-pass algorithm correctly handles this by partitioning the array based on the colors that are present.
Input array consists of all identical elements (e.g., all 0s, all 1s, or all 2s)	The pointers in the one-pass solution will move appropriately, resulting in the correct, unchanged sorted array.
Input array is already sorted	The algorithm will perform a single pass without any swaps, efficiently confirming the sorted state.
Input array is sorted in reverse order (e.g., [2, 2, 1, 0, 0])	The algorithm will perform the maximum number of swaps but will still correctly sort the array in a single pass.
Large input array (approaching memory or time limits)	The one-pass, in-place solution has O(n) time and O(1) space complexity, ensuring it scales efficiently for large inputs.
Input contains only 0s and 2s with no 1s	The middle pointer will correctly increment or the right pointer will decrement after swaps, leaving no space for the non-existent 1s.

Input array is null or empty

How to Handle:

The algorithm should handle this gracefully by simply returning without modification as there is nothing to sort.

Input array has only one element

How to Handle:

The array is already sorted by definition, so the algorithm should terminate immediately without making any changes.

Input array contains only one or two distinct colors

How to Handle:

The one-pass algorithm correctly handles this by partitioning the array based on the colors that are present.

Input array consists of all identical elements (e.g., all 0s, all 1s, or all 2s)

How to Handle:

The pointers in the one-pass solution will move appropriately, resulting in the correct, unchanged sorted array.

Input array is already sorted

How to Handle:

The algorithm will perform a single pass without any swaps, efficiently confirming the sorted state.

Input array is sorted in reverse order (e.g., [2, 2, 1, 0, 0])

How to Handle:

The algorithm will perform the maximum number of swaps but will still correctly sort the array in a single pass.

Large input array (approaching memory or time limits)

How to Handle:

The one-pass, in-place solution has O(n) time and O(1) space complexity, ensuring it scales efficiently for large inputs.

Input contains only 0s and 2s with no 1s

How to Handle:

The middle pointer will correctly increment or the right pointer will decrement after swaps, leaving no space for the non-existent 1s.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What should I do if the input array is empty or contains only a single element?
Is it guaranteed that the array will only contain the integers 0, 1, and 2, or could there be other values present that require special handling?
The problem states sorting should be done 'in-place'. Does this strictly mean I should not use any auxiliary data structures whose space complexity depends on the input size?
Can the input array `nums` be null or undefined? If so, how should I handle that case?
Just to confirm the sorting order, the final arrangement should be all 0s, followed by all 1s, and then all 2s, correct?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, go through the entire collection of colored items one by one.
Keep three separate tallies: one for red, one for white, and one for blue.
For each item you look at, add one to the correct color's tally.
After you've looked at every single item, you'll know the total number of reds, whites, and blues.
Now, imagine you have a new, empty collection.
Fill the beginning of this new collection with the number of red items you counted.
Next, right after the reds, fill it with the number of white items you counted.
Finally, fill the remaining spots with the number of blue items you counted.
The collection is now sorted by color.

Code Implementation

class Solution:
    def sortColors(self, nums: list[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # This approach uses two passes: one to count the colors and another to overwrite the array.
        red_count = 0
        white_count = 0
        blue_count = 0

        for color in nums:
            if color == 0:
                red_count += 1
            elif color == 1:
                white_count += 1
            else:
                blue_count += 1

        # Overwrite the original array with the correct number of 0s (reds).
        for index in range(red_count):
            nums[index] = 0

        # Continue overwriting where the reds left off with the 1s (whites).
        for index in range(red_count, red_count + white_count):
            nums[index] = 1

        # Finally, fill the remaining part of the array with 2s (blues).
        for index in range(red_count + white_count, len(nums)):
            nums[index] = 2

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine the collection is divided into three areas: a 'red' section at the beginning, a 'blue' section at the end, and an 'unknown' section in the middle.
Start by looking at the first item in the 'unknown' area.
If the item you're looking at is red, swap it with the first item right after the 'red' section and then expand the 'red' section by one.
If the item is blue, swap it with the last item right before the 'blue' section and then shrink the 'unknown' area from the end.
If the item is white, it's already in the right place for now, so just leave it and move on to inspect the next 'unknown' item.
Keep repeating this process of checking and swapping until the 'unknown' section completely disappears.
By the end, all the reds will have been moved to the front, all the blues to the back, and the whites will naturally end up in the middle, resulting in a sorted collection.

Code Implementation

def sort_colors(colors):
    red_section_end = 0
    blue_section_start = len(colors) - 1
    current_index = 0

    while current_index <= blue_section_start:
        # If the current element is red (0), it belongs in the front partition.

        if colors[current_index] == 0:
            colors[current_index], colors[red_section_end] = colors[red_section_end], colors[current_index]
            red_section_end += 1
            current_index += 1

        # If the current element is blue (2), it must be moved to the end partition.

        elif colors[current_index] == 2:
            colors[current_index], colors[blue_section_start] = colors[blue_section_start], colors[current_index]
            blue_section_start -= 1

        # If the element is white (1), it's in the correct middle partition, so we just advance.

        else:
            current_index += 1

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input array is null or empty	The algorithm should handle this gracefully by simply returning without modification as there is nothing to sort.
Input array has only one element	The array is already sorted by definition, so the algorithm should terminate immediately without making any changes.
Input array contains only one or two distinct colors	The one-pass algorithm correctly handles this by partitioning the array based on the colors that are present.
Input array consists of all identical elements (e.g., all 0s, all 1s, or all 2s)	The pointers in the one-pass solution will move appropriately, resulting in the correct, unchanged sorted array.
Input array is already sorted	The algorithm will perform a single pass without any swaps, efficiently confirming the sorted state.
Input array is sorted in reverse order (e.g., [2, 2, 1, 0, 0])	The algorithm will perform the maximum number of swaps but will still correctly sort the array in a single pass.
Large input array (approaching memory or time limits)	The one-pass, in-place solution has O(n) time and O(1) space complexity, ensuring it scales efficiently for large inputs.
Input contains only 0s and 2s with no 1s	The middle pointer will correctly increment or the right pointer will decrement after swaps, leaving no space for the non-existent 1s.

Input array is null or empty

How to Handle:

The algorithm should handle this gracefully by simply returning without modification as there is nothing to sort.

Input array has only one element

How to Handle:

The array is already sorted by definition, so the algorithm should terminate immediately without making any changes.

Input array contains only one or two distinct colors

How to Handle:

The one-pass algorithm correctly handles this by partitioning the array based on the colors that are present.

Input array consists of all identical elements (e.g., all 0s, all 1s, or all 2s)

How to Handle:

The pointers in the one-pass solution will move appropriately, resulting in the correct, unchanged sorted array.

Input array is already sorted

How to Handle:

The algorithm will perform a single pass without any swaps, efficiently confirming the sorted state.

Input array is sorted in reverse order (e.g., [2, 2, 1, 0, 0])

How to Handle:

The algorithm will perform the maximum number of swaps but will still correctly sort the array in a single pass.

Large input array (approaching memory or time limits)

How to Handle:

The one-pass, in-place solution has O(n) time and O(1) space complexity, ensuring it scales efficiently for large inputs.

Input contains only 0s and 2s with no 1s

How to Handle:

The middle pointer will correctly increment or the right pointer will decrement after swaps, leaving no space for the non-existent 1s.

0/0 Capgemini questions completed

0/0 completed