Hello guys👋
In this article you will learn how to solve the Contains Duplicate II Question on Leetcode and I will solve the question using a very easy method.
Stay Calm and Let's get in✨
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.
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
Solution
This has a similar approach to the Contains Duplicate we solved earlier.
- Set up a map to store our values by index.
const map = new Map();
- Loop through the nums array and set the values of the array in the map by index.
for (let i = 0; i < nums.length; i++) { map.set(nums[i], i); }
We need to meet two conditions according to the questions and the conditions are:
nums[i] == nums[j].
abs(i-j) <= k.
So for
nums[i] == nums[j]
, that means it appears more than once or it is a duplicate. We will need to check the map if it has occurred before.for (let i = 0; i < nums.length; i++) { if (map.has(nums[i])) { } map.set(nums[i], i); }
If it has occurred before we will get the index of the duplicate and follow the second condition which is
abs(i-j) <= k
.for (let i = 0; i < nums.length; i++) { if (map.has(nums[i])) { const j = map.get(nums[i]); if (Math.abs(i - j) <= k) { } } map.set(nums[i], i); }
If this second condition is met then we will return
true
.for (let i = 0; i < nums.length; i++) { if (map.has(nums[i])) { const j = map.get(nums[i]); if (Math.abs(i - j) <= k) { return true; } } map.set(nums[i], i); }
We are done but we will need to return
false
if none of this condition is met.return false;
The Compilation of the code above is found below:
for (let i = 0; i < nums.length; i++) { if (map.has(nums[i])) { const j = map.get(nums[i]); if (Math.abs(i - j) <= k) { return true; } } map.set(nums[i], i); } return false;
- Time Complexity: O(n)
- Space Complexity: O(n)
Conclusion
I hope you have learnt a lot from this article and your contribution is also highly welcomed because we get better by learning from others, you can reach out to me on Twitter here . Watch out for more helpful contents on Data Structures and Algorithm from me.
Don't forget to Like, share and subscribe for more articles in this series called Solutions to Data Structures and Algorithm Questions on Leetcode.
Enjoy 🎉