22ms Java straight-forward sorting solution beats 87.92% solutions, surprisingly fast


  • 3
    Y

    This is my first thought on this problem, sort the input with index info saved and search as far as the value difference is less than or equal to k. For worst case scenario, the search would be O(n^2), but this solution is surprisingly fast, my thought would be the test cases are not covering the case that all the input is within the value difference of k.

    public class Solution {
        
        class Pair {
            int val;
            int index;
            Pair(int v, int i) {
                this.val = v;
                this.index = i;
            }
        }
        
        public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
            if (nums == null || nums.length < 2 || t < 0 || k < 1) {
                return false;
            }
            int len = nums.length;
            Pair[] pair = new Pair[len];
            for(int i = 0; i < len; i++) {
                pair[i] = new Pair(nums[i], i);
            }
            
            Arrays.sort(pair, new Comparator<Pair> () {
              public int compare(Pair p1, Pair p2) {
                  return p1.val - p2.val;
              } 
            });
            
            for(int i = 0; i < len; i++) {
                for(int j = i + 1; j < len && Math.abs((long)pair[j].val - (long)pair[i].val) <= (long)t; j++){
                    int indexDiff = Math.abs(pair[i].index - pair[j].index);
                    if (indexDiff <= k) {
                        return true;
                    }
                }
            }
            return false;
        }
    }

  • 0
    J

    my thought would be the test cases are not covering the case that all the input is within the value difference of k. (I think it's your typo that it should be " t ")

    I don't think so. When the difference between any two nums is <= t, you will return true on nums[0] and nums[1].


  • 0
    H
    This post is deleted!

  • 0
    2

    How could it run such fast? Because it implements random?


  • 0
    L

    TLE if I put the check of two values' difference inside the for loop as below. What's the reason?

    for(int i=0; i<data.length; i++){
        for(int j=i+1; j<data.length; j++){
           if(Math.abs((long)data[j].val - (long)data[i].val)<=(long)t && Math.abs(data[j].ind-data[i].ind)<=k) {
                return true;
            }
        }
    }
    

  • 0
    Z
     for(int i = 0; i < len; i++) {
            for(int j = i + 1; j < len && Math.abs((long)pair[j].val - (long)pair[i].val) <= (long)t; j++){
                int indexDiff = Math.abs(pair[i].index - pair[j].index);
                if (indexDiff <= k) {
                    return true;
                }
            }
        }
    

    Can we do this part in O(n)? like using two pointers. That way, this solution has time complexity of O(nlogn).


Log in to reply
 

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