Share my 1-pass in-place java solution with detailed explanation


  • 3
    M
    public class Solution {
        public void sortColors(int[] nums) {
            if (nums==null || nums.length<2) { return; }
            int i=0, j=0, k=nums.length-1;
            while (j <= k) {
                if (nums[j] == 0) { swap(nums, i++, j++); }  // should swap with whatever at index i; note that i++ AND j++
                else if (nums[j] == 1) { ++j; }
                else { swap(nums, j, k--); }  // nums[j]==2, should swap with whatever at index k, then --k 
            }
        }
        
        private void swap(int[] nums, int i, int j) {
            int save = nums[i];
            nums[i] = nums[j];
            nums[j] = save;
        }
    }
    

    Define [0, i) -- all 0s; [i, j) -- all 1s; 
    (k, nums.length-1] all 2s; [j, k] -- unexplored segment.
    We are moving pointer j.
    
    if nums[j]==0, by definition we should swap nums[j] with nums[i]. 
    this 0 comes to index i, so i++ is needed;
    the number previously at index i comes to index j, again, by definition, it must be 1
    (remember? [i,j) are all 1s...), so j++ is needed.
    
    if nums[j]==1, ++j of course.
    
    if nums[j]==2, by definition we should swap nums[j] with nums[k].
    this 2 comes to index k, so k-- is needed;
    the number previously at index k comes to index j, but this time, 
    we do not know what it is, so j holds its position.

  • 0
    B

    Thanks for the explanation!


Log in to reply
 

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