Python solution with detailed discussion

  • 0

    Solution with discussion

    Contains Duplicate II

    • When we iterate the array, we receive the indces of the same element in ascending order. This is an important insight to remember.
    • Assume k = 3. Say we see x=5 at index 4. Then we see it again at index 8. 8-4 > 3 and this doesnt meet our criterion. Now any other index of 5 will definitely not meet meet the criterion with respect to index 4, since the difference will surely be more than 4.
    • This means that we can build a last_seen_index dictionary and update the last_seen index when we do not meet the criterion or return True if we do.
    class Solution(object):
        def containsNearbyDuplicate(self, nums, k):
            :type nums: List[int]
            :type k: int
            :rtype: bool
            last_seen_index = {}
            for idx, x in enumerate(nums):
                if x in last_seen_index and idx - last_seen_index[x] <= k:
                    return True
                last_seen_index[x] = idx
            return False

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.