Problem description: 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.
Input: nums = [1,2,3,1], k = 3
Output: true
Thought process: If we are given an array of integers wherein we do not have any duplicate numbers then there's no point to check any further. So, our first step will be to write a piece of code which checks for this condition.
We can utilize the fact that set doesn't contain any duplicate integers. So first part of our code will be like:
#if length of given list is equal to the length of set
#it means the list had no duplicates in the first place!
if len(nums) == len(set(nums)):
return False
#so return false
Now will move to the other case where we have to deal with the duplicates. Here, two piece of information is useful for us:
- Number in the list
- Index of that number
To keep track of both of them we can use dictionary. Lets observe how will we store the above piece of information if we are given nums = [ 1, 2, 3, 1]
Since we need to keep track of index as well as the number we can simply use enumerate method. We will add in the key value pairs (index, number) in our dictionary.
- We will keep on adding the numbers in the dictionary till we encounter a duplicate number.
{1:0, 2:1, 3:2}
Stop 🛑
- As soon as we encounter the duplicate number, we will get the index of the number which is there in the dictionary and the current index we are at.
- Finally, calculate the absolute value of the difference of two indices and compare with k
Final code with comments:
def dup(nums,k):
#create a dictionary
h = {}
#check for the first condition
if len(nums) == len(set(nums)):
return False
#enumerate through dictionary
for i, j in enumerate(nums):
#if number is in dictionary and absolute value of differences is also less than equal to k #then return true
if j in h and abs(h[j]- i) <=k:
return True
#if dictionary is empty or the number encountered is not duplicate add it to the #dictionary
h[j] = i
return False
And Phew! we are done with this problem 👩🏼💻 🏅 Follow me for more ✍🏼