LeetCode 75. Sort Colors

, , , , , ,

Question

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. Sort it in O(n) time.

Example

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

Solution

(1) we want to move the 0’s to the left side and then we set the left pointer (which prepares to move if meet the condition). We do the same thing for 2’s. So, there would be two-pass solution.

(2) we also can achieve the one pass solution for using three pointers (index for unclassified elements, smaller for 0’s and larger for 2’s)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// two pass. Time:O(n), Space:O(1)
public void sortColors(int[] nums) {
        if (nums == null || nums.length == 0) return;
        int n = nums.length;
        int pivot = 1;
        int left = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] < pivot) {
                exch(nums, left++, i);
            }
        }
        
        int right = n - 1;
        for (int i = n - 1; i >= 0; i--) {
            if (nums[i] > pivot) {
                exch(nums, i, right--);
            }
        }
    }
public void exch(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

// one pass. Time:O(n), Space:O(1)
public void sortColors2(int[] nums) {
        if (nums == null || nums.length == 0) return;
        int n = nums.length;
        int pivot = 1;
        int smaller = 0;
        int larger = n - 1;
        int index = 0;
        while (index <= larger) {
            if (nums[index] > pivot) {
                exch(nums, index, larger--);
            } else if (nums[index] < pivot) {
                exch(nums, index++, smaller++);
            } else {
                index++;
            }
        }
    }