Why my code get TLE (O(n) time and O(1) space


  • 0
    H

    The basic idea is scan from left,
    once find maximum,

    1. check if A[i] >= prevmax ( checking which side is the shorter border, if right, currwater -= (prevmax - A[i]) * (i-prevmaxpos -1) )

    2. add currwater to result,

    3. record its value and position to prevmax and prevmaxpos,

    4. set currwater to 0

    if not maximum, currwater += prevmax - A[i] (suppose left border is the shorter one)

    So, only prevmax, prevmaxpos, currwater and result as extra space and one iteration for O(n) time complexicity, why I got TLE with a long input starting with [10527,740,9013,1300,...]? Anybody can help me check what is wrong with my code? Thanks

    public class Solution {
    public int trap(int[] A) {
        if(A.length <3) return 0;
        int prevmax = A[0];
        int prevmaxpos = 0;
        int currcount = 0;
        int result = 0;
        for(int i = 1; i < A.length-1; i++){
            if(A[i] > A[i-1] && (A[i] > A[i+1] )){             // find max
                if(A[i] >= prevmax) result += currcount;
                else result += (i - prevmaxpos - 1)*(prevmax - A[i]);
                prevmax = A[i]; 
                prevmaxpos = i;
                currcount = 0;
            }
            else currcount += Math.max(0, prevmax - A[i]);
        }
        if(A[A.length-1] >= prevmax) result += currcount;
        else result += Math.max( 0, currcount -(A.length-1 - prevmaxpos - 1)*(prevmax - A[A.length-1]));
        
        return result;
    }
    

    }


Log in to reply
 

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