How to improve time limit exceeded in Leetcode?-CodePudding

I did exercise 11. Container with more water in Leetcode, i got a 55/60 test cases passed with a status of time limit exceeded, there isn't a specific error.

So, Do you have any idea to how to fix my code to get the 5 missing points ?

My code is the next:

/**
 * @param {number[]} height
 * @return {number}
 */

//to get the area between two endpoints
const getArea = (left, right, distance) => {

  if (left <= right) {
    return left * distance;
  } else {
    return right * distance;
  }
}

//this function receive height array to check all areas and find max area
const maxArea = (height) => {

  let left = 0;
  let right = height.length - 1;
  let distance = right - left;
  let maxArea = 0;
  let area = 0;

  // for the conditional of the loop, i use the Gauss sum 
  // to get all possible areas.
  // Example: in the array [2,4,5,10], the possible areas are:
  // [2,4], [2,5], [2,10], [4,5], [4,10], [5,10]
  // using the Gauss sum: n(n 1)/2, where n = array.length-1, 
  // i can get the possible areas, in this case, the result is 6

  for (let i = 0; i < ((height.length - 1) * ((height.length - 1)   1) / 2);   i) {

    area = getArea(height[left], height[right], distance);

    if (area > maxArea) {
      maxArea = area;
    }

    //Increase and reduce the pointers to pass to the next possible area
    if (right == left   1) {
      left  ;
      right = height.length - 1;
      distance = right - left;
    } else {
      right -= 1;
      distance--;
    }
  }

  return maxArea;

};

let height = [1, 8, 6, 2, 5, 4, 8, 3, 7];

console.log(maxArea(height));

I'm wait for an answer, i'm learning Javascript, beforehand thank you.

CodePudding user response：

Maybe try replacing:

area = getArea(height[left], height[right], distance);

with:

area = height[left] <= height[right] ? left*distance : right*distance;

and remove the getArea() function all together.

CodePudding user response：

Here's a substantially streamlined revision of your code. The most important fix is to have the iteration happen only from the edges of the array inward, not to an n^2 limit as you had it...

var maxArea = function(height) {
    let left=0;
    let right=height.length-1;
    let maxArea = 0;
    while (right>left) {
        // area is the smallest height times distance
        let area = Math.min(height[left], height[right]) * (right-left)
        if (area > maxArea) maxArea = area;
        // move the pointer off the smaller element
        if (height[left] < height[right]) left  ; else right--;
    }
    return maxArea
};

console.log(maxArea([1,8,6,2,5,4,8,3,7]))

I haven't tried it on leet code, but I'd be surprised if there's a better than O(n) solution, and I don't see any wasteful constant time in the idea.