Leetcode 219 Contains Duplicate II
Contains Duplicate II – LeetCode
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.
We use a map the keep some information for each number in the array. The key would be the number itself, the value is a map too to keep the upper bound and lower of the index for a valid pair, where nums[i] == nums[j] and abs(i - j) <= k. e.g
{
1: {
upper: 5,
lower: -1
},
2: {
upper: 7,
lower: 1
}
}Then we check each number in the array and see if the index falls between the upper bound and lower bound for that particular number, otherwise we need to update the map for that number
Solution
/**
* @param {number[]} nums
* @param {number} k
* @return {boolean}
*/
var containsNearbyDuplicate = function(nums, k) {
let map = {};
for(let i = 0; i < nums.length; i++) {
if(map[nums[i]] && i >= map[nums[i]].lower && i <= map[nums[i]].upper) {
return true
} else {
map[nums[i]] = {
upper: i + k,
lower: i - k
}
}
}
return false
};