By Long Luo

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

Here are \(3\) approaches to solve this problem in Java, which is Brute Force, HashMap and Sliding Window.

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(n^2)\)
• Space Complexity: \(O(1)\)

HashMap

We use a \(\texttt{HashMap}\) to record the maximum index of each element. When scanning the array from left to right, the process:

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

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

The order of the above two-step operations cannot be changed, when the index \(i\) 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 \(i\).

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)\)
• Space Complexity: \(O(n)\)

Sliding Window

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

If the sliding window has repeated elements, then there are two different index \(i\) and \(j\) such that \(\textit{nums}[i] = \textit{nums}[j]\) and \(i - 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 > k\), the element whose index is \(i - k - 1\) will be removed from the sliding window.

If a element already exists in the \(\texttt{HashSet}\), there are duplicate elements, return \(\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)\).
• Space Complexity: \(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. 😉😃💗