Hello this is Derek! 👋
I’m starting a new blog series called LeetCode
in Swift, where I solve LeetCode
challenges in Swift, as I am in the middle of job hunting process and I need to prepare for possible upcoming coding interview.
This question is an medium difficulty in LeetCode
and shows history of being asked this question from interviews at Microsoft
, Google
, Amazon
, Adobe
, and Bloomberg
for 0–6 months of experience interviewees.
Disclaimer: I am not an experienced developer nor I have a Computer Science education background. My solution may not be the most efficient or effective approach in solving the problem. The reason why I am writing this in blog series is to help these logics, algorithms and approach to stick into my head, and to possibly help absolute beginners who is also facing similar problems.
Today’s challenge: Container With Most Water
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.
Notice that you may not slant the container.
Example 1:
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
Example 2:
Input: height = [1,1]
Output: 1
Constraints:
n == height.length
2 <= n <= 105
0 <= height[i] <= 104
Approach and Thought Process
In solving this problem, we will use the two-pointer technique, which is a commonly used strategy for solving array-related problems.
Our objective is to maximize the area formed between the vertical lines. The area is calculated as the product of the distance (width) between the two lines (left and right pointers) and the height of the shorter line (min(height[left], height[right])).
We initialize two pointers, one at the beginning of the array (left) and one at the end (right). We calculate the area and keep track of the maximum area observed (maxArea). Then, we move the pointers towards each other, always choosing to move the pointer that is at the shorter line. This is because moving the pointer at the taller line wouldn’t help in finding a larger area
.
Let’s break down the process:
Step 1. Initialize pointers and maxArea
We start by initializing two pointers, left
and right
, to the beginning and end of the array, respectively. We also initialize maxArea
to keep track of the maximum area we've calculated so far.
var left = 0
var right = height.count - 1
var maxArea = 0
Step 2. Calculate area and move pointers
We enter a while loop, which continues as long as left
is less than right
. In each iteration, we calculate the area
, update maxArea
if the current area is larger, and move either the left
or right
pointer.
If height[left]
is less than height[right]
, we increment left
; otherwise, we decrement right.
while left < right {
let h = min(height[left], height[right])
let w = right - left
let area = h * w
maxArea = max(maxArea, area)
if height[left] < height[right] {
left += 1
} else {
right -= 1
}
}
Step 3. Return maxArea
Finally, we return maxArea
, which is the maximum area of water the container can hold.
return maxArea
So our complete solution would look like this:
class Solution {
func maxArea(_ height: [Int]) -> Int {
// Use Two Pointer Technique
var left = 0
var right = height.count - 1
var maxArea = 0
while left < right {
let h = min(height[left], height[right])
let w = right - left
let area = h * w
maxArea = max(maxArea, area)
if height[left] < height[right] {
left += 1
} else {
right -= 1
}
}
return maxArea
}
}
Walkthrough Example
Let’s walk through an example with the following input: height = [1,8,6,2,5,4,8,3,7]
We initialize two pointers, left
and right
, at the beginning and end of the array respectively, and maxArea
as 0.
In the first iteration, the height
of the water is determined by the smaller of the two lines heights
, so h
= min(1, 7) = 1. The width
, w
, is right — left = 8–0 = 8. Thus, the area
of the water is 1*8 = 8. Since 8 is larger than the current maxArea
(0), we update maxArea
to 8. Since the line at the left
pointer is shorter than the right
one, we move the left
pointer one step to the right
.
In the second iteration, the height
becomes min(8, 7) = 7 and the width
becomes 7 (right — left = 7–1 = 7). So, the area
is 7*7 = 49. This is greater than the current maxArea
(8), so we update maxArea
to 49. The height
at the left
pointer (8) is greater than the height
at the right
pointer (7), so we move the right
pointer one step to the left
.
We continue this process, always moving the pointer that points to the shorter line. This way, we have the possibility to find a taller line that, combined with the larger of the two original lines, might form a container with greater area
.
Following this process, the next few steps look like this:
- In the third iteration, the
area
is calculated as 3*6 = 18. Since 18 is less thanmaxArea
, we don’t updatemaxArea
and move theright
pointer to theleft
(because height[7] = 3 < height[1] = 8). - In the fourth iteration, the
area
is 8*5 = 40. It’s still less thanmaxArea
, so we keepmaxArea
as is and move theright
pointer to theleft
. - In the fifth iteration, the
area
is 4*4 = 16.MaxArea
remains unchanged and we move theright
pointer to theleft
. - In the sixth iteration, the
area
is 5*3 = 15.MaxArea
remains unchanged and we move theright
pointer to theleft
. - In the seventh iteration, the
area
is 2*2 = 4.MaxArea
remains unchanged and we move theright
pointer to theleft
. - In the eighth and final iteration, the
area
is 6*1 = 6.MaxArea
remains unchanged and since theright
pointer has reached theleft
one, we end the iteration.
Therefore, the maximum area of water the container can contain, as per our solution, is 49
.
I hope this step-by-step breakdown clarifies how our algorithm works. Let’s test it on LeetCode to ensure it performs as expected!
And just like that, we have successfully solved another problem!
Time and Space Complexity Analysis
The time complexity of our solution is O(n)
, where n
is the number of lines. This is because we iterate over the array of heights
once.
The space complexity is O(1)
, as we only use a constant amount of space to store our variables.
I hope this explanation was helpful! As always, please feel free to ask any questions or share your thoughts in the comments section.
Stay tuned for more LeetCode solutions in Swift.
Until then, happy coding! 🔥