Grind 75 problem 7 - Container With Most Water

The question .

This is a problem I'm very familiar with, so I appreciated the easy and breezy time. This feels like the type of problem that is really easy once you know how to do it, but there are some heuristics you need to know.

Premise -

We're given an array of heights and tasked to find the two heights that yield the largest volume.

The heuristics to know -

I'm not positive that I'm using the word 'heuristics' right

The way to calculate the volume is to use the lower of the two heights as the height multiplied by the distance between the indexes of the heights. We choose the smaller of the two heights because if we use the taller height, the water would overflow over the smaller height.

We solve this using two pointers, starting at the beginning and end of the array. At this state, the width is the most it can ever be.

The algorithm for finding the greatest volume works as follows:

Calculate your starting volume. That is now your largest.

Look at your left and right pointer heights, and move the pointer associated with the smaller height closer to the center. This will make your width smaller by one, but it might find a higher height.

Per the first point above, we move the smaller height in because it's the only way to possible find a larger overall height. The lower height is the constraint, so if we moved the taller height pointer in, we could only ever go down in height.

For each move, we calculate total volume and replace "largest" if the volume is larger

We finish when our left and right pointer overlap

function maxArea(height: number[]): number {
let largest = 0;
let left = 0;
let right = height.length - 1;

while(
left < right
){
const leftHeight = height[left];
const rightHeight = height[right];
const isLeftLesser = leftHeight < rightHeight
const lesser = isLeftLesser ? leftHeight : rightHeight;
const width = right - left;
const product = lesser * width;
largest = product > largest ? product: largest

if(isLeftLesser){
left = left + 1
}
else{
right = right - 1
}
}
return largest
};

My solution above finished in the 95th percentile for runtime.