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! 🔥