How does The Interns Company match students with internships?

We use a combination of AI-powered matching algorithms and human expertise to connect students with internship opportunities that align with their skills, interests, and career goals.

Are the internship opportunities exclusive?

Yes, many of our partner companies offer positions exclusively through our platform that you won't find on public job boards or career sites.

Is there a cost to use The Interns Company?

Our basic matching service is free for students. Premium services like one-on-one interview coaching and resume reviews may have associated fees.

Container With Most Water

MediumAcceptance: 57.4%

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 that together with the x-axis form a container, such that the container contains the most water. Return the maximum amount of water a container can store.

Constraints:

n == height.length
2 <= n <= 10^5
0 <= height[i] <= 10^4

Input Format:

An integer array height

Output Format:

Return the maximum amount of water a container can store

Examples:

Example 1:

Input:

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

Output:

Explanation:

The maximum area is obtained by choosing the 2nd and 8th lines, with heights 8 and 7. The area is min(8, 7) * (8 - 1) = 7 * 7 = 49.

Example 2:

Input:

height = [1,1]

Output:

Explanation:

The maximum area is min(1, 1) * (2 - 1) = 1 * 1 = 1.

Solutions

Two Pointers Approach

Time: O(n)

Space: O(1)

Use two pointers starting from both ends of the array and move the pointer with the smaller height inward.

Brute Force Approach

Time: O(n²)

Space: O(1)

Check all possible pairs of lines and calculate the area for each pair.

Algorithm Walkthrough

Example input: nums = [1,8,6,2,5,4,8,3,7]

Step-by-step execution:

left=0, right=8, width=8, height=min(1,7)=1, area=8, maxWater=8
height[left]=1 < height[right]=7, so move left: left=1
left=1, right=8, width=7, height=min(8,7)=7, area=49, maxWater=49
height[left]=8 > height[right]=7, so move right: right=7
left=1, right=7, width=6, height=min(8,3)=3, area=18, maxWater=49
height[left]=8 > height[right]=3, so move right: right=6
left=1, right=6, width=5, height=min(8,8)=8, area=40, maxWater=49
height[left]=8 == height[right]=8, either move, move right: right=5
left=1, right=5, width=4, height=min(8,4)=4, area=16, maxWater=49
height[left]=8 > height[right]=4, so move right: right=4
left=1, right=4, width=3, height=min(8,5)=5, area=15, maxWater=49
height[left]=8 > height[right]=5, so move right: right=3
left=1, right=3, width=2, height=min(8,2)=2, area=4, maxWater=49
height[left]=8 > height[right]=2, so move right: right=2
left=1, right=2, width=1, height=min(8,6)=6, area=6, maxWater=49
left=1, right=2, left < right is false, exit loop
Return maxWater = 49

Hints

Hint 1

Try using two pointers, one at the beginning and one at the end of the array.

Hint 2

Move the pointer with the smaller height inward.

Hint 3

The area is limited by the smaller height and the distance between the lines.

Video Tutorial

Container With Most Water - Two Pointers Approach

YouTube•Learn the Container With Most Water solution step-by-step

Video tutorials can be a great way to understand algorithms visually

Visualization

Visualize the two pointers moving from both ends of the array and calculating the area at each step.

Key visualization elements:

current pointers
current area
maximum area

Asked By

Amazon Google Microsoft Apple Bloomberg

Implementation Notes

This problem demonstrates the efficiency of the two-pointers technique for problems involving linear scanning of an array from both ends.