/ Data Structure and Algorithms  

Leetcode 75. Sort Colors

Question



Give an array containing only 0, 1, and 2, sort the numbers from small to large.

Similar Questions

Solution 1

A very straightforward method. Requires 2 iterations. During first iteration, count the number of occurrences of 0, the number of occurrences of 1, and the number of occurrences of 2. During second iteration, traverse the array and change the elements of the array to the corresponding values according to the number of occurrences. Of course we only need to record 0 and 1, and the rest is 2.

Time complexity O(n), space complexity O(1).

Solution 2

Solution 1 requires 2 iterations. Can we do better in only 1 iteration?

Suppose the array only have number 0 and 1 (e.g, 1 0 1 1 0). We can use a pointer, zero_position, meaning the positions before this pointer are 0. Then use a pointer i to traverse the array, find 0 and put 0 to the position pointed by zero_position, and move zero_position forward. Let Z be zero_position and see the traversal process below.

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
1 0 1 1 0   Initialize Z,i point to position 0，move forward i
^
Z
i

1 0 1 1 0   Find 0，exchange value at Z and i, move forward Z
^ ^
Z i

0 1 1 1 0   Move forward i
  ^
  i
  Z

0 1 1 1 0  Move forward i
  ^ ^
  Z i

0 1 1 1 0  Move forward i
  ^   ^
  Z   i

0 1 1 1 0  Found 0，exchange value at Z and i, move forward Z
  ^     ^
  Z     i

0 0 1 1 1  Finish
    ^   ^
    Z   i

Now We have 3 numbers, so we can use two pointers, one is zero_position. As before, all the positions before it are all 0. Another pointer, two_position. All the positions after it are all 2.

1
2
3
0 1 0 2 1 2 2 2
  ^ ^   ^
  Z i   T
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
// elements before this are all '0'
int zeroIndex = 0;
// elements after this are all '2'
int twoIndex = nums.length - 1;

for (int i = 0; i <= twoIndex; i++) {
    if (nums[i] == 0) {
        // exchange zeroIndex with i
        int temp = nums[zeroIndex];
        nums[zeroIndex] = nums[i];
        nums[i] = temp;

        // move forward zeroIndex
        zeroIndex++;
    } else if (nums[i] == 2) {
        // exchange twoIndex with i
        int temp = nums[twoIndex];
        nums[twoIndex] = nums[i];
        nums[i] = temp;

        // move backward twoIndex
        twoIndex--;
        // Note here since we exchanged the number after index i
        // We haven't check this number yet. It will be skipped
        // So we need i--, to check this number
        i--;
    }
}

Time complexity O(n), space complexity O(1).