This is the question: https://leetcode.com/problems/contains-duplicate-ii/
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.
My code:
var containsNearbyDuplicate = function(nums, k) {
for(let i = 0; i < nums.length; i++) {
for(let j = i+1; j < nums.length; j++) {
console.log([i, j])
if(nums[i] == nums[j] && Math.abs(i-j) <= k){
return true;
}
}
}
return false;
};
On submission, I can pass 20/51 cases with status being ‘Time Limit Exceeded’.
I can pass the following example inputs:
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
I can’t think of any fringe cases which is causing the submission to exceed time limit. I’m aware that there are other ways to solve this problem, but I would like to know what’s wrong with my code. Any help will be highly appreciated!
EDIT:
I realised the problem is with this line: console.log([i, j]). If I comment it out, there is no problem with submission. But I’m not quite sure why that line is causing the time limit exceeded error. Any help will be highly appreciated!
>Solution :
Leetcode and similar sites often provide huge data sets as input. In such cases, an unnecessarily computationally complex algorithm can take too much processing time to complete. That may be what’s happening here.
You have a nested loop – if the input array contains 1000 items, that’s on the order of 1000 * 1000 iterations. Use a different, less expensive algorithm – such as by iterating over the input only once. One possible approach is
var containsNearbyDuplicate = function(nums, k) {
const numsByLastIndex = {};
for(let i = 0; i < nums.length; i++) {
const num = nums[i];
if (numsByLastIndex[num] !== undefined && i - numsByLastIndex[num] <= k) {
return true;
}
numsByLastIndex[num] = i;
}
return false;
};
When I try the above code, the time required has changed from on the order of 9 seconds (which may be close to the limit) down to 1/4 of a second.
Another issue is that logging in the Node CLI, if you do a ton of logging, can slow things down. Sometimes, logging can even take up most of the processing time of your script. It’s not needed to perform the task, so feel free to remove it.