Container With Most Water - A Greedy Two-Pointer Strategy (Java)

We've explored various array problems, including the nuances of "Trapping Rain Water." Today, we tackle another classic: "Container With Most Water" (LeetCode #11). While both involve water and bars, this problem has a distinct goal and an elegant solution using the Two-Pointer pattern combined with a greedy strategy.

Understanding the Problem:

We are given an integer array heights, where heights[i] represents the height of the i-th bar. Each bar has a width of 1.

Our task is to choose any two bars to form a container and return the maximum amount of water that this container can store. The container's base will be the distance between the two chosen bars, and its height will be limited by the shorter of the two bars.

Formula for Area: Area = min(height[left_bar], height[right_bar]) * (right_bar_index - left_bar_index)

Example:

• Input: heights = [1, 8, 6, 2, 5, 4, 8, 3, 7]

• Output: 49

Let's visualize the example (the bars at index 1 (height 8) and index 6 (height 8) form the largest container):

    #                   #
    # #               # #
    # # #           # # #
    # # # #       # # # #
    # # # # #     # # # #
    # # # # # #   # # # #
    # # # # # # # # # # #
    # # # # # # # # # # #
  _ _ _ _ _ _ _ _ _ _ _ _
  1 8 6 2 5 4 8 3 7    (Heights)

---

My Thought Process & Approach (Two-Pointer Greedy Strategy):

A naive approach might be to try every possible pair of bars, calculate the area, and find the maximum. This would involve nested loops, leading to an O(N^2) time complexity, which is too slow for larger inputs.

The problem's structure (finding a pair, maximizing something based on their relative positions) combined with the desire for efficiency often points to the Two-Pointer pattern. But how do we move the pointers to guarantee we find the optimal solution? This is where the greedy part comes in.

Here's the core idea:

1. Initialize Pointers:

   • Set a left pointer (i) at the beginning of the array (index 0).

   • Set a right pointer (j) at the end of the array (index heights.length - 1).

   • Initialize ans to 0 to store the maximum area found so far.

2. Iterate and Adjust (The Greedy Move):

   • While i is less than j (meaning our pointers haven't crossed):

     • Calculate the area of the container formed by heights[i] and heights[j]. This is Math.min(heights[i], heights[j]) * (j - i).

     • Update ans with the maximum of its current value and area.

     • Now, for the crucial part: Which pointer do we move?

       • The width (j - i) will always decrease as we move pointers inward. To maximize the area, we need to maximize min(heights[i], heights[j]).

       • If heights[i] is less than heights[j], then heights[i] is the limiting factor for the current container's height. To potentially find a larger area, we must try to find a taller left wall. Moving j inwards would only decrease the width and still be limited by the same heights[i]. So, we increment i.

       • If heights[j] is less than heights[i], then heights[j] is the limiting factor. We decrement j to search for a potentially taller right wall.

       • If heights[i] and heights[j] are equal, both are limiting. Moving either (or both) will explore new possibilities. Moving both is a safe and common practice to reduce search space efficiently.

3. Return: After the pointers cross (i >= j), the loop terminates, and ans will hold the maximum water that could be contained.

This greedy two-pointer strategy ensures that at each step, we're making the locally optimal choice that will lead to the globally optimal solution. We avoid configurations that we know cannot be better than our current best.

Java Code Implementation:

class Solution {
    public int maxArea(int[] heights) {
        int i =0;
        int j = heights.length-1;
        int ans = 0;
        while(i<j){
            int area = Math.min(heights[i],heights[j])*(j-i);
            if(heights[i]>heights[j]){
                j--;
            }
            else if(heights[i]<heights[j]){
                i++;
            }
            else{
                i++;j--;
            }
            ans = Math.max(ans,area);
        }
        return ans;
    }
}

Time and Space Complexity Analysis:

• Time Complexity: O(N)

  • The while loop iterates as the i pointer moves towards j, or j moves towards i. In each step, at least one pointer moves inwards.

  • In the worst case, the pointers will traverse the entire array once.

  • Each operation inside the loop (comparison, Math.min, Math.max, arithmetic) is constant time.

  • Therefore, the total time complexity is O(N). This is optimal as you need to at least look at a significant portion of the bars.

• Space Complexity: O(1)

  • We only use a few constant-space variables (i, j, area, ans).

  • No auxiliary data structures are used whose size depends on the input N.

  • This makes it a highly space-efficient solution.