This problem I used brute force first, but after submission it exceed the time limit. The time complexity is O(n^2).
Then I changed to two pointers' way. The left pointer from the index 0 and the right pointer from the last index. Then calculate the area. The area is (right - left) * the shorter height of the two indices. So the pointer is seeking a bigger value of height to produce a bigger area. If left one is shorter, then move rightward; if the right one is shorter, then move leftward. res
picks the bigger value each loop and return the result in the end. The time complexity is O(n).
Top comments (0)