75. Sort Colors
Medium
Topics: Array
, Two Pointers
, Sorting
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 either0
,1
, or2
.
Follow-up: Could you come up with a one-pass algorithm using only constant extra space?
Hint:
- A rather straight forward solution is a two-pass algorithm using counting sort.
- Iterate the array counting number of 0's, 1's, and 2's.
- Overwrite array with the total number of 0's, then 1's and followed by 2's.
Solution:
To solve this problem, we can follow these steps:
The goal is to sort the array nums
with elements representing the colors red (0), white (1), and blue (2) in one pass, using constant extra space.
Approach:
The most efficient way to solve this problem is by using the Dutch National Flag algorithm, which is a one-pass algorithm with constant extra space. The idea is to use three pointers:
-
low
to track the position for the next 0 (red), -
mid
to traverse the array, -
high
to track the position for the next 2 (blue).
Algorithm:
-
Initialize three pointers:
-
low
at the start (0), -
mid
at the start (0), -
high
at the end (n-1) of the array.
-
-
Traverse the array with
mid
:- If
nums[mid]
is0
(red), swapnums[mid]
withnums[low]
, then increment bothlow
andmid
. - If
nums[mid]
is1
(white), movemid
to the next element. - If
nums[mid]
is2
(blue), swapnums[mid]
withnums[high]
and decrementhigh
.
- If
Continue until
mid
exceedshigh
.
This algorithm sorts the array in-place with a single pass.
Let's implement this solution in PHP: 75. Sort Colors
<?php
// Example usage:
$nums1 = [2, 0, 2, 1, 1, 0];
sortColors($nums1);
print_r($nums1); // Output: [0, 0, 1, 1, 2, 2]
$nums2 = [2,0,1];
sortColors($nums2);
print_r($nums2); // Output: [0,1,2]
?>
Explanation:
-
Initialization:
-
low
starts at the beginning (0
). -
mid
starts at the beginning (0
). -
high
starts at the end (n-1
).
-
-
Loop Through Array:
- If
nums[mid]
is0
, it swaps withnums[low]
because0
should be at the front. Both pointerslow
andmid
are then incremented. - If
nums[mid]
is1
, it is already in the correct position, so onlymid
is incremented. - If
nums[mid]
is2
, it swaps withnums[high]
because2
should be at the end. Onlyhigh
is decremented, whilemid
stays the same to check the swapped element.
- If
-
Completion:
- The loop continues until
mid
passeshigh
, ensuring that the array is sorted in the order of0
,1
, and2
.
- The loop continues until
This approach is optimal with O(n) time complexity and O(1) space complexity.
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!
If you want more helpful content like this, feel free to follow me:
Top comments (0)