Contains Duplicate II

Problem Summary

(Write in your own words, not copied from LeetCode. This forces comprehension.)

• Given a list of nums, find out whether same numbers appear k or less far away from each other
• Condition is: nums[i] == nums[j] and abs(i-j) <= k

Key Observations

(Patterns, constraints, or hints in the problem statement.)

• We only need to know the last index of the same number
• We don't need all indices of the number

Main Concepts Used

(Mark the CS concepts or algorithms used.)

• Array
• Hash Map

Time & Space Complexity

• Time: $O(n)$ → Reason: Iterating through it once
• Space: $O(n)$ → Reason: All unique numbers will be stored

Code

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        numToLastIndex = {}
        for currentIndex, num in enumerate(nums):
            if num in numToLastIndex: # we know when was it last found, do calc
                indexOfLastNum = numToLastIndex[num]
                if abs(currentIndex - indexOfLastNum) <= k:
                    return True
            numToLastIndex[num] = currentIndex
        return False

Common Mistakes / Things I Got Stuck On

• Was trying to store all indices and over complicating the solution