18 ms Java solution using HashMap and sort


  • 0
    L

    In the first iteration, record the position of each number. Sort the array and check if close numbers have close indices.

    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i]) && 
                0 <= t && i - map.get(nums[i]) <= k) {
                return true;
            }
            map.put(nums[i], i);
        }        
        
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] - nums[i] > 0 && nums[j] - nums[i] <= t) {
                    if (Math.abs(map.get(nums[j]) - map.get(nums[i])) <= k) {
                        return true;
                    }
                } else {
                    break;
                }
            }
        }
        return false;

  • 0
    L

    I was wondering why you use the last index of duplicated elements as the value of the hashmap.


  • 0
    M

    @liang54 The last index is stored as there is a window size k.


  • 0
    A

    I like it, but the asymptotic running time and space are not ideal.

    You have O(n * log n) time from the sort, and then O(n * t) for the index checking.

    For example on inputs:
    0,5,10,15,20,1,6,11,16,21,2,7,12,17,22, ..., 4,9,14,19,24
    0,2,4,6,..., 98, 1,3,5,7,..., 99
    t=100,k=1
    your output is false but you end up with O(n^2) time when testing indices in the sorted array
    0,1,2,..., 99

    In addition, you are using O(n) space, when I believe you can do this problem in O(k) space (which is likely to be small).


  • 2
    O

    Your solution fails for the following example, because you are storing only the last index of the duplicated element:
    [3,4,500,800,3]
    1
    2


Log in to reply
 

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