75: Sort-Colors
Medium
table of contents
I swear I have solved this problem before…
Anyways, the intuition for this solution is, as long as we place the
0
’s and 2
’s in the correct position, the
remaining 1
’s will naturally end up in the correct position
as well.
Then, since 0
’s always end up at the start of
nums
and 2
’s always end up at the end
of nums
, we can initialize two pointers to
track where we should be placing 0
s and 1
s:
start
and end
.
Now, all we need to do now is iterate between 0
and
end
inclusively (since all the values past
end
are all 2
’s, there is no need to
iterate through them). During each iteration i
,
Then, our colours will be sorted in-place.
code
class Solution {
public:
void sortColors(vector<int>& nums) {
int start = 0, end = nums.size()-1;
for (int i = 0; i <= end; ++i) {
while (i < end && nums[i] == 2) {
(nums[i], nums[end]);
swap--end;
}
if (nums[i] == 0) {
if (i != start) {
(nums[i], nums[start]);
swap}
++start;
}
}
}
};