Skip to main content

Leetcode 11: Container With Most Water

1. Problem Statement (Simple Explanation):


You’re given an array height of length n.

  • At each index i, there is a vertical line from (i, 0) to (i, height[i]).

  • Choose two different lines, at indices i and j (i < j), and form a container with the x-axis.

The amount of water this container can hold is:

area=(j-i)×min(height[i],height[j])

You must find the maximum possible area over all pairs (i, j) and return it.

  • You cannot tilt/slant the container.


2. Examples:


Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]

Possible pairs (showing a few):

  • Lines at 1 and 8 (0-based indices):
    width = 8 − 1 = 7, min height = 8 → area = 56 (not actually correct; max is 49 using lines 1 and 8 indices 1 & 8? Let’s pick correct example)

The optimal pair is at indices 1 and 8 (heights 8 and 7):

  • width = 8 - 1 = 7

  • height = min(8, 7) = 7

  • area = 7 * 7 = 49

Output: 49


Example 2:

Input: height = [1,1]

Only one pair: indices 0 and 1:

  • width = 1

  • height = min(1, 1) = 1

  • area = 1 * 1 = 1

Output: 1


3. Approach 1 – Brute Force (O(n²)):


Intuition:


Try all pairs of lines (i, j):

  • Compute area for each pair.

  • Track the maximum.


Algorithm:


  1. Initialize maxArea = 0.

  2. For each i from 0 to n - 1:

    • For each j from i + 1 to n - 1:

      • width = j - i

      • height = min(height[i], height[j])

      • area = width * height

      • Update maxArea = max(maxArea, area).

  3. Return maxArea.


Pseudo-code (Brute Force):



Complexity:


  • Time: O(n²) → too slow for n up to 10^5.

  • Space: O(1) extra.

We need a better solution.


4. Approach 2 – Two Pointers (Optimal, O(n)):


This is the classic solution.


Intuition:


We want:

max0≤i<j<n(j-i)⋅min(height[i],height[j])

Key observation:

  • The area is limited by the shorter of the two lines.

  • For a fixed pair (i, j), if we want a bigger area, we need:

    • a larger width or

    • a taller minimum height.

We start with the widest container:

  • left = 0, right = n - 1.

Then:

  • Compute area for (left, right).

  • Move one pointer inward:

    • Always move the pointer that points to the shorter line.

  • Why?
    Because:

    • If we move the pointer at the taller line, the width decreases, and the min height stays limited by the shorter line (which we kept), so the area cannot increase by moving the taller one.

    • Only by moving the shorter one can we possibly find a taller line that may increase min(height[left], height[right]) enough to compensate for the smaller width.

We repeat until left >= right.


Algorithm (Step-by-Step):


  1. Initialize:

    • left = 0

    • right = n - 1

    • maxArea = 0

  2. While left < right:

    • width = right - left

    • h = min(height[left], height[right])

    • area = width * h

    • Update maxArea = max(maxArea, area)

    • If height[left] < height[right]:

      • move left++ (trying to find a taller left line)

    • Else:

      • move right-- (trying to find a taller right line)

  3. After loop, return maxArea.


Pseudo-code (Two Pointers):



Complexity:


  • Time: O(n)

  • Space: O(1)

Meets constraints and is the standard optimal solution.


5. Java code:



6. C code:



7. C++ code:



8. Python code:


9. JavaScript code:



Comments

Post a Comment

Popular posts from this blog

Leetcode 1: Two Sum

  Leetcode Link: https://leetcode.com/problems/two-sum/ 1. Problem Statement (Simple Explanation) You are given: An array of integers nums An integer target You need to  return the indices of two numbers in the array  such that: Conditions: Each input has  exactly one solution . You  cannot use the same element twice . You can return the answer in  any order . 2. Examples Example 1 Input:                                    nums = [2, 7, 11, 15], target = 9 Output:                                 [0, 1] Explanation:                     nums[0]+nums[1]=2+7=9              So we return [0, 1]. Example 2 Input:           ...
Post a Comment
Read more

Leetcode 3: Longest Substring Without Repeating Characters

  Leetcode Link 1. Problem Statement (Simple Explanation) You are given a string s. You need to find the length of the longest substring of s that does not  contain any repeated characters. A substring is a contiguous sequence of characters in the string. You must return an integer length, not the substring itself. 2. Examples Example 1 Input: s = "abcabcbb" Output: 3 Explanation: Some substrings without repeating characters: "abc", "bca", "cab"The longest length is 3. Example 2 Input: s = "bbbbb" Output: 1 Explanation: All substrings that are valid are just "b". The longest length is 1. Example 3 Input:   s = "pwwkew" Output:   3 Explanation: Possible substrings without repetition: "pw", "wke", "kew". "wke" or "kew" have length 3. "pwke" is not valid because it’s not contiguous in the original string (p and k are separated by ww). Constraints...
Post a Comment
Read more

Leetcode 2: Add Two Numbers

Leetcode Link: https://leetcode.com/problems/add-two-numbers/ 1. Problem Statement (Simple Explanation) You are given  two non-empty linked lists , l1 and l2, that represent two non-negative integers. Each node contains a  single digit . The digits are stored in  reverse order  (i.e., the 1’s digit is at the head). You need to  add the two numbers  and return the  sum as a linked list , also in reverse order. You can assume: There are  no leading zeros , except when the number itself is 0. 2. Examples Example 1 Input:                l1 = [2,4,3]                l2 = [5,6,4]           Interpreting linked lists as numbers (reverse order): l1 represents 342 l2 represents 465 Output:                [7,0,8] Explanation:        ...
Post a Comment
Read more