Contains Duplicate II

(#219), Easy

Category: Array, Hash Table, Sliding Window

Problem Statement

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

Examples

Input: nums = [1, 2, 3, 1], k = 3

Output: true

Input: nums = [1, 0, 1, 1], k = 1

Output: true

Input: nums = [1, 2, 3, 1, 2, 3], k = 2

Output: false

Approach

Brute Force

  • Iterate through each index `i` from `0` to `n - 1`.
  • For each index `i`, check the next `k` elements (from `i+1` to `i+k`) to see if any are equal to `nums[i]`.
  • If a duplicate is found within the range, return `true`.
  • If no duplicates are found in any range, return `false`.
var containsNearbyDuplicate = function(nums, k) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j <= i + k && j < nums.length; j++) {
      if (nums[i] === nums[j]) return true;
    }
  }
  return false;
};

Sliding Window with Set

  • Initialize an empty Set to track the elements in the current window of size `k`.
  • Iterate through the array `nums` using index `i`.
  • If `nums[i]` is already in the Set, return `true` (duplicate within window found).
  • Otherwise, add `nums[i]` to the Set.
  • If the Set size exceeds `k`, remove the element at `i - k` from the Set (to maintain the window).
  • If no duplicates are found by the end of the loop, return `false`.
var containsNearbyDuplicate = function(nums, k) {
  const set = new Set();
  for (let i = 0; i < nums.length; i++) {
    if (set.has(nums[i])) return true;
    set.add(nums[i]);
    if (set.size > k) {
      set.delete(nums[i - k]);
    }
  }
  return false;
};

Complexity

Time: O(n)

Space: O(min(n, k))

Watch Explanation

📊 Presentation (PPT)

📥 Download PPT

📎 Resources