Container With Most Water

Description

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

class Solution {
    func maxArea(_ height: [Int]) -> Int {
        var p = 0
        var c = height.count - 1
        var areaM = 0
        for _ in 0..<height.count - 1{
            if (min(height[p], height[c]) * (c - p) >= areaM){
                areaM = min(height[p], height[c]) * (c - p)
            }
            if (height[c] > height[p]){
                p = p + 1
            }else{
                c = c - 1
            }
        }

        return areaM
    }
}

Explanation

To calculate the area of a rectangle we need the base and the height. To solve this problem we have to max these two variables, at first we don’t know the maximum height, but the max base will be from index 0 to height.length. That is our starting point, from here the base will only reduce by one each iteration.

The height is limited by the shortest vertical line on the endpoints, I use 2 variables one in one at each end of the array p = 0 and c = height.length – 1 to mark the limits of the containers. 

After each iteration, I check which vertical is the smallest and increase p or reduce c by 1. 

Performance 

How to improve

Sense we have to variable in each end we can reduce the run time by n/2, because we are multiplying positives values and is the same B x H to H x B

Leave a Comment

Your email address will not be published.