75. Sort Colors (https://leetcode.com/problems/sort-colors/): 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…

75. Sort Colors (#1 Two pointer).java

// Two pointer solution
// Time: O(n), 0ms
// Space: O(1), 35.1mb
class Solution {
    public void sortColors(int[] nums) {
        // 2 pointers: [0, l) - 0, [l, r] - 1, [r, nums.length - 1] - 2
        // m for traversing
        int l = 0, r = nums.length - 1, m = 0;
        
        while(m <= r) {
            if(nums[m] == 1) {
                m++;
                
            } else if(nums[m] == 0) {
                // Swap with l
                nums[m] = nums[l];
                nums[l] = 0;
                l++;
                m++;
                // !!: No need to check the new nums[m] because there won't be any 2 in range [0, m)
                // !!: New nums[m] won't be 0 if m > l (l stops where there is a 1)
                
            } else { // nums[m] == 2
                // Swap with r
                nums[m] = nums[r];
                nums[r] = 2;
                r--;
                // !!: No m++ because we need to check the value of the swapped one
                
            }
        }
    }
}