Lesson

5.9Sort color

Sorting Colors Problem

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 use the integers 0, 1, and 2 to represent red, white, and blue respectively. You must solve this problem without using the library's sort function.

Example Test Cases

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

Approaches

Brute Force Approach

Idea: Count the number of 0's, 1's, and 2's and then overwrite the original array.
Steps:
1. Traverse through the array and count how many 0's, 1's, and 2's are present.
2. Modify the array by first filling it with all 0's, followed by 1's, and then 2's.
Time Complexity: O(n) where n is the length of the array.
Space Complexity: O(1) as we only use constant extra space.
Example Code:

Dry Run: Input: [2, 0, 2, 1, 1, 0]
1. Count the occurrences: count = [2, 2, 2]
2. Overwrite the array with 0's, 1's, and 2's: [0, 0, 1, 1, 2, 2]

Efficient Approach (Dutch National Flag Algorithm)

Idea: Use three pointers to sort the array in one pass. One pointer for 0's, one for 2's, and the current element for 1's.
Steps:
1. Use three pointers: low (for 0's), mid (current element), and high (for 2's).
2. Traverse the array:
  - If the current element is 0, swap it with low and move both low and mid.
  - If the current element is 1, move mid.
  - If the current element is 2, swap it with high and move high down.
Time Complexity: O(n) where n is the length of the array.
Space Complexity: O(1) as it works in-place.
Example Code:

Dry Run: Input: [2, 0, 2, 1, 1, 0]
1. Initial pointers: low = 0, mid = 0, high = 5
2. Traverse and swap elements in a single pass to get [0, 0, 1, 1, 2, 2].

Complexity Analysis

Brute Force Approach

Time Complexity: O(n)
Space Complexity: O(1)

Efficient Approach

Time Complexity: O(n)
Space Complexity: O(1)

Conclusion

Both approaches solve the problem efficiently, but the Dutch National Flag Algorithm is more optimal as it sorts the array in a single pass and avoids the need for counting elements.

Previous Next