Given an array nums with n objects colored red, white, or blue, sort them in-place so…
- User
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? i want to do question by using hastable in thisfirst set all the varibles to 1 and then iteratie through nums array and then mark all those value of array to 0 in arr and then print the values
- Assistant
Certainly! You can solve the problem by using a hash table (in Python, a dictionary) to count the occurrences of each color (0, 1, and 2) and then overwrite the original
numsarray based on these counts. Here's a step-by-step guide to achieve this:-
Initialize a Hash Table:
- Create a dictionary to store the count of each color. Initialize the counts to
0for each color (0, 1, and 2).
- Create a dictionary to store the count of each color. Initialize the counts to
-
Count the Occurrences:
- Iterate through the
numsarray and increment the count corresponding to each color in the hash table.
- Iterate through the
-
Overwrite the Original Array:
- Modify the
numsarray by writing the correct number of 0s, followed by 1s, and then 2s based on the counts stored in the hash table.
- Modify the
-
Print the Result:
- After modifying the
numsarray in-place, you can print or return it as the sorted array.
- After modifying the
Here's how you can implement this approach in Python:
def sortColors(nums): # Step 1: Initialize the hash table with counts for each color color_counts = {0: 0, 1: 0, 2: 0} # Step 2: Count the occurrences of each color for num in nums: if num in color_counts: color_counts[num] += 1 else: # This case shouldn't occur as per the problem constraints raise ValueError(f"Invalid color value found: {num}") # Step 3: Overwrite the original nums array based on the counts index = 0 for color in [0, 1, 2]: count = color_counts[color] for _ in range(count): nums[index] = color index += 1 # The nums array is now sorted in-place return nums # Optional, since the sorting is in-place # Example Usage: nums1 = [2, 0, 2, 1, 1, 0] sorted_nums1 = sortColors(nums1) print(sorted_nums1) # Output: [0, 0, 1, 1, 2, 2] nums2 = [2, 0, 1] sorted_nums2 = sortColors(nums2) print(sorted_nums2) # Output: [0, 1, 2]Explanation of the Code:
-
Initialization:
color_counts = {0: 0, 1: 0, 2: 0}initializes a dictionary to keep track of the count of each color.
-
Counting Occurrences:
- The
forloop iterates over each number innumsand increments the corresponding count incolor_counts. - An error is raised if an unexpected value is found, ensuring the input adheres to the constraints.
- The
-
Overwriting the Array:
- The variable
indexkeeps track of the current position in thenumsarray. - The outer
forloop iterates over the colors in the desired order: 0, then 1, then 2. - The inner
forloop writes the appropriate number of each color back intonums.
- The variable
-
Result:
- The original
numsarray is modified in-place to reflect the sorted order. - The function also returns the sorted array for convenience, but this is optional since the sorting is done in-place.
- The original
Time and Space Complexity:
-
Time Complexity: O(n), where n is the length of the
numsarray. The array is traversed twice—once for counting and once for overwriting. -
Space Complexity: O(1), since the size of the
color_countsdictionary is fixed (it always contains exactly three keys: 0, 1, and 2), regardless of the input size.
Alternative Approach: One-Pass Algorithm (Dutch National Flag)
While the hash table method is effective and easy to understand, you can also solve this problem in a single pass using the Dutch National Flag algorithm, which uses only constant extra space. Here's how you can implement it:
def sortColorsOnePass(nums): low, mid, high = 0, 0, len(nums) - 1 while mid <= high: if nums[mid] == 0: # Swap nums[low] and nums[mid] nums[low], nums[mid] = nums[mid], nums[low] low += 1 mid += 1 elif nums[mid] == 1: mid += 1 else: # Swap nums[mid] and nums[high] nums[mid], nums[high] = nums[high], nums[mid] high -= 1 return nums # Optional # Example Usage: nums1 = [2, 0, 2, 1, 1, 0] sorted_nums1 = sortColorsOnePass(nums1) print(sorted_nums1) # Output: [0, 0, 1, 1, 2, 2] nums2 = [2, 0, 1] sorted_nums2 = sortColorsOnePass(nums2) print(sorted_nums2) # Output: [0, 1, 2]How It Works:
-
Pointers:
low: Position to place the next 0.mid: Current element under consideration.high: Position to place the next 2.
-
Logic:
- If the current element (
nums[mid]) is 0, swap it withnums[low]and move bothlowandmidpointers forward. - If it's 1, just move the
midpointer forward. - If it's 2, swap it with
nums[high]and move thehighpointer backward (without movingmidbecause the swapped element needs to be evaluated).
- If the current element (
This method ensures that all 0s are moved to the beginning, 2s to the end, and 1s remain in the middle, achieving the desired sorting in a single traversal with constant space.
Conclusion
Both methods effectively sort the array with the required constraints. The hash table approach is straightforward and easy to implement, especially when dealing with a small fixed number of distinct elements. The Dutch National Flag algorithm is more efficient in terms of the number of passes and is ideal for scenarios where in-place and one-pass solutions are preferred.
-