LC-0219 Easy LeetCode

219. Contains Duplicate II

Read the full problem statement on LeetCode.

Difficulty: easy Acceptance: 49% Topics: Array, Hash Table, Sliding Window

Reading material

Arrays & Hashing 12 min Sliding Window 11 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(n)

class Solution(object):
    # @param {integer[]} nums
    # @param {integer} k
    # @return {boolean}
    def containsNearbyDuplicate(self, nums, k):
        lookup = {}
        for i, num in enumerate(nums):
            if num not in lookup:
                lookup[num] = i
            else:
                # If the value occurs before, check the difference.
                if i - lookup[num] <= k:
                    return True
                # Update the index of the value.
                lookup[num] = i
        return False

Solution from kamyu104/LeetCode-Solutions · MIT