![Sort Colors Leetcode Problem 75 [Python Solution]](https://auditorical.com/wp-content/uploads/2023/10/Sort-Colors-Leetcode-Problem-75-Python-Solution-1.webp)
Sort Colors Leetcode Problem 75 [Python Solution]
Under the category of Arrays and Hashing, with a medium difficulty level, Sort Colors Leetcode problem is a great problem to understand and practice various sorting techniques.
Let’s dive into the details.
Problem Overview
Question: 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 colors 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. Now that we understand the problem, let’s explore the various solutions.
Problem Solutions
Bruteforce Approach
One way to solve this problem is to use a bruteforce approach by simulating the process.
We can iterate through the nums array and, for each element, determine its color and move it to its appropriate position.
This approach, however, is not the most efficient.
Here’s a Python code snippet that demonstrates this approach:
def sortColors(nums):
low = 0
high = len(nums) - 1
mid = 0
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], nums[high] = nums[high], nums[mid]
high -= 1
return nums
This code iterates through the array, moving zeros to the left and twos to the right, while ones naturally fall into place.
Although this approach is correct, it’s not the most efficient way to solve the problem.
Efficient Approach
Now, let’s discuss the more efficient one-pass solution.
The idea here is to maintain three pointers: left, right, and i.
The left pointer keeps track of the position where the next 0 should go, the right pointer keeps track of the position where the next 2 should go, and the i pointer iterates through the array.
We follow these steps:
1. Initialize left to 0 and right to the end of the array (length of nums - 1).
2. Iterate through the array using the i pointer.
3. If nums[i] is 0, we swap it with the element at the left pointer and increment left.
4. If nums[i] is 2, we swap it with the element at the right pointer and decrement right.
5. If nums[i] is 1, we leave it in place.
6. Continue until i is greater than right.
Here’s the Python code that implements this efficient approach:
def sortColors(nums):
left = 0
right = len(nums) - 1
i = 0
while i <= right:
if nums[i] == 0:
nums[left], nums[i] = nums[i], nums[left]
left += 1
i += 1
elif nums[i] == 2:
nums[i], nums[right] = nums[right], nums[i]
right -= 1
else:
i += 1
return nums
This solution has a time complexity of O(n) as it processes the array in a single pass and places each element in its correct position, ensuring the desired sorting.
Time and Space Complexity
Time Complexity: The efficient approach has a time complexity of O(n), where n is the length of the nums array.
It iterates through the array once, performing swaps and updates along the way.
Space Complexity: The space complexity is O(1) because we only use a constant amount of extra space to maintain the left, right, and i pointers.
Reasoning Behind Our Approach
The efficient approach leverages the concept of a Dutch National Flag.
By maintaining three pointers (left, right, and i), we can partition the array into three sections, each corresponding to a color: 0, 1, and 2.
We use these pointers to keep track of the positions where the next element of each color should go.
This approach is highly efficient, as it sorts the array in a single pass, without the need for additional data structures.
It minimizes unnecessary operations and achieves the desired sorting result.
Related Interview Questions By Company:
Related Interview Questions By Difficulty:
- Word Pattern LeetCode
- Push Dominoes LeetCode
- Find The Index Of The First Occurrence In A String LeetCode
Related Interview Questions By Category:
Conclusion
In this blog post, we’ve tackled the Sort Colors problem from LeetCode.
We discussed both a bruteforce approach and a more efficient one-pass solution.
The efficient approach leverages the Dutch National Flag algorithm to sort the array in linear time, which is an optimal solution for this problem.
If you found this guide helpful, please like and engage to support the our platform.
If you have any questions, suggestions, or comments, feel free to share them below.
Sorting problems are fundamental in computer science, and mastering them is a valuable skill for any programmer.
Happy coding!
