# 219. Contains Duplicate II

Reference: LeetCode

Difficulty: Easy

## Problem

Given an array of integers and an integer

`k`

, find out whether there are two distinct indices`i`

and`j`

in the array such that`nums[i] = nums[j]`

and theabsolute differencebetween`i`

and`j`

isat most`k`

.

**Example:**

1 | Input: nums = [1,2,3,1], k = 3 (diff = 3) |

## Analysis

### Hash Map

Go through some cases that have duplicates, e.g. `[1,0,1,1]`

.

1 | public boolean containsNearbyDuplicate(int[] nums, int k) { |

**Time:** $O(\min(N, k))$ since we don’t know how large `k`

could be.**Space:** $O(\min(N, k))$

### Sliding Window (k-size set)

We can just use a hash set of size `k`

. Whenever there is one more element, we remove the oldest element.

1 | // 0 1 2 3 4 |

1 | public boolean containsNearbyDuplicate(int[] nums, int k) { |

**Time:** $O(\min(N, k))$**Space:** $O(\min(N, k))$

Comment