219. Contains Duplicate II
Problem Description
The goal is to find out whether there is a pair of indices i
and j
in the given integer array nums
such that nums[i]
is equal to nums[j]
and the absolute difference between i
and j
is less than or equal to k
. This problem is checking for duplicates within a specified range of indices in an array. The crucial point here is that i
and j
must be distinct, which means you cannot compare an element with itself. If such a pair exists, then the correct output is true
; otherwise, false
.
Intuition
The intuitive approach for this problem uses a hash table to track the indices of elements we've already seen. As we iterate through the nums
array, we keep updating the hash table with the elements as keys and their indices as values. At each step, we look at the current element x
and check if it's already in the hash table. If it is, and the stored index is close enough to the current index (the difference is less than or equal to k
), then we've found the required pair, and we can immediately return true
. If there's no such element or the distance is too large, we simply keep the hash table updated by overwriting the index of the current element. After checking all elements, if no such pair is found, the function returns false
.
This approach is efficient as it only requires a single pass through the array, and the lookups and updates in the hash table are performed in constant time. Hence, the total time complexity is O(n), where n is the number of elements in the nums
array.
Learn more about Sliding Window patterns.
Solution Approach
The algorithm utilizes a hash table to implement the solution efficiently. The hash table stores elements from the array nums
as keys, and the most recent index at which each element occurs as the corresponding value.
We initiate the iteration through the array with a for
loop. At each step, we consider the current element and its index (i, x
fetched from enumerate(nums)
).
Here's the step-by-step implementation:
-
If the current element
x
already exists in the hash tabled
and the difference between the current indexi
and the previously stored index forx
(d[x]
) is less than or equal tok
, then we have found two indicesi
andj
(wherej
isd[x]
) that satisfy both conditions:nums[i] == nums[j]
andabs(i - j) <= k
. In this case, the function immediately returnstrue
. -
If the current element
x
does not satisfy the condition, or if it is not present in the hash table, it means we have not yet found a duplicate within the specified range. Therefore, we update the hash table with the current indexi
for elementx
:d[x] = i
. This step is crucial because it keeps the hash table updated with the latest index where each number is found, ensuring that when checking for the range condition, we are always using the smallest possible index difference. -
After iterating through all the elements in the array, if we have not returned
true
, it means no two indices satisfy the given conditions, and the function concludes by returningfalse
.
In summary, the hash table is essential to keep track of the indices of the elements we've seen, enabling us to check the existence of nearby duplicates in constant time. This approach leads to a linear time complexity, which is O(n), with n being the length of the array nums
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's take a small example to better understand the solution approach. Consider the array nums = [1, 2, 3, 1, 2, 3]
and let's say k = 2
. We want to find if there are any duplicates within an index range of 2.
-
We start with an empty hash table
d = {}
. -
We iterate through the nums array with index
i
and elementx
.a. At
i = 0
,x = 1
. We add1
to the hash table with its index:d = {1: 0}
.b. At
i = 1
,x = 2
. The hash table is now:d = {1: 0, 2: 1}
.c. At
i = 2
,x = 3
. The hash table updates to:d = {1: 0, 2: 1, 3: 2}
.d. At
i = 3
,x = 1
. The current element1
is already in the hash table. We check the index of the last occurrence of1
ind
, which is0
. The difference between the current index3
and the last index0
is 3 which is not less than or equal tok
. We updated
with the new index for1
:d = {1: 3, 2: 1, 3: 2}
.e. At
i = 4
,x = 2
. Again,2
is already in the hash table. The last occurrence was at index1
. The difference betweeni = 4
and1
is 3, which again, is not less than or equal tok
. We updated
:d = {1: 3, 2: 4, 3: 2}
.f. At
i = 5
,x = 3
. The3
is found in the hash table at index2
. The difference betweeni = 5
and2
is 3, which is also not less than or equal tok
. Updated
:d = {1: 3, 2: 4, 3: 5}
. -
After completing the iteration, we have not found any elements where the absolute difference in their indices was less than or equal to
k
. So, the function returnsfalse
.
Through this example, it's clear how the hash table d
is used to keep track of the indices of elements. Despite encountering duplicates, the conditions for k
were not satisfied, which the algorithm correctly identified.
Solution Implementation
1class Solution:
2 def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
3 # Initialize a dictionary to store the value as key and its index as value
4 index_map = {}
5
6 # Enumerate over the list to have both index and value
7 for index, value in enumerate(nums):
8 # If the value is in index_map, and the current index minus the
9 # stored index is less than or equal to k, a nearby duplicate exists
10 if value in index_map and index - index_map[value] <= k:
11 return True
12 # Update the index value in the index_map for each value
13 # It ensures that if the same value comes up again, the index_map stores
14 # the latest index, which is useful for distance calculation
15 index_map[value] = index
16
17 # Return False if no nearby duplicates found within the given k distance
18 return False
19```
20
21To ensure Python 3 syntax, especially for typing:
22- Make sure `List` is imported from `typing` module, which will be used for the type hint of the `nums` argument.
23
24Here is how you would include that import:
25```python
26from typing import List
27
28class Solution:
29 # the rest of the code remains the same as above
30
1import java.util.HashMap;
2import java.util.Map;
3
4class Solution {
5
6 public boolean containsNearbyDuplicate(int[] nums, int k) {
7 // Initialize a HashMap to store the value and its most recent index
8 Map<Integer, Integer> indexMap = new HashMap<>();
9
10 for (int currentIndex = 0; currentIndex < nums.length; ++currentIndex) {
11 // Use getOrDefault to find the last index of the current number.
12 // If it's not found, use a default value that is far away from any possible index.
13 int lastIndex = indexMap.getOrDefault(nums[currentIndex], -1000000);
14
15 // Check if the current index and the last index of the same value are within k steps
16 if (currentIndex - lastIndex <= k) {
17 // If so, we found a nearby duplicate and return true.
18 return true;
19 }
20
21 // Update the map with the current value and its index for the next iteration checks
22 indexMap.put(nums[currentIndex], currentIndex);
23 }
24
25 // If no nearby duplicates are found, return false.
26 return false;
27 }
28}
29
1#include <vector>
2#include <unordered_map>
3using namespace std;
4
5class Solution {
6public:
7 bool containsNearbyDuplicate(vector<int>& nums, int k) {
8 // Create a hashmap to store the most recent index of each value observed
9 unordered_map<int, int> valueToIndexMap;
10
11 for (int i = 0; i < nums.size(); ++i) {
12 // Check if the current value exists in the map, i.e., it has been encountered before
13 if (valueToIndexMap.count(nums[i])) {
14 // If the previous occurrence is within k indices from the current index, return true
15 if (i - valueToIndexMap[nums[i]] <= k) {
16 return true;
17 }
18 }
19 // Update the hashmap with the current index for this value
20 valueToIndexMap[nums[i]] = i;
21 }
22
23 // If no duplicate elements are within the given k indices, return false
24 return false;
25 }
26};
27
1// This function checks if there are any duplicates within 'k' indices apart in the array 'nums'
2function containsNearbyDuplicate(nums: number[], k: number): boolean {
3 // Create a map to keep track of the numbers and their indices
4 const indexMap: Map<number, number> = new Map();
5
6 // Iterate through the 'nums' array
7 for (let index = 0; index < nums.length; ++index) {
8 // Check if the current number is in the map and if the difference between
9 // the indices is less than or equal to 'k'
10 if (indexMap.has(nums[index]) && index - indexMap.get(nums[index])! <= k) {
11 return true; // Duplicate found within 'k' distance
12 }
13
14 // Update the index of the current number in the map
15 indexMap.set(nums[index], index);
16 }
17
18 // No duplicate found within 'k' distance
19 return false;
20}
21
Time and Space Complexity
The time complexity of the provided code is O(n)
because the code uses a single loop that iterates over the elements in 'nums' once. Inside the loop, the code performs constant time operations including checks in a dictionary and assignment.
The space complexity is also O(n)
as the code allocates a dictionary 'd' that could potentially store all the unique elements of 'nums' if there are no nearby duplicates. In the worst case, the dictionary will have as many entries as there are elements in 'nums'.
Learn more about how to find time and space complexity quickly using problem constraints.
Depth first search is equivalent to which of the tree traversal order?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!