# 18 ms Java solution using HashMap and sort

• 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;``````

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

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

• 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).

• 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

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