Container With Most Water

Given an array arr[] of non-negative integers, where each element arr[i] represents the height of the vertical lines, find the maximum amount of water that can be contained between any two lines, together with the x-axis.

Note: In the case of a single vertical line it will not be able to hold water.

Examples:

Input: arr[] = [1, 5, 4, 3]
Output: 6
Explanation: 5 and 3 are 2 distance apart. So the size of the base is 2. Height of container = min(5, 3) = 3. So, total area to hold water = 3 * 2 = 6.

Input: arr[] = [3, 1, 2, 4, 5]
Output: 12
Explanation: 5 and 3 are 4 distance apart. So the size of the base is 4. Height of container = min(5, 3) = 3. So, total area to hold water = 4 * 3 = 12.

Input: arr[] = [2, 1, 8, 6, 4, 6, 5, 5]
Output: 25 
Explanation: 8 and 5 are 5 distance apart. So the size of the base is 5. Height of container = min(8, 5) = 5. So, the total area to hold water = 5 * 5 = 25.

Constraints:
1<= arr.size() <=10⁵
1<= arr[i] <=10⁴

Approach 01:

class Solution {
  public:
    int maxWater(vector<int> &heights) {
        int size = heights.size();
        int leftIndex = 0;
        int rightIndex = size - 1;
        int maxArea = 0;

        // Return 0 if there is only one element (no container can be formed)
        if (size == 1) {
            return 0;
        }

        // Use two-pointer approach to find the maximum water area
        while (leftIndex < rightIndex) {
            int width = rightIndex - leftIndex;
            int height = min(heights[leftIndex], heights[rightIndex]);
            maxArea = max(maxArea, width * height);

            // Move the pointer pointing to the shorter height
            if (heights[leftIndex] < heights[rightIndex]) {
                ++leftIndex;
            } else {
                --rightIndex;
            }
        }

        return maxArea;
    }
};

class Solution:
    def maxWater(self, heights):
        size = len(heights)
        leftIndex = 0
        rightIndex = size - 1
        maxArea = 0

        # Return 0 if there is only one element (no container can be formed)
        if size == 1:
            return 0

        # Use two-pointer approach to find the maximum water area
        while leftIndex < rightIndex:
            width = rightIndex - leftIndex
            height = min(heights[leftIndex], heights[rightIndex])
            maxArea = max(maxArea, width * height)

            # Move the pointer pointing to the shorter height
            if heights[leftIndex] < heights[rightIndex]:
                leftIndex += 1
            else:
                rightIndex -= 1

        return maxArea

Time Complexity:

• Two-Pointer Traversal:

  The algorithm uses a two-pointer approach, where each pointer moves towards the center of the array. In the worst case, each pointer is moved \( n \) times, where \( n \) is the size of the input array.

• Operations Per Step:

  At each step, the algorithm performs a constant amount of work to calculate the area and update pointers.

• Overall Time Complexity:

  \( O(n) \).

Space Complexity:

• Extra Variables:

  The algorithm uses a constant amount of extra space for variables like leftIndex, rightIndex, maxArea, width, and height.

• Data Structures:

  No additional data structures are used, and the input array is not modified.

• Overall Space Complexity:

  \( O(1) \).