My brute solution works fine with a break condition handled by a map.

function trap_a(arr) {
    let result = 0;
    for (let i=1; i<arr.length-1; i  ) {
        const curr = arr[i];
        let left = 0;
        let right = 0;
        let li = i-1;
        let ri = i 1;
        const hasNext = { left: true, right: true }; // <== here
        while(hasNext.left || hasNext.right) {  // <== here
            left = Math.max(left, arr[li]);
            right = Math.max(right, arr[ri]);
            if (arr[li-1] != undefined) {
                li--;
            }  else {
                hasNext.left = false;  // <== here
            }
            if (arr[ri 1] != undefined) {
                ri  ;
            } else {
                hasNext.right = false;  // <== here
            }
        }
        result  = Math.min(left, right) - curr;
    }
    return Math.abs(result);
}

This compares the biggest on the left side of the current element and same on the right.

But when I try to simplify the code by NOT using a map, it gives a different answer (wrong):

function trap_b(arr) {
    let result = 0;
    for (let i=1; i<arr.length-1; i  ) {
        const curr = arr[i];
        let left = 0;
        let right = 0;
        let li = i-1;
        let ri = i 1;
        while(arr[li-1] !== undefined || arr[ri 1] !== undefined) { // <== here
            left = Math.max(left, arr[li]);
            right = Math.max(right, arr[ri]);
            if (arr[li-1] != undefined) {
                li--;
            }  
            if (arr[ri 1] != undefined) {
                ri  ;
            } 
        }
        result  = Math.min(left, right) - curr;
    }
    return Math.abs(result);
}

Test case:

    console.log(trap_a([4,1,0,3,2,5]) === 10); // passes
    console.log(trap_b([4,1,0,3,2,5]) === 10); // fails

I am not sure what I am doing wrong in the second solution, it is literally doing the same thing. Am I missing something here?

CodePudding user response：

In trap_b, when you decrement li (respectively, increment ri), you check a different index in the loop test instead of the same one, so the loop exits early.

CodePudding user response：

It seems that trap_b is unable to iterate through the loop entirely. More specifically the right most element of the array is unreachable.

So in the first iteration, "right" is never updated to 5. This in turn results in

Math.max(left, right) - curr = Math.max(4, 3) - 1 = 2.

It should be:

Math.max(left, right) - curr = Math.max(4, 5) - 1 = 3.

Here is a small change that I made to the algorithm that ensures that left and right variables are updated correctly.

function trap_b(arr) {
    let result = 0;
    for (let i=1; i<arr.length-1; i  ) {
        const curr = arr[i];
        let left = 0;
        let right = 0;
        let li = i-1;
        let ri = i 1;
        while(arr[li-1] !== undefined || arr[ri 1] !== undefined) { // <== here
            left = Math.max(left, arr[li]);
            right = Math.max(right, arr[ri]);
            if (arr[li-1] != undefined) {
                li--;
            }  
            if (arr[ri 1] != undefined) {
                ri  ;
            } 
        }
        //Here is the change
        left = Math.max(left, arr[li]);
        right = Math.max(right, arr[ri]);
        //end of change

        result  = Math.min(left, right) - curr;
    }
    
    return Math.abs(result);
}