Easy

Contains Duplicate II

LAB

Return true if two equal values appear at indices whose distance is at most k.

EXAMPLES

Example 1

Input
{
  "nums": [
    1,
    2,
    3,
    1
  ],
  "k": 3
}

Output
true

FUNCTION SHAPE

nums: intArrayk: int→bool

SOLUTION NOTE

This problem is actually very similar to Two Sum - we track the last index we saw each value and check if the distance constraint is satisfied.

Reveal reference solution +

pythonREFERENCE

# Method 1: With explicit check
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
    last = {}
    for i in range(len(nums)):
        if nums[i] in last and i - last[nums[i]] <= k:
            return True
        last[nums[i]] = i
    return False

# Method 2: With defaultdict
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
    last = defaultdict(lambda: -inf)
    for i in range(len(nums)):
        if i - last[nums[i]] <= k:
            return True
        last[nums[i]] = i
    return False

TimeO(n)

SpaceO(n)

Open on LeetCode ↗