Skip to content

75. Sort Colors 👍

Approach 1: 3 pointers

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  void sortColors(vector<int>& nums) {
    int zero = -1;
    int one = -1;
    int two = -1;

    for (const int num : nums)
      if (num == 0) {
        nums[++two] = 2;
        nums[++one] = 1;
        nums[++zero] = 0;
      } else if (num == 1) {
        nums[++two] = 2;
        nums[++one] = 1;
      } else {
        nums[++two] = 2;
      }
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public void sortColors(int[] nums) {
    int zero = -1;
    int one = -1;
    int two = -1;

    for (final int num : nums)
      if (num == 0) {
        nums[++two] = 2;
        nums[++one] = 1;
        nums[++zero] = 0;
      } else if (num == 1) {
        nums[++two] = 2;
        nums[++one] = 1;
      } else {
        nums[++two] = 2;
      }
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
  def sortColors(self, nums: List[int]) -> None:
    zero = -1
    one = -1
    two = -1

    for num in nums:
      if num == 0:
        two += 1
        one += 1
        zero += 1
        nums[two] = 2
        nums[one] = 1
        nums[zero] = 0
      elif num == 1:
        two += 1
        one += 1
        nums[two] = 2
        nums[one] = 1
      else:
        two += 1
        nums[two] = 2

Approach 2: 2 pointers + swapping

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
 public:
  void sortColors(vector<int>& nums) {
    int l = 0;                // The next 0 should be placed in l.
    int r = nums.size() - 1;  // The next 2 should be placed in r.

    for (int i = 0; i <= r;)
      if (nums[i] == 0)
        swap(nums[i++], nums[l++]);
      else if (nums[i] == 1)
        ++i;
      else
        // We may swap a 0 to index i, but we're still not sure whether this 0
        // is placed in the correct index, so we can't move pointer i.
        swap(nums[i], nums[r--]);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
  public void sortColors(int[] nums) {
    int l = 0;               // The next 0 should be placed in l.
    int r = nums.length - 1; // THe next 2 should be placed in r.

    for (int i = 0; i <= r;)
      if (nums[i] == 0)
        swap(nums, i++, l++);
      else if (nums[i] == 1)
        ++i;
      else
        // We may swap a 0 to index i, but we're still not sure whether this 0
        // is placed in the correct index, so we can't move pointer i.
        swap(nums, i, r--);
  }

  private void swap(int[] nums, int i, int j) {
    final int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
  def sortColors(self, nums: List[int]) -> None:
    l = 0  # The next 0 should be placed in l.
    r = len(nums) - 1  # THe next 2 should be placed in r.

    i = 0
    while i <= r:
      if nums[i] == 0:
        nums[i], nums[l] = nums[l], nums[i]
        i += 1
        l += 1
      elif nums[i] == 1:
        i += 1
      else:
        # We may swap a 0 to index i, but we're still not sure whether this 0
        # is placed in the correct index, so we can't move pointer i.
        nums[i], nums[r] = nums[r], nums[i]
        r -= 1