Container With Most Water

Introduction

Today, I tackled an interesting problem from LeetCode 75: Container With Most Water. This medium-level question requires knowledge of two pointers and greedy algorithms. It involves finding the maximum amount of water a container can store using an array of heights representing vertical lines. Let’s dive into the problem statement, approach, and solution.

Problem Statement

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i-th line are (i, 0) and (i, height[i]).

Find two lines that, together with the x-axis, form a container that contains the most water.

Example 1:

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

Output: 49

Explanation: The above vertical lines are represented by the array [1,8,6,2,5,4,8,3,7]. The maximum area of water the container can contain is 49.

Example 2:

Input: height = [1,1]

Output: 1

Constraints:

• n == height.length

• 2 <= n <= 10^5

• 0 <= height[i] <= 10^4

Approach to Solve the Problem

To solve this problem, we can use the two pointers technique combined with a greedy approach. Here are the steps involved:

1. Initialize Pointers: Use two pointers, one at the beginning (i) and one at the end (j) of the array.

2. Calculate Area: Calculate the area between the lines pointed by the two pointers and update the maximum area if the current area is larger.

3. Move Pointers: Move the pointer pointing to the shorter line inward, as this has the potential to increase the area by finding a taller line.

Solution

Here’s the Java code that implements the above approach:

public static int maxWater(int [] height){
    int max = 0;

    // initialising pointers at both end of array
    int i = 0, j = height.length-1;

    while (i < j){
        // Calculating the area
        int area = Math.min(height[i],height[j]) * (j-i);
        max = Math.max(max,area);

        // updating the pointer by finding a taller line
        if(height[i] > height[j]){
            j--;
        }
        else{
            i++;
        }
    }

    return max;
}

Explanation

1. Initialization: Pointers i and j are initialized to the start and end of the array, respectively.

2. Area Calculation: In each iteration, the area between the lines at i and j is calculated and compared with the current maximum area.

3. Pointer Movement: The pointer pointing to the shorter line is moved inward to potentially find a taller line, which could increase the area.

Performance

This solution efficiently finds the maximum area with a time complexity of O(n), where n is the length of the array. The use of two pointers ensures that each element is considered only once, making the approach both time and space efficient.

Conclusion

This problem highlights the power of the two pointers technique and greedy algorithms in solving optimization problems. The approach ensures that we find the maximum area by intelligently moving the pointers based on the heights of the lines.

I hope you found this explanation helpful. Stay tuned for more daily blogs on interesting problems and concepts I encounter in my learning journey!