219. Contains Duplicate II

EasyArrayHash TableSliding Window
Leetcode Link

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

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:

  1. If the current element x already exists in the hash table d and the difference between the current index i and the previously stored index for x (d[x]) is less than or equal to k, then we have found two indices i and j (where j is d[x]) that satisfy both conditions: nums[i] == nums[j] and abs(i - j) <= k. In this case, the function immediately returns true.

  2. 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 index i for element x: 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.

  3. 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 returning false.

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

Example 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.

  1. We start with an empty hash table d = {}.

  2. We iterate through the nums array with index i and element x.

    a. At i = 0, x = 1. We add 1 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 element 1 is already in the hash table. We check the index of the last occurrence of 1 in d, which is 0. The difference between the current index 3 and the last index 0 is 3 which is not less than or equal to k. We update d with the new index for 1: 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 index 1. The difference between i = 4 and 1 is 3, which again, is not less than or equal to k. We update d: d = {1: 3, 2: 4, 3: 2}.

    f. At i = 5, x = 3. The 3 is found in the hash table at index 2. The difference between i = 5 and 2 is 3, which is also not less than or equal to k. Update d: d = {1: 3, 2: 4, 3: 5}.

  3. 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 returns false.

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
Not Sure What to Study? Take the 2-min Quiz：

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

Recommended Readings

Sliding Window Maximum

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 - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫