DEV Community

Mahdi SHamlou | مهدی شاملو
Mahdi SHamlou | مهدی شاملو

Posted on Edited on

Mahdi Shamlou | Solving LeetCode #11: Container With Most Water — Step by Step

Hey everyone! Mahdi Shamlou here again — back with another LeetCode classic problem.

Today, we're going to solve LeetCode #11: Container With Most Water.

Mahdi Shamlou

This problem is a good example of how starting with a simple solution can help us understand a problem, but sometimes we need to think differently to make our code efficient.

Let's get started!

1. Understanding the Problem

We are given an array called height.

Each element represents the height of a vertical line. The position of each element represents its horizontal position.

We need to choose two lines that, together with the x-axis, can hold the maximum amount of water.

The amount of water depends on two things:

  • The distance between the two lines (width).
  • The height of the shorter line.

So, we can calculate the area like this:

area = (right - left) * min(height[left], height[right])
Enter fullscreen mode Exit fullscreen mode

Our goal is to find the maximum possible area.

2. My First Approach: Brute Force

My first idea was simple: check every possible pair of lines.

I used two nested loops:

  • The first loop selects the left line.
  • The second loop selects the right line.
  • For every pair, I calculate the area.
  • I keep track of the maximum area.

The logic looks like this:

max_area = 0

for i in range(len(height)):
    for j in range(i + 1, len(height)):
        width = j - i
        current_area = width * min(height[i], height[j])

        max_area = max(max_area, current_area)
Enter fullscreen mode Exit fullscreen mode

This approach works correctly, but there is a problem.

We are checking every possible pair, which means the time complexity is O(n²).

When I submitted this solution to LeetCode, I got:

Time Limit Exceeded — 56 / 65 testcases passed.

This was a good reminder that getting the correct answer is not always enough. We also need to consider performance.

3. Can C++ Solve the Problem?

At first, I considered whether using C++ instead of Python could make the brute-force solution fast enough.

C++ is generally faster than Python, so it might reduce the execution time.

However, changing the programming language does not change the algorithm's time complexity.

The brute-force approach is still O(n²).

So, instead of only trying to make the same algorithm faster, I decided to look for a better algorithm.

4. The Optimized Approach: Two Pointers

The key observation is that we don't need to check every possible pair.

We can start with two pointers:

  • left starts at the beginning of the array.
  • right starts at the end of the array.

At every step:

  1. Calculate the width between the two pointers.
  2. Find the shorter line.
  3. Calculate the current area.
  4. Update the maximum area if necessary.
  5. Move the pointer that points to the shorter line.

Why do we move the shorter line?

Because the shorter line limits the amount of water we can hold.

Imagine that the left line is shorter than the right line.

If we move the right pointer, the width becomes smaller, but the limiting height cannot become greater than the current left line's height.

That means we cannot get a better area by keeping the same shorter line.

So, we move the left pointer and look for a taller line.

The same logic applies when the right line is shorter.

This is the main idea behind the Two Pointers approach.

5. My Final Python Solution

After applying this idea, my solution became:

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left = 0
        right = len(height) - 1

        max_area = 0

        while left < right:
            width = right - left

            current_area = width * min(
                height[left],
                height[right]
            )

            max_area = max(max_area, current_area)

            if height[left] < height[right]:
                left += 1
            else:
                right -= 1

        return max_area
Enter fullscreen mode Exit fullscreen mode

6. How Does It Work?

Let's look at the important part:

if height[left] < height[right]:
    left += 1
else:
    right -= 1
Enter fullscreen mode Exit fullscreen mode

This condition decides which pointer should move.

  • If the left line is shorter, move left forward.
  • Otherwise, move right backward.

We continue until both pointers meet.

Notice that we only move one pointer in each iteration. We never need to check all possible pairs.

7. Complexity Analysis

Let's compare both approaches:

Approach Time Complexity Space Complexity
Brute Force O(n²) O(1)
Two Pointers O(n) O(1)

The optimized solution has:

  • Time Complexity: O(n) — We move each pointer through the array at most once.
  • Space Complexity: O(1) — We only use a few variables, regardless of the input size.

That's a big improvement over the brute-force approach!

8. What Did I Learn?

This problem taught me an important lesson.

My first solution was correct, but it wasn't efficient enough for larger inputs.

Instead of trying to solve the performance problem by changing the programming language, I needed to improve the algorithm itself.

The Two Pointers technique helped me reduce the time complexity from O(n²) to O(n).

I think this is one of the most important things about solving algorithm problems: sometimes the best improvement comes from changing the way we think about the problem.

Final Thoughts

I started with a simple Brute Force solution, got a Time Limit Exceeded result, and then improved it using Two Pointers.

This is exactly why I enjoy solving LeetCode problems. Every problem gives me an opportunity to improve my problem-solving skills.

What about you? Have you used the Two Pointers technique in other problems? Let me know in the comments!

You can also find my LeetCode solutions in my GitHub repository:

GitHub: mahdi0shamlou/LeetCode


Mahdi Shamlou

Author: Mahdi Shamlou
Author: مهدی شاملو

Top comments (0)