[LeetCode in Swift] Container With Most Water

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 than maxArea, we don’t update maxArea and move the right pointer to the left (because height[7] = 3 < height[1] = 8).
• In the fourth iteration, the area is 8*5 = 40. It’s still less than maxArea, so we keep maxArea as is and move the right pointer to the left.
• In the fifth iteration, the area is 4*4 = 16. MaxArea remains unchanged and we move the right pointer to the left.
• In the sixth iteration, the area is 5*3 = 15. MaxArea remains unchanged and we move the right pointer to the left.
• In the seventh iteration, the area is 2*2 = 4. MaxArea remains unchanged and we move the right pointer to the left.
• In the eighth and final iteration, the area is 6*1 = 6. MaxArea remains unchanged and since the right pointer has reached the left 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! 🔥