Leetcode problem number- 219

ยท

2 min read

Contains Duplicate II

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]

duplicate.PNG

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.

dup-2.PNG

  • Finally, calculate the absolute value of the difference of two indices and compare with k

dup-4.PNG 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 โœ๐Ÿผ

ย