Contains Duplicate II

Problem Statement: Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.

Example 1:

Input: nums = [1,2,1,3], k = 3
Output: true

Example 2:

Input: nums = [1,0,0,1,1], k = 1
Output: true

Constraints:

• 1 <= nums.length <= 105
• -109 <= nums[i] <= 109
• 0 <= k <= 105

Source: https://leetcode.com/problems/contains-duplicate-ii/

Leetcode Difficulty: Easy

Asked in: Google

Code:

    def duplicate_ii(self, nums, k):
        """
        :nums: List[int]
        :k: int
        :return: bool
        """
        big_idx_map={}
        
        for idx, i in enumerate(nums):
            if i not in big_idx_map:
                big_idx_map[i] = idx
            else:
                if (idx-big_idx_map[i])<=k:
                    return True
                else:
                    big_idx_map[i]=idx
        return False

Thought Process / Explanation:

We are given k (difference to compare against) and the value at any two different idx can be atmost k. Since we will need to find all positions of every element, this hints me to use a dictionary that would help me store numbers and lists idx as key-value pair. Finally, I can iterate through the idx list and get pair that satisfies the condition of <=k. 

But can we do better and reduce this idx list traversal?

One thing to notice over here is that the difference between nearby values will always be less than the difference between farther apart ones. And since we need to satisfy the at-most condition, So, instead of storing list of idx as a value in our dictionary, we can only get done by storing the next higher idx of the occurrence of a particular number and do the comparison with that. That's what is written in the code above.

Thank You!