Java AC one pass solution, use 3 pointers


  • 0
    H

    public class Solution {
    public void sortColors(int[] nums) {

        //Algo thinking: two pass, first pass count 0s, 1s, 2s, second pass fill array with respect to counts
        //Better: use 3 pointers, left, right, i
        
        int left = 0, i = 0, right = nums.length - 1;
        while (i <= right) {
            if (nums[i] == 0) {
                swap(nums, i++, left++); // loop invariant: left either points to 0 or 1, so after swap, i++
            } else if (nums[i] == 2) {
                swap(nums, i, right--);
            } else {    // nums[i] == 1
                i ++;
            }
        }
    }
    
    private void swap(int[] a, int i, int j) {
        int t = a[i]; a[i] = a[j]; a[j] = t;
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.