What is the time complexity of Container With Most Water?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Container With Most Water?

This problem uses Array, Two Pointers, Greedy. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Container With Most Water?

Insight 1: The area of the container is determined by the shorter of the two heights and the distance between the lines. Insight 2: A brute-force approach (checking every possible pair of lines) would be inefficient. A two-pointer approach is more efficient.

Which companies ask LeetCode 11. Container With Most Water in interviews?

This problem is frequently asked at Accenture, Accolite, Adobe, Amazon, Apple and 45 more companies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Container With Most Water - LeetCode 11 Solution

Container With Most Water - Complete Solution Guide

Container With Most Water is LeetCode problem 11, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

You are given an integer array height of length n . There are n vertical lines drawn such that the two endpoints of the i th 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 [

Detailed Explanation

The problem asks us to find the largest area of water that can be contained between two vertical lines, defined by their heights in the input array `height`, and the x-axis. The width of the container is the distance between the two lines, and the height is the minimum of the two line heights. The container cannot be slanted.

Solution Approach

The provided solution employs a two-pointer approach. Two pointers, `left` and `right`, are initialized to the beginning and end of the `height` array, respectively. The algorithm iteratively calculates the area formed by the lines at `left` and `right`, updates the maximum area seen so far, and moves either the `left` or `right` pointer based on which line is shorter. The pointer associated with the shorter line is moved towards the center in hopes of finding a taller line. This process continues until the two pointers meet.

Step-by-Step Algorithm

Step 1: Initialize two pointers, `left` to 0 and `right` to `len(height) - 1`.
Step 2: Initialize `max_area` to 0.
Step 3: While `left < right`, repeat steps 4-7.
Step 4: Calculate the width of the container as `width = right - left`.
Step 5: Calculate the height of the container as `h = min(height[left], height[right])`.
Step 6: Calculate the current area as `current_area = width * h`.
Step 7: Update `max_area = max(max_area, current_area)`.
Step 8: If `height[left] < height[right]`, increment `left`; otherwise, decrement `right`.
Step 9: Return `max_area`.

Key Insights

Insight 1: The area of the container is determined by the shorter of the two heights and the distance between the lines.
Insight 2: A brute-force approach (checking every possible pair of lines) would be inefficient. A two-pointer approach is more efficient.
Insight 3: Moving the pointer associated with the shorter height has the potential to increase the height of the container, thereby increasing the area. Moving the pointer associated with the taller height will always decrease the potential area (either decreasing width or maintaining/decreasing height).

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Array, Two Pointers, Greedy.

Companies

Asked at: Accenture, Accolite, Adobe, Amazon, Apple, Atlassian, Bloomberg, ByteDance, Citadel, Coveo, Deloitte, Flipkart, Goldman Sachs, HSBC, HashedIn, Infosys, Intel, J.P. Morgan, Lenskart, Mastercard, Meta, Microsoft, Miro, Myntra, Nutanix, Oracle, PayPal, Paytm, QBurst, RBC, SAP, Salesforce, Samsung, ServiceNow, Snowflake, Sprinklr, Tesla, TikTok, Uber, Visa, Walmart Labs, Wix, Yahoo, Yandex, Zoho, Zoom, Zopsmart, oyo, razorpay, tcs.

Container With Most Water | LeetCode 11

Medium

Array Two Pointers Greedy

Time: O(n)Space: O(1)

Solution Code

Available in:

class Solution {
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int max_area = 0;

        while (left < right) {
            int width = right - left;
            int h = Math.min(height[left], height[right]);
            int current_area = width * h;
            max_area = Math.max(max_area, current_area);

            if (height[left] < height[right]) {
                left += 1;
            } else {
                right -= 1;
            }
        }
        
        return max_area;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 11: Container With Most Water - Detailed explanation and solution approaches.

Topics

Array Two Pointers Greedy

Companies

AccentureAccoliteAdobeAmazonAppleAtlassianBloombergByteDance

Stats

Difficulty:Medium

Languages:4

Companies:50

Problem #:11

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

9 steps

1
Step 1: Initialize two pointers, `left` to 0 and `right` to `len(height) - 1`.
2
Step 2: Initialize `max_area` to 0.
3
Step 3: While `left < right`, repeat steps 4-7.
4
Step 4: Calculate the width of the container as `width = right - left`.
5
Step 5: Calculate the height of the container as `h = min(height[left], height[right])`.
6
Step 6: Calculate the current area as `current_area = width * h`.
7
Step 7: Update `max_area = max(max_area, current_area)`.
8
Step 8: If `height[left] < height[right]`, increment `left`; otherwise, decrement `right`.
9
Step 9: Return `max_area`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The two-pointer approach ensures that each element in the input array is visited at most once, leading to a linear time complexity. The algorithm only uses a few integer variables for calculations, leading to constant space complexity.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Brute-Force Approach

Iterate through all possible pairs of vertical lines and calculate the area for each pair, keeping track of the maximum area found. This approach considers every possible combination.

Time: O(n^2), where n is the length of the `height` array.Space: O(1)

Trade-offs: The brute-force approach is simple to understand but is inefficient for large input arrays. The two-pointer approach is much more efficient (O(n)) and is preferred for larger inputs.

✨

Key Insights

1Insight 1: The area of the container is determined by the shorter of the two heights and the distance between the lines.
2Insight 2: A brute-force approach (checking every possible pair of lines) would be inefficient. A two-pointer approach is more efficient.
3Insight 3: Moving the pointer associated with the shorter height has the potential to increase the height of the container, thereby increasing the area. Moving the pointer associated with the taller height will always decrease the potential area (either decreasing width or maintaining/decreasing height).

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Two Pointers

Using two indices to traverse data from different positions simultaneously.

Greedy Algorithm

Making the best choice at each step without looking ahead.

Edge Cases

Edge case 1: Array with only two elements (e.g., `[1, 1]`). The algorithm correctly calculates the area formed by these two lines and returns 1.
Edge case 2: Array with monotonically increasing heights (e.g., `[1, 2, 3, 4, 5]`). The algorithm correctly finds the maximum area by gradually reducing the width and increasing the height as the `left` pointer moves.
Edge case 3: Array with monotonically decreasing heights (e.g., `[5, 4, 3, 2, 1]`). The algorithm finds the correct area in similar way with previous edge case.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Incorrectly calculating the area by using the sum of the heights instead of the minimum of the heights. The minimum height determines the amount of water the container can hold.

✗Common mistake 2: Moving the wrong pointer (e.g., always moving the `right` pointer or always moving the `left` pointer). The optimal strategy is to move the pointer associated with the shorter height.

✗Common mistake 3: Not updating `max_area` after each area calculation. This would lead to the algorithm returning the area of the last container considered instead of the maximum area encountered.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Optimizing resource allocation where there are limited resources and varying demands. The 'height' can represent resource availability and the distance can be the time period for resource utilization. The goal is to maximize the overall utilization within the constraints.

🏦Real-world scenario 2: Finding the best placement for facilities (e.g., warehouses) along a transportation network (represented by array indices). The height can represent the potential market demand and the distance the cost or time of delivery. The goal is to place the facilities in a way that maximizes overall market coverage or profit.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Consider multiple approaches before coding. Mentioning alternatives shows breadth of knowledge.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: June 12, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 14

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 7

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJun 30

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

How do I avoid infinite loops with two pointers?

Always ensure your loop condition guarantees termination (typically left < right or slow != fast). Move at least one pointer in each iteration, and handle edge cases where pointers might not move (like skipping duplicates). Draw out pointer movement on paper first.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Container With Most Water"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether two pointers techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?