3
\$\begingroup\$

I was doing container with most water question in Leetcode for which I wrote this algorithm

Question link: https://leetcode.com/problems/container-with-most-water

Question:

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

Input: [1,8,6,2,5,4,8,3,7]

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



var maxArea = function(height) {
    let currentHighest=0
    while(height.length) {
        const num = height.shift() 
        let j=0
        while(j<height.length) {
            const lowerNum = Math.min(num, height[j]) 
            const distance = j+1
            const area = distance * lowerNum 
            currentHighest = Math.max(currentHighest,  area) 
            j++
        }
    }
    return currentHighest
};

but it appears so this code isn't opimized, Can someone help me in optimizng the above code?

\$\endgroup\$
  • \$\begingroup\$ In your solution you destroy the input array. Is it required, allowed or unwanted? \$\endgroup\$ – slepic Nov 16 '19 at 7:49
  • \$\begingroup\$ Nope but it reduces the iterations for inside array \$\endgroup\$ – iRohitBhatia Nov 16 '19 at 8:11
1
\$\begingroup\$

Ok, so I made implementation very similar to yours with these modifications:

  • input is not being destroyed (althout it can still be adjusted to destroy it, but it just feels like such algorithm should not do this)
  • I compute maximum potential container area for values as I iterate them from left
  • I iterate the inner loop from end towards front
  • I use the potential to reduce the number of iterations of the inner loop.
function maxArea (input)
{
    // result value will go here
    let currentMax = 0;

    // we will need this value at least 2*(n-1) times:
    const limit = input.length - 1;

    // i<limit because having i=limit would always yield zero size container so skip it:
    for(let i = 0; i < limit; ++i) {
      const left = input[i];

      // zero size edge always yields zero size container so move to next i
      // this check may be omitted as the next will exclude it as well
      //if (left == 0) continue;

      // the largest container we can have on the right has this area:
      let potential = left * (limit - i);

      // if potential is not enough to get over currentMax, just move to next i
      if (potential <= currentMax) continue;

      // search from end towards i becase more distant j is more likely to yield larger container and only the last j can actualy yield current potential
      for (let j = limit; j > i; --j) {
        const right = input[j];

        // if right is at least as high as left then this container has the area equal to potential and no other j will do better for current left value
        if (right >= left) {
          currentMax = potential;
          break;
        }

        // if it is smaller we check if its area is greater then currentMax and use it if it is
        const area = right * (j - i);
        if (area > currentMax) currentMax = area;

        //decrease potential by 1 times left value because we will reduce distance by 1 for next iteration (--j):
        potential -= left;

        // if new potential is not enough to get over currentMax we can stop searching further j's and move to next i
        if (potential <= currentMax) break;
      }
    }
    return currentMax;
}

In conjuction this algorithm is still (like yours) O(n^2) in time and O(1) in space. But it is a better n^2 then yours, I believe. And (unlike yours) the actual performance will be different for different input values, not only for different lengths of the input array. It is same as yours in worst case (ie strictly decreasing sequence) and actualy O(n) in best case (ie increasing sequence). And of course anywhere in between for most of the possible variations of input values.

EDIT: hehe ok I benched it on random 100k value arrays and mine takes about 4ms, yours 15+ seconds :) The worst case scenario is about 15 seconds yours, 7 seconds mine. But the worst case scenario is very small set of all posibilities, so to get it from randomness is very unlikely. Randomness holds it on few ms. So improvement by factor of several thousands for random 100k value inputs :)

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.