Buggy quicksort solution accepted


  • 0

    This code have been accepted,

    public boolean containsNearbyDuplicate(int[] nums, int k) {
        if (nums.length == 0)
            return false;
        int[] indices = new int[nums.length];
        for (int i = 0; i < nums.length; ++i) {
            indices[i] = i;
        }
        quicksort(nums, indices, 0, nums.length);
        for (int i = 1; i < nums.length; ++i) {
            if (nums[i - 1] == nums[i] && Math.abs(indices[i - 1] - indices[i]) <= k)
                return true;
        }
        return false;
    }
    
    private void quicksort(int[] nums, int[] indices, int start, int end) {
        if (end - start > 1) {
            int p = partition(nums, indices, start, end);
            quicksort(nums, indices, start, p);
            quicksort(nums, indices, p + 1, end);
        }
    }
    
    private int partition(int[] nums, int[] indices, int start, int end) {
        int p = start + (end - start) / 2;
        int pivot = nums[p];
        for (int i = start, j = end - 1; ; ) {
            while (nums[i] < pivot) {
                ++i;
            }
            while (nums[j] > pivot) {
                --j;
            }
            if (i < j && nums[i] != nums[j]) {
                nums[i] ^= nums[j];
                indices[i] ^= indices[j];
                nums[j] ^= nums[i];
                indices[j] ^= indices[i];
                nums[i] ^= nums[j];
                indices[i] ^= indices[j];
            } else {
                return i;
            }
        }
    }
    

    but it's obviously bugged:

    1. The partition algorithm doesn't always work correctly, sometimes even throwing exceptions.

    2. More importantly, the very idea is wrong: you can't just sort these numbers by value, you need to also sort equal numbers by their original indices, otherwise you may end up with false negatives, like in the following example:

       int[] nums = new int[14];
       for (int i = 0; i < 14; ++i) {
           nums[i] = i;
       }
       nums[13] = nums[5] = nums[6] = 0;
       System.out.println(new BuggyDuplicate2().containsNearbyDuplicate(nums, 1));
      

    This prints false, although it should obviously print true. At least this test should be added, possibly more to detect various cases where sorting algorithms may not sort correctly due to bugs.


  • 0

    Thanks, I have just published your test case and the incorrect solution should not get Accepted again.


Log in to reply
 

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