Problem 37 - Contains Duplicate II

Explore our archive for previous posts.

Problem 36 - Contains Duplicate

Problem 35 - Majority Element

Question

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

Approach

The high-level approach to solving this problem involves efficiently detecting whether there are two distinct elements in the given array that have a maximum allowed index difference (window size) of 'k'. The primary idea is to efficiently use a hashmap data structure to keep track of elements and their indices in the sliding window, allowing you to identify duplicates within the allowed range 'k' while avoiding unnecessary checks for elements outside the window.

Here's a summarized explanation of the approach:

1. Iterate through the given array, maintaining a sliding window of size 'k'.

2. As you traverse the array, keep track of the elements within the current window and their corresponding indices.

3. At each step, check if the current element already exists in a data structure like a HashMap. If it does, calculate the difference between the current index and the index stored in the data structure for that element.

4. If the difference between indices is less than or equal to 'k', you've found two elements within the allowed window size, which means there's a duplicate within the specified range.

5. Continue sliding the window through the array, updating the data structure as you move.

6. If you find a pair of elements with a maximum index difference of 'k', you can immediately return true, indicating the presence of a duplicate with the required constraints.

7. If you traverse the entire array without finding such a pair, you can return false, as no duplicates within the specified range were found.

Solution

Solve it here

public class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        // Store the elements as keys and their indices as values.
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];

            // If the element is already in the HashMap and the absolute difference between the
            // current index and the stored index is at most k, return true.
            if (map.containsKey(num) && i - map.get(num) <= k) {
                return true;
            }

            // Update the index of the element in the HashMap.
            map.put(num, i);
        }

        // If we reach this point without finding a pair that satisfies the condition, return false.
        return false;
    }
}

Time and space complexity

Time Complexity: The time complexity of the solution is O(n), where 'n' is the number of elements in the array. This is because we iterate through the entire array exactly once.

Space Complexity: The space complexity of the solution is O(min(n, k)). This is because the space required to store elements in the sliding window is directly related to the window size 'k'. In the worst case, where 'k' is equal to or larger than 'n', we need to store 'n' elements in the window. However, if 'k' is smaller, the space complexity is determined by the window size, which is 'k'. This accounts for the varying space requirements depending on the relationship between 'n' and 'k', hence O(min(n, k)).

Explore more?

Missed a previous edition? Catch up on the insightful content you might have missed by visiting our archive here. Thank you for being a valued reader of our newsletter. We appreciate your continued support!