Sort Colors | LeetCode 75 | C

2023-09-07
#LeetCode #C #Array #Two Pointers #Sorting
LeetCode

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:

1
2
Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Example 2:

1
2
Input: nums = [2,0,1]
Output: [0,1,2]

Constraints:

1
2
3
n == nums.length
1 <= n <= 300
nums[i] is either 0, 1, or 2.

Approach

1
Use two pointers to keep 0 and 2 at the beginning and the end of the array.

Algorithm

1
2
3
1. Go through the list. If encounter 2, swap the current element and the right element. Move the right pointer to the left.
2. If encounter 2, swap the current element and the left element. Move the left pointer to the right. Mover the current pointer to the right too.
3. If the current element is neither 0 nor 2, move the current pointer to the right only.

Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void swap(int* nums, int x, int y) {
    int temp = nums[x];
    nums[x] = nums[y];
    nums[y] = temp;
}
void sortColors(int* nums, int numsSize){
    int left = 0, right = numsSize - 1, curr = 0;
    int temp;
    while(curr<=right){
        if(nums[curr] == 0)
        {
            swap(nums, left, curr);
            curr++;
            left++;
        }
        else if (nums[curr] == 2)
        {
            swap(nums, right, curr);       
            right--;
        }
        else
            curr++;
    }
}