Reference: LeetCode
Difficulty: Easy

Problem

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

Example:

1
2
3
4
5
6
7
8
9
10
11
Input: nums = [1,2,3,1], k = 3 (diff = 3)
Output: true

Input: nums = [1,2,3,3], k = 3 (diff = 1)
Output: true

Input: nums = [1,0,1,1], k = 1 (diff = 2)
Output: true

Input: nums = [1,2,3,1,2,3], k = 2 (diff = 3)
Output: false

Analysis

Hash Map

Go through some cases that have duplicates, e.g. [1,0,1,1].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean containsNearbyDuplicate(int[] nums, int k) {
  int n = nums.length;
  Map<Integer, Integer> map = new HashMap<>(); // <nums[i], i>
  for (int i = 0; i < n; ++i) {
    if (map.containsKey(nums[i])) { // contains duplicate
      int diff = i - map.get(nums[i]);
      if (Math.abs(diff) <= k) return true;
    }
    map.put(nums[i], i); // if exists, always put the latest index
    // if the latest index (also closest) does not satisfy, the previous index is not possible to satisfy.

  }
  return false;
}

Time: $O(\min(N, k))$ since we don’t know how large k could be.
Space: $O(\min(N, k))$

Sliding Window (k-size set)

We can just use a hash set of size k. Whenever there is one more element, we remove the oldest element.

1
2
3
4
5
6
7
8
9
10
//  0  1  2  3  4
//  3  4  5  6  7
//  -------
//   k = 3,  so index 3 - 0 = 3 or 3 - 2 = 1, they are all <= 3 = k
// we always keep the size of the set as k

// Also, consider case [1 1 0 1] k = 3
//                      --- stops!
// Also, consider case [1 2 3 4 1 1 1] k = 3
//                      ----------- stops!
1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean containsNearbyDuplicate(int[] nums, int k) {
  int n = nums.length;
  Set<Integer> window = new HashSet<>();
  for (int i = 0; i < n; ++i) {
    if (window.contains(nums[i])) return true; // set always store elements within the range of k
    window.add(nums[i]);
    if (window.size() > k) {
      window.remove(nums[i - k]); // remove the oldest element
      // it is not possible that out-of-bound occurs, since the size of set > k indicates that we have at least go through k distinct elements.
    }
  }
  return false;
}

Time: $O(\min(N, k))$
Space: $O(\min(N, k))$