Python solution with detailed discussion


  • 0
    G

    Solution with discussionhttps://discuss.leetcode.com/topic/79863/python-solution-with-detailed-discussion

    Contains Duplicate II https://leetcode.com/problems/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.