Contains Duplicate II

EASY

Description

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⁵
-10⁹ <= nums[i] <= 10⁹
0 <= k <= 10⁵

Approaches

Checkout 3 different approaches to solve Contains Duplicate II. Click on different approaches to view the approach and algorithm in detail.

HashMap with Index Tracking

Use a HashMap to store the most recent index of each element and check for distance constraint.

Algorithm

Create a HashMap to store element to index mapping
Iterate through the array
If current element exists in map and distance ≤ k, return true
Update element's index in map
If loop completes, return false

We use a HashMap to store each element as key and its most recent index as value. For each element, we check if it exists in the map and if the distance from its last occurrence is within k. If yes, we found a valid duplicate. Otherwise, we update the element's most recent index in the map.

public boolean containsNearbyDuplicate(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    
    for (int i = 0; i < nums.length; i++) {
        if (map.containsKey(nums[i])) {
            if (i - map.get(nums[i]) <= k) {
                return true;
            }
        }
        map.put(nums[i], i);
    }
    return false;
}

Complexity Analysis

Time Complexity: O(n) where n is the length of array as we only traverse the array onceSpace Complexity: O(n) in worst case where all elements are unique

Pros and Cons

Pros:

Most efficient solution
Single pass through array
No need to remove elements
Cleaner implementation

Cons:

Uses more space than sliding window approach
HashMap operations have some overhead
Space complexity doesn't benefit from k constraint

Code Solutions

Checking out 5 solutions in different languages for Contains Duplicate II. Click on different languages to view the code.

public class Solution { public bool ContainsNearbyDuplicate ( int [] nums , int k ) { var d = new Dictionary < int , int >(); for ( int i = 0 ; i < nums . Length ; ++ i ) { if ( d . ContainsKey ( nums [ i ]) && i - d [ nums [ i ]] <= k ) { return true ; } d [ nums [ i ]] = i ; } return false ; } }

Video Solution

Watch the video walkthrough for Contains Duplicate II

Patterns:

Sliding Window

Data Structures:

ArrayHash Table

Companies:

Airbnb |Goldman Sachs |Google |Netflix |