algoadvance

Leetcode 11. Container With Most Water

Problem Statement

You are given an array height of length n where height[i] is the height of a vertical line drawn at the i-th position. Find two lines that, together with the x-axis, form a container that holds the most water. You need to return the maximum amount of water a container can store.

Example:

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

   • Explanation: The vertical lines are drawn as such:

     |       |
     |       |
     | |     |
     | |     |
     | | |   |
     | | | | |
     | | | | |
     

     The container formed by lines at index 1 and 8 (heights 8 and 7) can contain the most water, with an area of (49).

2. Input: height = [1,1] Output: 1

Clarifying Questions

1. What is the range of values for height[i]?
   • The heights are positive integers.
2. What is the maximum possible length of the array?
   • You can assume the length of height will be at least 2 and can be up to (10^5).

Strategy

1. Two Pointers Approach:
   • Use two pointers, one at the beginning (left) and one at the end (right) of the array.
   • Calculate the area formed between the left and right pointers.
   • Move the pointer pointing to the shorter line towards the other pointer in hopes of finding a taller line and potentially a larger area.
   • Keep track of the maximum area found during the process.

This approach ensures we consider all potential containers while optimizing by skipping unnecessary calculations when we know no larger area can be formed with the current pointers.

Code

public class Solution {
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int maxArea = 0;

        while (left < right) {
            // Calculate the width and height to determine the area of the current container
            int width = right - left;
            int currentHeight = Math.min(height[left], height[right]);
            int currentArea = width * currentHeight;

            // Update maxArea if we find a larger area
            if (currentArea > maxArea) {
                maxArea = currentArea;
            }

            // Move the pointer pointing to the shorter line inwards
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return maxArea;
    }
}

Time Complexity

• Time Complexity: (O(n)), where (n) is the length of the height array. The two-pointer approach efficiently covers the entire array in a single traversal.
• Space Complexity: (O(1)), since we’re using only a constant amount of extra space.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?