From the description of the problem, we are told that each number in the array represents the height of the vertical line at that index. So given an array
[4, 3, 7, 8, 2, 6, 9, 5], a visual representation of this array would look something like:
A brute force solution for this problem would be to go through each of the following combinations from
[0,1], [0,2], ... ,[1,2], [1,3], ... , [6, 7] and keep track of the maximum area found. But this would be
Can we do better? We sure can! Remember our task is to find the maximum area and the maximum area between two vertical lines is limited by the height of the shorter line.
We can use a two pointer approach, one at the beginning and one at the end to solve this problem in
O(N) time and constant space. Since we want to maximize, we only update the pointer with the shorter length, i.e. if the length at the start pointer is shorter than the end pointer, we move the start pointer forward, else move the end pointer backward. We terminate our algorithm when the two pointers cross over and at this time we are sure we have found the maximum area.
Given the array above,
[0, 7] → 4x7 = 28
[1, 7] → 3x6 = 18
[2, 7] → 5x5 = 25
[2, 6] → 7x4 = 28
[3, 6] → 8x3 = 24
[4, 6] → 2x2 = 4
[5, 6] → 6x1 = 6
[6, 6] → terminate
In our case we have a tie with the value 28 and since returning the indices is not required, we just return the value 28.
O(1) since the algorithm takes no extra space.
The problem is taken from Leetcode.
Solution hosted on Github.