75. Sort Colors

Source link: https://leetcode.com/problems/sort-colors/

Design

[2,0,2,1,1,0] → [0,0,1,1,2,2]

  1. Traverse through the array, and initialize three pointers start, end and index. The pointer idx stores the index of current element, and both the others are responsible for recording the start and end position.
  2. If the current value equals to 0, swap it with the element where pointer start at. Then move both pointers start and idx forward.
  3. If the current value equals to 2, swap it with the element where pointer end at. Then move only the pointer end backward. The reason why the pointer idx not moving forward is because when both elements where pointers idx and end at are 2, the first 2 would be missing.
  4. If the current value equals to 1, just simply move the pointer idx forward.

Implementation

class Solution {
  public void sortColors(int[] nums) {
    if (nums.length == 0 || nums.length == 1) return;
    int start = 0, end = nums.length - 1, index = 0;
    while (index <= end) {
      if (nums[index] == 0) {
        nums[index] = nums[start];
        nums[start] = 0;
        start++;
        index++;
      } else if (nums[index] == 2) {
        nums[index] = nums[end];
        nums[end] = 2;
        end--;
      } else {
        index++;
      }
    }
  }
}

Complexity Analysis

Time: $O(n)$

Space: $O(1)$