Contains Duplicate II

Easy#219find a pair

You get an array of numbers and a number k. Find out whether two equal numbers stand at indices no more than k apart. Our example: [7, 3, 9, 7, 4, 9, 4] and k = 2 — yes: the 7s and the 9s are too far apart, but the 4s at indices 4 and 6 are exactly 2 apart.

219 Contains Duplicate IIWalkthrough · 1×

Example: [7, 3, 9, 7, 4, 9, 4], k = 2. Above the array is the distance to the earlier copy, below it the map: number and its last index.

07132937445964lastx: i—
not reached yetseencurrent numbera copy too farclose enough

Start with an empty map: number → the last index it was seen at

01/29
restart · back · play · step
Speed
1function containsNearbyDuplicate(nums, k):
2 last = empty map
3 for i from 0 to len(nums) - 1:
4 x = nums[i]
5 if x in last and i - last[x] <= k:
6 return true
7 last[x] = i
8 return false
state
last
{}
i
–
x
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Only the nearest earlier copy matters: if any copy is close enough, the latest one is. So the map keeps just the last index of each number.
  2. A repeat that is too far is not an answer, but it takes over the index: the next copy of the number is measured from it, not from an older one.
  3. Check first, store after, as in Two Sum: a number never measures the distance to itself.

Complexity

Time O(n): one pass, map lookups are O(1). Memory O(n) for the map; keeping only the last k numbers in a set brings it down to O(k).

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.