My short and easy c++ code in O(n)


  • 22
    G
    class Solution {
    public:
        int maxArea(vector<int>& height) {
            int i=0,j=height.size()-1,ans = 0;
            while(j>i)
            {
                ans = max(min(height[i],height[j])*(j-i),ans);
                if(height[i]>height[j]) j--;
                else i++;
            }
            return ans;
        }
    };

  • 0
    C

    what's the execution time?
    You can also skip some iteration if next height is shorter than current height


  • 0
    G

    The execution time is of order(N) as we transverse the array only once, yes we could skip by checking the previous index value for the ith index and next index value for jth index


  • 0
    S

    Is the solution accepted? For {3,1,1,4,1,3}, it gives answer 15 (considering 3...3) but it should be 9. Where am I wrong?


  • 0
    G

    This solution is accepted . For {3,1,1,4,1,3}, the answer should be 15 because the distance between the three's is 5 so maximum water they could hold is (3 * 5) which is 15. Read the problem carefully because to calculate the water stored two planks at indices i an j you use formulae (j-i) * min(height[i],height[j]).


  • 0
    S

    My doubt is that if you are taking those three's, won't the middle four act as a barrier in the container? I guess it won't. I have solved a similar problem with that variation.


  • 0
    G

    The middle 4 separates the container but still the water is the same ie (3,4 ) + (4,3) =
    (3 , 3). The answer remains the same because 3 is minimum in both cases.


  • 0
    R

    Very clear and easy to understand, thanks for sharing.


  • 0

    really nice implementation !


Log in to reply
 

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