Container With Most Water
Medium About 20 min Free, no account needed
Pick two lines that, with the x-axis, hold the most water.
The brief
Given height, where each element is the height of a vertical line at that x
position, pick two lines that together with the x-axis form a container holding
the most water. The area between lines i and j is
min(height[i], height[j]) * (j - i). Return that maximum area.
The obvious approach checks every pair of lines, O(n²). The hidden test
uses 200,000 lines, so that's too slow. MaxArea needs an approach that
scales better than checking every pair.
The area can exceed
int.MaxValue, so the method returns along.
Starter code
using System;
public class Solution
{
// TODO: return the maximum water area between two of the given lines.
public long MaxArea(int[] height)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Two pointers
- Walk a sorted or symmetric sequence from both ends, or fast and slow, instead of checking every pair.
- Greedy algorithms
- Make the locally best choice when an exchange argument proves it stays globally optimal.
Related katas
- Boats to Save People Medium Free Pair people into two-person boats under a weight limit, using as few boats as possible.
- Find the Duplicate Number Medium Free Find the one repeated value in an array of n+1 numbers from 1..n, without allocating a set to do it.
- Integer to Roman Medium Free Write Roman numerals the way Romans did - greedily.
- Longest Palindromic Substring (Length) Medium Free How long is the longest palindrome hiding in the string?