Contains Duplicate II

Photo by Irvan Smith on Unsplash

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

Example 1:

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

Example 2:

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

Example 3:

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

This is a kind of follow up to my last post about Maps in javascript because I will be using what I learned with Maps to solve this problem. The wording of this problem is a little confusing at first read so let’s start to break it down to make it easier to understand.

We want to see if the array given has duplicate numbers that are at most k indices apart. If we are looking at the first example we can see that there are obviously two distinct 1’s. One of them is at index 0 and the other at index 3 this is equal to the given k = 3 so in this case our function we create should return true.

var containsNearbyDuplicate = function(nums, k) {
    let myMap = new Map()
    for(let i=0; i<nums.length; i++){
        let currentNum = nums[i]
        if(myMap.has(currentNum) && i - myMap.get(currentNum) <= k){
            return true
        } else {
            myMap.set(nums[i], [i])
        }
    }
    return false
}

Using what I learned with Maps the first thing I’m going to do is create a new map set to a variable that I will name myMap and then use a for loop. To make it a bit easier to read and write let’s make another variable called currentNum that we will set to whatever the number is at whatever loop we are in.

Then we will use our if statement. I’m going to go through my thought process for this even though the full code is already above. So first I will start with if myMap contains the current num I want to return true and if it doesn’t I want to add the current number and it’s index to myMap. That logic would look a little like this:

if(myMap.has(currentNum){
      return true
} else {
      myMap.set(nums[i], [i])
}

As of right now we are disregarding the k part of the equation. All this if statement does is checks if myMap already has this number and if it doesn’t it will add that number to the map as a key. Now to consider the k part. So because the duplicate number has to be k indices away I’ll have to add some logic to our if statement. I’m going to use the logical AND operator or && to make sure that our duplicated number is within k away. To do that we take the index we are currently at in the loop or i and subtract it from the first index of the duplicated number. But how do I find that? I will use the .get() method on my myMap and pass in the currentNum. This will get me the value of the first instance of the duplicated number, which is that numbers index. So we subtract that index from the index the loop is currently at and if that is less than or equal to k then the function will return true. The final piece of code we need to add to the end of the function will be to return false just in case the for loop gets to the end of itself and does not find a condition that will return true.