[Leetcode][219. Contains Duplicate II] 3 Solutions: Brute Force, HashMap and Sliding Window

By Long Luo

This article is the solution of Problem 219. Contains Duplicate II.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
219. Contains Duplicate II

Easy

Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.

Example 1:
Input: nums = [1,2,3,1], k = 3
Output: true

Example 2:
Input: nums = [1,0,1,1], k = 1
Output: true

Example 3:
Input: nums = [1,2,3,1,2,3], k = 2
Output: false

Constraints:
1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
0 <= k <= 10^5

Brute Force

Easy, using 2 loops to determine whether there is the same number.

obviously, it will time out.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean containsNearbyDuplicate(int[] nums, int k) {
if (nums == null || nums.length <= 1 || k <= 0) {
return false;
}

int len = nums.length;
for (int i = 0; i < len; i++) {
for (int j = i + 1; j < len; j++) {
if (nums[i] == nums[j]) {
if (Math.abs(i - j) <= k) {
return true;
}
}
}
}

return false;
}

Analysis

  • Time Complexity: O(n2)O(n^2)
  • Space Complexity: O(1)O(1)

HashMap

We use a HashMap to record the maximum index of each element. When scanning the array from left to right, the process:

  • If an element nums[i]\textit{nums}[i] already exists in the hash table and the index jj of the element recorded in the hash table satisfies ijkij \le k, return true\text{true};

  • Recording nums[i]\textit{nums}[i] and index ii into the hash table, where ii is the largest index of nums[i]\textit{nums}[i].

The order of the above two-step operations cannot be changed, when the index ii is traversed, the element equal to the current element and the maximum index of the element can only be found in the elements before the index ii.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public boolean containsNearbyDuplicate(int[] nums, int k) {
if (nums == null || nums.length <= 1 || k <= 0) {
return false;
}

int len = nums.length;
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < len; i++) {
if (map.containsKey(nums[i])) {
int idx = map.get(nums[i]);
if (Math.abs(i - idx) <= k) {
return true;
}
map.put(nums[i], i);
} else {
map.put(nums[i], i);
}
}

return false;
}

Analysis

  • Time Complexity: O(n)O(n)
  • Space Complexity: O(n)O(n)

Sliding Window

Maintain a sliding window whose length does not exceed k+1k+1 in the array nums\textit{nums}, and the abs value of any two index delta in the same sliding window does not exceed kk.

If the sliding window has repeated elements, then there are two different index ii and jj such that nums[i]=nums[j]\textit{nums}[i] = \textit{nums}[j] and ijki - j \le k.

If there are no repeating elements in the sliding window, there is no index that meets the requirements.

Therefore, it is only necessary to traverse each sliding window and determine whether there are duplicate elements in the sliding window.

We use a HashSet to store the elements in the sliding window.

If i>ki > k, the element whose index is ik1i-k-1 will be removed from the sliding window.

If a element already exists in the HashSet, there are duplicate elements, return true\textit{true}, if not in the hash set add it to the hash set.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public boolean containsNearbyDuplicate(int[] nums, int k) {
if (nums == null || nums.length <= 1 || k <= 0) {
return false;
}

int len = nums.length;
Set<Integer> set = new HashSet<>();
for (int i = 0; i < len; i++) {
if (i > k) {
set.remove(nums[i - k - 1]);
}

if (set.contains(nums[i])) {
return true;
} else {
set.add(nums[i]);
}
}

return false;
}

Analysis

  • Time Complexity: O(n)O(n).
  • Space Complexity: O(k)O(k).

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗