No swap needed


  • 0

    I was reviewing for an onsite interview and encountered this question. The requirement is to use as little swap function as possible. This solution uses 0 swap. It greedly set each position to 2 and reset it back if 0's or 1's were found.
    Here, i is the next position for 1, j is the next position for 0.

        public void sortColors(int[] nums) {
            if (nums == null || nums.length == 0) return;
            for (int i = 0, j = 0, k = 0; k < nums.length; k++) {
                int tmp = nums[k];
                nums[k] = 2;
                if (tmp < 2) nums[i++] = 1;
                if (tmp < 1) nums[j++] = 0;
            }
        }
    

  • 0
    S

    it looks like a dp solution and it is really smart solution.


Log in to reply
 

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