Why time exceeded? how can it be optimized?


  • 0
    G
    #ingclude <stdlib.h> 
    bool containsNearbyAlmostDuplicate(int* nums, int numsSize, int k, int t) {
    int i,j;
    long max,min;
    if (numsSize == 1 || k <= 0 || t < 0 ) {
        return false;
    } 
    j = 0;
    max = nums[j] + t;
    min = nums[j] - t;
    
    for (i=j+1; i < numsSize; i++){
        if (nums[i] >= min && nums[i] <= max) {
            return true;
        }
        if (i == j + k || i == numsSize - 1){
            j = j + 1;
            max = nums[j] + t;
            min = nums[j] - t;
            i = j + 1;
        }
    } 
    return false;
    

    }


  • 1
    T

    Your method is O(N^2). There is no way for your code to pass the large case if you stick with this algorithm. You need to use an O(NlogN) method (binary search tree) or O(N) method (bucket sort) or other method to pass the time limit.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.