[LeetCode] 219 - Contains Duplicate Number - 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.

Brute-force approach:

• Have a nested for loop that takes in all the pairs and check the above condition.
• Problems is that it will solve the basic test cases but since its time complexity is O(N^2), it will error out with "Time Exceeded" if an array is passed with 1000s of elements in it.

Brute-force solution:

Brute-force Result:

Efficient Approach:

• With the help of a hash map we can track the last index of each element.
• In order to implement a hash map in JavaScript, we would use Map.
• We will first traverse through the array once, then check if the key exists in the map:
• If yes, then we will check if the current index and stored index is less or equal to 'k'. return true;
• If not, we will store the element as key and its index as value in Map.
• Outside the loop, 'return false' if no duplicates found with index difference <= k.

Efficient Solution:

Efficient Result:

Link: https://leetcode.com/problems/contains-duplicate-ii/submissions/1488719668