Container With Most Water Solution for Google

Company: Google · Difficulty: Medium · Topics: Array, Two Pointers, Greedy

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 ith line are (i, 0) and (i, height[i]).

Find two lines, which, together with the x-axis, forms a container, such that the container contains the maximum amount of water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Examples

Example 1:

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

Output: 49

Explanation: The maximum area is obtained by choosing height[1] = 8 and height[8] = 7.

Example 2:

Input: height = [1,1]

Output: 1

Explanation: The maximum area is obtained by choosing height[0] = 1 and height[1] = 1.

Intuition

The key insight is to use two pointers starting from the ends of the array. The area is limited by the shorter of the two heights, so we always move the pointer with the shorter height inward, as this gives us the best chance of finding a larger area.

Approach

1. Use two pointers (left and right) starting from the ends

2. Calculate the area between the two pointers

3. Move the pointer with the shorter height inward

4. Keep track of the maximum area found

Solution

⚠️ Disclaimer: Don't jump directly to the solution, try it out yourself first. Only look at the solution after you've given it a good attempt.

Solution: Two Pointers Approach

Time Complexity: O(n) - Single pass through the array

Space Complexity: O(1) - Constant extra space

More Google coding questions