Scale Engineer

Contains Duplicate II

Easy
#0207Time: O(n) where n is the length of array as we only traverse the array onceSpace: O(n) in worst case where all elements are unique6 companies
Patterns
Sliding Window
Data structures
ArrayHash Table
Companies
AirbnbGoldman SachsGoogleNetflix

Prompt

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 <= 105
  • -109 <= nums[i] <= 109
  • 0 <= k <= 105

Approaches

3 approaches with complexity analysis and trade-offs.

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

Algorithm

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

Walkthrough

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

Time

O(n) where n is the length of array as we only traverse the array once

Space

O(n) in worst case where all elements are unique

Trade-offs

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

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem