# Contains Duplicate II

Published: Oct 21, 2022

Easy Hash Table Sliding Window Array

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

Constraints:

• `1 <= nums.length <= 10**5`
• `-10**9 <= nums[i] <= 10**9`
• `0 <= k <= 10**5`

https://leetcode.com/problems/contains-duplicate-ii/

## Examples

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

## How to Solve

This is not a difficult problem. Multiple O(n) iterations would be the easiest, brute force approach. However, making the solution efficient, say, O(n), needs a bit of considerations. While we check all values from index 0 to n, what we care about is the last index of the same value only. When the same value appears, check the last index. If the difference is less than or equals to k, return True.

The Hash Table is a good data structure to save the value and its last index pair. If the same value is in the Hash Table, check the difference between the last and current index. Return true if the difference is less than or equals to k.

## Solution

``````#include <unordered_map>
#include <vector>

using namespace std;

class ContainsDuplicate2 {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_map<int, int> counts;
for (int i = 0; i < nums.size(); ++i) {
if (counts.find(nums[i]) != counts.end() && i - counts[nums[i]] <= k) {
return true;
}
counts[nums[i]] = i;
}
return false;
}
};
``````
``````import java.util.*;

class ContainsDuplicate2 {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Map<Integer, Integer> counts = new HashMap<>();
for (int i = 0; i < nums.length; ++i) {
if (counts.containsKey(nums[i]) && i - counts.get(nums[i]) <= k) {
return true;
}
counts.put(nums[i], i);
}
return false;
}
}
``````
``````/**
* @param {number[]} nums
* @param {number} k
* @return {boolean}
*/
var containsNearbyDuplicate = function(nums, k) {
const counts = new Map();
for (let i = 0; i < nums.length; i++) {
if (counts.has(nums[i]) && i - counts.get(nums[i]) <= k) {
return true;
}
counts.set(nums[i], i);
}
return false;
};
``````
``````class ContainsDuplicate2:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
counts = {}
for idx, v in enumerate(nums):
if v in counts and idx - counts[v] <= k:
return True
counts[v] = idx
return False
``````
``````# @param {Integer[]} nums
# @param {Integer} k
# @return {Boolean}
def contains_nearby_duplicate(nums, k)
counts = {}
(0...nums.size).each do |i|
if counts.has_key?(nums[i]) && i - counts[nums[i]] <= k
return true
end
counts[nums[i]] = i
end
false
end
``````

## Complexities

• Time: `O(n)`
• Space: `O(n)`