Bug in leetcode, javascript 219. Contains Duplicate II

user_19239946 0
Viewed 84

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.

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.

logic arrays javascript
1 Answers

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.

user_95152070
Related