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

By Long Luo

This article is the solution 3 Approaches: Brute Force, HashMap and Sliding Window of Problem 219. Contains Duplicate II.

Here are 33 approaches to solve this problem in Java, which is Brute Force, HashMap and Sliding Window.

Brute Force

Easy, using 22 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\texttt{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 abs(ij)kabs(i - j) \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\texttt{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. 😉😃💗