This is our solution and implementation to problem #11: Container With Most Water on LeetCode.
Our code is written in Java. If you want to code your solution in a different language, no worries, as the core concepts will carry over from language to language. This page includes our analysis of the problem, our implementation strategy our video which outlines our analysis and implementation approach, a breakdown on the space and time complexity, and the full code implementation.
Note: the code and contents here might be slightly different than what is in the video. We've made some improvements to some of the code since recording.
If you would like to view the original problem and solve it, please visit: Container With Most Water on LeetCode.
Problem Analysis
We are given a scenario where we have a series of walls on a 2D surface. We want to pour water into this structure in a way that maximizes the amount of water we can hold. The water is poured by selecting two walls as the containers, then pour water until the container is filled as much as possible without spilling over. Note that we treat the walls themselves as having no area, so we don't need to factor that into our calculation. Once the algorithm finishes, it will return the area of the maximum amount of water that can be contained.
Implementation Strategy
A simple way to implement the solution is to perform a quadratic iteration, which means that for each wall, we check all remaining walls and calculate the available areas. While this would work, it is very inefficient with a time complexity of O(n^2). We can implement a solution which runs in linear time. The whiteboard diagram below explores how to do this. The input heights are: [2, 3, 1, 4, 7, 5, 4]; the diagram shows this using a grid where the x-axis has each wall evenly spaced and the y-axis shows the heights of each wall. Under the diagram, we explore an algorithm approach which uses two iterators instead of just one. Instead of performing a nested iteration, we use the left and right iterators to get the area of the water as it would appear if those two walls were selected, then moves the left iterator to the right if the left wall is smaller than the right, or moves the right iterator to the left if the right wall is smaller. This is guaranteed to find the best answer, because at any point: if the iterator pointing to the smaller of two walls is not moved, any subsequent area found by moving the other iterator will be even worse than the current solution. To summarize the algorith:
- Initialize an int leftPointer as 0.
- Initialize an int rightPointer as height.length - 1. In other words, it will point to the last wall.
- While we still have walls to consider (while rightPointer > leftPointer):
- Calculate area: Min(leftPointerWall, rightPointerWall) * (rightPointer - leftPointer).
- If it's larger than the best one we've found so far, set this as the best option so far.
- If leftPointerWall > rightPointerWall, decrement rightPointer.
- Else: decrement leftPointer.
- Return the best found solution.
Space and Time Complexity
The space complexity is O(1), as we only use a small, constant number of variables and space regardless of the input size. The time complexity is O(n) as we never revisit a wall once we have moved beyond it.
Additional Resources
Full Code
Our solution is given in the Java code below:
All of our solutions are hosted on GitHub. The code on this page was pulled from the repo.