Think of the numbers in the array representing a height. Now, you can create an imaginary box by selecting any two numbers in the array. The max height of water that this imaginary box can hold is the minimuj of the two numbers. So what is the area of the water that can be held?
area = min(height1, height2) * |right - left|.
Initialize two pointers,
left = 0 and
right = arr.size() - 1 and
result = 0 and perform the following for as long as
left < right:
- Caluclate area between
result = max(result, area)
- Because we want to find the biggest possible container, we must elimnate the shorter side. So, either
right--depending on which height is shorter.
The time complexity is
N is the total number elements in the array.
The space complexity is
O(1) since no additional space was used.
The problem is taken from Leetcode.
Solution is hosted on Github.