grid47 Exploring patterns and algorithms
Oct 30, 2024
5 min read
Solution to LeetCode 75: Sort Colors Problem
You are given an array of integers where each element represents a color: 0 for red, 1 for white, and 2 for blue. Your task is to sort the array such that all reds (0) appear first, followed by whites (1), and finally blues (2). Solve the problem in one pass with constant extra space, without using any built-in sort functions.
Problem
Approach
Steps
Complexity
Input: The input consists of an array of integers where each integer is either 0, 1, or 2.
Example: nums = [1, 0, 2, 1, 0, 2]
Constraints:
• 1 <= n <= 300
• nums[i] is either 0, 1, or 2.
Output: Return the sorted array where all 0s (red) appear first, followed by 1s (white), and finally 2s (blue).
Example: [0, 0, 1, 1, 2, 2]
Constraints:
• The output should be a single array with the elements sorted according to the color order.
Goal: Sort the array in-place using a one-pass algorithm with constant space.
Steps:
• Use a three-pointer approach (Dutch National Flag algorithm):
• Set pointers i and j at the beginning and end of the array, respectively.
• Iterate through the array using a third pointer k to rearrange the elements by swapping them with the correct pointers.
Goal: The matrix contains only integers 0, 1, or 2, and its size is constrained.
Steps:
• 1 <= n <= 300
• nums[i] is either 0, 1, or 2.
Assumptions:
• The array will only contain the integers 0, 1, and 2.
• The array has at least one element.
• Input: nums = [1, 0, 2, 1, 0, 2]
• Explanation: By sorting the array, we move the 0s to the front, followed by the 1s and 2s, resulting in [0, 0, 1, 1, 2, 2].
• Input: nums = [2, 1, 0]
• Explanation: The array is sorted to [0, 1, 2], with all the 0s first, followed by 1s and 2s.
Approach: The goal is to perform an in-place sort with a time complexity of O(n) and constant extra space. We can achieve this using the Dutch National Flag algorithm.
Observations:
• The array only contains three distinct values: 0, 1, and 2.
• We need to sort the array in a way that minimizes space and performs in linear time.
• By using three pointers, we can segregate the 0s, 1s, and 2s efficiently.
Steps:
• Initialize three pointers: i (for 0), k (for current element), and j (for 2).
• Move through the array using k as the current pointer.
• If nums[k] is 0, swap it with nums[i] and increment i and k.
• If nums[k] is 2, swap it with nums[j] and decrement j.
• If nums[k] is 1, simply increment k.
Empty Inputs:
• If the array is empty, there is nothing to sort.
Large Inputs:
• Ensure that the algorithm works efficiently with the maximum array size of 300.
Special Values:
• The input array may contain only one type of color (e.g., all 0s, all 1s, or all 2s).
Constraints:
• The function should perform the sorting in one pass with O(1) extra space.
voidsortColors(vector<int>& nums) {
int n = nums.size();
int low =0, mid =0, high = n -1;
while (mid <= high) {
if (nums[mid] ==0) {
swap(nums[low], nums[mid]);
low++;
mid++;
} elseif (nums[mid] ==1) {
mid++;
} else {
swap(nums[mid], nums[high]);
high--;
}
}
}
1 : Function Declaration
voidsortColors(vector<int>& nums) {
Declares a function `sortColors` that takes a vector of integers `nums` as input and sorts it in-place.
2 : Variable Initialization
int n = nums.size();
Initializes a variable `n` to store the size of the input array.
3 : Variable Initialization
int low =0, mid =0, high = n -1;
Initializes three pointers: `low`, `mid`, and `high`. `low` points to the next position for a 0, `mid` is the current element being considered, and `high` points to the next position for a 2.
4 : Loop Iteration
while (mid <= high) {
Starts a `while` loop that continues as long as `mid` is less than or equal to `high`.
5 : Conditional
if (nums[mid] ==0) {
Checks if the current element at `mid` is 0.
6 : Swap
swap(nums[low], nums[mid]);
Swaps the element at `mid` with the element at `low`.
7 : Increment
low++;
mid++;
Increments both `low` and `mid` pointers.
8 : Conditional
} elseif (nums[mid] ==1) {
Checks if the current element at `mid` is 1.
9 : Increment
mid++;
Increments the `mid` pointer to the next element.
10 : Conditional
} else {
If the current element at `mid` is 2.
11 : Swap
swap(nums[mid], nums[high]);
Swaps the element at `mid` with the element at `high`.
12 : Decrement
high--;
Decrements the `high` pointer.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The algorithm has a linear time complexity of O(n) because we traverse the array once using the three-pointer approach.
Best Case: O(1)
Worst Case: O(1)
Description: The algorithm uses only constant extra space, as the sorting is done in-place.
