Container With Most Water

Container With Most Water

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.

Example

Input: height = [1,8,6,2,5,4,8,3,7] Output: 49 Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Approach 1:

For this type of question, I thought having a left and right pointer to examine the maximum amount would be most efficient.

Implementation:

class Solution:


    def maxArea(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        maxarea = 0
        while left < right:
            if height[left] < height[right]:
                maxarea = max(maxarea, (right- left) * height[left])
                left += 1
            else:
                maxarea = max(maxarea, (right - left)*height[right])
                right -= 1
        return maxarea

        

Complexity Analysis:

Time Complexity: O(N) where n is the length of the array height

Space Complexity: O(1)

Reflection

Since I finished the array questions, I thought it would be good to reflect back on some methods in solving array questions.

1. For array questions, it is crucial to use the right type of data structure, to get your answer. Most commonly used ones are hashmaps and hashsets.
2. Some array questions can be solved with a left and a right pointer to check and update for whatever needs to be returned for that specific question.
3. It is always worthy to check if we can use max or min functions to optimize our answer.
4. When you are sure that the optimal solution exceeds O(N * logN) time complexity, inspect whether sorting the array first will speed up your answer