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