[LeetCode] 75. Sort Colors

Posted on | In

Problem

Given an array 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.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note: You are not suppose to use the library’s sort function for this problem.

Example:

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

Follow up:

  • A rather straight forward solution is a two-pass algorithm using counting sort. First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2’s.
  • Could you come up with a one-pass algorithm using only constant space?

Explanation

  1. We can use two pointer method to solve this problem. First, we delcare a redPointer points at the beginning, and a bluePointer points at the end index. Now, iterate from the beginning, if the element is red (0), then we swap it with the element that redPointer points at, redPointer moving forward. If the element is blue (2), then we swap it with the element that the bluePointer points at, bluePointer moving backward.

  2. One corner case is when the element that the blue pointer points at is red (0), when iterating, if the current iterated element is blue (2), then we swap it with the red (0), now the iterator shouldn’t move to the next, it should check this iterated current element again and move the red (0) element to the correct position.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    void swap(int[] nums, int p, int i) {
        int temp = nums[p];
        nums[p] = nums[i];
        nums[i] = temp;
    }
    public void sortColors(int[] nums) {
        int redPointer = 0;
        int bluePointer = nums.length-1;
        for (int i = 0; i <= bluePointer; i++) {
            if (nums[i] == 0) {
                swap(nums, redPointer, i);
                redPointer += 1;
            }
            if (nums[i] == 2) {
                swap(nums, bluePointer, i);
                bluePointer -= 1;
                i -= 1;
            }
        }
    }
}