a trick to help understanding


  • 0
    F

    This post provides excellent explanation.

    Basically for the sort color problem, we maintain the following invariant:

    // [0, left), [left, i), [i, right], (right, length)
    //  0,          1,         unknown,   2
    

    So, my trick is printing the pointers after each iteration programmably:

    public class Solution {
        public void sortColors(int[] nums) {
            if (nums == null || nums.length == 0) return;
            int left = 0;
            int right = nums.length - 1;
            for (int i = 0; i <= right;) {
                if (nums[i] == 0) {
                    swap(nums, i, left);
                    left += 1;
                    i += 1;
                } else if (nums[i] == 2) {
                    swap(nums, i, right);
                    right -= 1;
                } else {
                    i += 1;
                }
    
                System.out.printf("array  : %s\n", Arrays.toString(nums));
                char[] p = new char[nums.length];
                Arrays.fill(p, ' ');
                if (i < nums.length) p[left] = 'L';
                if (i < nums.length) p[i] = 'i';
                if (right >= 0) p[right] = 'R';
                System.out.printf("pointer: %s\n\n", Arrays.toString(p));
            }
            
        }
        
        private void swap(int[] nums, int left, int right) {
            int tmp = nums[left];
            nums[left] = nums[right];
            nums[right] = tmp;
        }
    }
    

    For the example [1,0,2,2,1,0] in that post, the printing is:

    array  : [1, 0, 2, 2, 1, 0]
    pointer: [L, i,  ,  ,  , R]
    
    array  : [0, 1, 2, 2, 1, 0]
    pointer: [ , L, i,  ,  , R]
    
    array  : [0, 1, 0, 2, 1, 2]
    pointer: [ , L, i,  , R,  ]
    
    array  : [0, 0, 1, 2, 1, 2]
    pointer: [ ,  , L, i, R,  ]
    
    array  : [0, 0, 1, 1, 2, 2]
    pointer: [ ,  , L, R,  ,  ]
    
    array  : [0, 0, 1, 1, 2, 2]
    pointer: [ ,  , L, R, i,  ]
    

    Using this trick, we could use different inputs and check the printings to help understanding the invariant we want to keep.


Log in to reply
 

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