Algorithm Puzzles: Container With Most Water

Algorithm Puzzles everyday every week sometimes: Container With Most Water

Puzzle

Puzzle from leetcode:

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.

Solution

This puzzle can be easily solved by exhaustion method but time complexity is O(N^2). A better approach will be using “compress window“:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int maxArea(const vector<int>& height) {
size_t length = height.size();
int currentMax = 0, windowLeft = 0, windowRight = length - 1;

while (windowLeft < windowRight) {
currentMax = std::max(
currentMax, std::min(height[windowLeft], height[windowRight]) *
(windowRight - windowLeft));
if (height[windowLeft] < height[windowRight]) {
++windowLeft;
} else {
--windowRight;
}
}
return currentMax;
}
};

Here time complexity is O(N)

Try to use iterator:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int maxArea(const vector<int>& height) {
int currentMax = 0;
auto iterL = height.cbegin();
auto iterR = height.cend() - 1;

while (iterL < iterR) {
currentMax =
std::max(currentMax, std::min(*iterL, *iterR) *
(int)std::distance(iterL, iterR));
if (*iterL < *iterR) {
++iterL;
} else {
--iterR;
}
}
return currentMax;
}
};

Bravo!