Container With Most Water

📋

Problem

Imagine you have vertical lines on a graph representing walls, and you want to find two walls that can hold the most water between them.

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i are at (i, ai) and (i, 0). Find two lines, which together with the x-axis forms a container, such that the container contains the most water. Return the maximum amount of water a container can store.

1 ≤ n ≤ 10^50 ≤ ai ≤ 10^4 for each 1 ≤ i ≤ n

Edge cases: All heights are zero → max area is 0Only one line → max area is 0 (no container)Two lines with same height → area is height * distance

</>

IDE

def maxArea(height: list[int]) -> int:public int maxArea(int[] height)int maxArea(vector<int> &height)function maxArea(height)

def maxArea(height):
    # Write your solution here
    pass

class Solution {
    public int maxArea(int[] height) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int maxArea(vector<int> &height) {
    // Write your solution here
    return 0;
}

function maxArea(height) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Returning 0 for all inputs due to missing or incorrect pointer movement and area calculation.✅ Initialize max_area=0 and update it by calculating area at each pointer position; move pointer at shorter line.

Wrong: 49 (correct) but fails on t3_01 with output 3Greedy trap: moving pointer at taller line instead of shorter line causes missing max area.✅ Always move the pointer at the shorter line to explore potentially larger areas.

Wrong: Non-zero for empty input or single element inputNo base case handling for empty or single-element arrays.✅ Add checks: if len(height) < 2: return 0.

Wrong: TLE on large inputUsing brute force nested loops O(n^2) approach instead of two-pointer O(n).✅ Implement two-pointer approach moving pointers inward based on shorter line.

✓

Test Cases

Focus on handling minimal inputs and zero heights correctly before moving on.

Ensure pointer movement logic is correct to avoid common greedy mistakes.

Optimize your solution to linear time using two pointers to handle large inputs efficiently.

t1_01basic

Input{"height":[1,8,6,2,5,4,8,3,7]}

Expected49

⏱ Performance - must finish in 2000ms

The max area is formed between lines at index 1 (height 8) and index 8 (height 7). Width is 7, height is min(8,7)=7, area=7*7=49.

💡 Try using two pointers starting at opposite ends of the array.

💡 Move the pointer pointing to the shorter line inward to potentially find a taller line.

💡 Calculate area at each step as width * min(height[left], height[right]) and update max area.

Why it failed: Incorrect max area indicates failure to correctly update max area or move pointers properly. Fix by ensuring to move the pointer at the shorter line and update max area at each step.

✓ Correctly implements two-pointer approach with proper pointer movement and area calculation.

t1_02basic

Input{"height":[4,3,2,1,4]}

Expected16

⏱ Performance - must finish in 2000ms

Max area between index 0 and 4: width=4, height=min(4,4)=4, area=16.

💡 Consider the container formed by the first and last lines initially.

💡 Move the pointer at the shorter line inward to find a potentially larger area.

💡 Keep track of the maximum area found during pointer movements.

Why it failed: Failing to consider the container between first and last lines or incorrect pointer movement leads to wrong max area. Fix by initializing max area with first and last lines and moving pointers correctly.

✓ Properly calculates max area by evaluating all valid pairs using two-pointer technique.

t2_01edge

Input{"height":[]}

Expected0

⏱ Performance - must finish in 2000ms

Empty input means no lines, so max area is 0.

💡 Check how your code handles empty input arrays.

💡 Ensure that when n=0, the function returns 0 without errors.

💡 Add a base case to return 0 if input array is empty.

Why it failed: Code crashes or returns non-zero for empty input. Fix by adding a check: if not height: return 0.

✓ Correctly returns 0 for empty input.

t2_02edge

Input{"height":[5]}

Expected0

⏱ Performance - must finish in 2000ms

Only one line means no container can be formed, so max area is 0.

💡 Consider the minimum number of lines needed to form a container.

💡 If there is only one line, the max area must be zero.

💡 Add a condition to return 0 if length of height is less than 2.

Why it failed: Code returns non-zero or crashes with single element input. Fix by returning 0 if len(height) < 2.

✓ Correctly returns 0 when only one line is present.

t2_03edge

Input{"height":[0,0,0,0]}

Expected0

⏱ Performance - must finish in 2000ms

All heights zero means no water can be contained, so max area is 0.

💡 Check how your code handles lines with zero height.

💡 Area is width * min(height[left], height[right]); zero height yields zero area.

💡 Ensure max area updates correctly even if all heights are zero.

Why it failed: Code returns non-zero max area when all heights are zero. Fix by correctly calculating area as zero when min height is zero.

✓ Correctly returns 0 when all heights are zero.

t3_01corner

Input{"height":[1,2,4,3]}

Expected4

⏱ Performance - must finish in 2000ms

Max area between index 1 and 3: width=2, height=min(2,3)=2, area=4.

💡 Beware of greedy traps: always moving the pointer at the shorter line is key.

💡 Check if your code mistakenly moves the pointer at the taller line.

💡 Fix pointer movement to always move the pointer at the shorter line to find max area.

Why it failed: Greedy trap: moving pointer at taller line causes missing max area. Fix by moving pointer at shorter line only.

✓ Correctly moves pointers at shorter line, avoiding greedy trap.

t3_02corner

Input{"height":[1,1,1,1,1]}

Expected4

⏱ Performance - must finish in 2000ms

Max area between index 0 and 4: width=4, height=1, area=4.

💡 Check if your code handles all equal heights correctly.

💡 Ensure max area updates even if heights are identical.

💡 Fix by always calculating area at each pointer position and updating max area.

Why it failed: Code fails to update max area when all heights are equal. Fix by always calculating and updating max area at each step.

✓ Correctly handles all equal heights and finds max area.

t3_03corner

Input{"height":[5,4,3,2,1]}

Expected6

⏱ Performance - must finish in 2000ms

Max area between index 0 and 2: width=2, height=min(5,3)=3, area=6.

💡 Test if your code handles strictly decreasing heights correctly.

💡 Check pointer movement logic when heights decrease monotonically.

💡 Fix by moving pointer at shorter line and updating max area at each step.

Why it failed: Code fails on strictly decreasing heights due to incorrect pointer movement. Fix by moving pointer at shorter line only.

✓ Correctly handles strictly decreasing heights with proper pointer movement.

t4_01performance

Input{"height":[10000,9999,9998,9997,9996,9995,9994,9993,9992,9991,9990,9989,9988,9987,9986,9985,9984,9983,9982,9981,9980,9979,9978,9977,9976,9975,9974,9973,9972,9971,9970,9969,9968,9967,9966,9965,9964,9963,9962,9961,9960,9959,9958,9957,9956,9955,9954,9953,9952,9951,9950,9949,9948,9947,9946,9945,9944,9943,9942,9941,9940,9939,9938,9937,9936,9935,9934,9933,9932,9931,9930,9929,9928,9927,9926,9925,9924,9923,9922,9921,9920,9919,9918,9917,9916,9915,9914,9913,9912,9911,9910,9909,9908,9907,9906,9905,9904,9903,9902,9901]}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100 with large heights decreasing by 1 each step. Algorithm must run in O(n) time within 2 seconds.

💡 Brute force O(n^2) approach will time out for n=100.

💡 Use two-pointer technique with O(n) time complexity.

💡 Move pointers inward based on shorter line to find max area efficiently.

Why it failed: TLE occurs due to O(n^2) brute force approach. Fix by implementing two-pointer O(n) solution.

✓ Algorithm runs in O(n) time, passing performance constraints.

Practice

1. You are given an integer array and a target integer. The task is to find three integers in the array whose sum is closest to the target. Which approach guarantees an optimal solution with O(n²) time complexity?

easy

A. Sort the array and use a fixed pointer with two pointers scanning from both ends.

B. Use a brute force triple nested loop to check all triplets.

C. Apply dynamic programming to store sums of pairs and find closest triplet sum.

D. Use a greedy approach by picking the closest element to target and then two others.

Solution

1. Step 1: Understand problem constraints

   The problem requires finding three numbers whose sum is closest to a target, which suggests checking combinations efficiently.

2. Step 2: Identify approach with O(n²) complexity

   Sorting the array allows fixing one element and using two pointers to find pairs that sum closest to the remaining target, achieving O(n²) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting + two pointers is classic for 3Sum Closest [OK]

Hint: Sorting + two pointers reduces complexity to O(n²) [OK]

Common Mistakes:

• Thinking brute force is optimal
• Confusing DP with this problem
• Assuming greedy works for closest sum

2. Given the following code and input array [3, 2, 2, 3] with val = 3, what is the returned new length and the array slice arr[:new_len] after execution?

easy

A. 2, [2, 2]

B. 3, [2, 2, 3]

C. 2, [3, 2]

D. 4, [2, 2, 3, 3]

Solution

1. Step 1: Trace first iteration

   start=0, end=3; nums[0]=3 equals val, swap nums[0] and nums[3], array becomes [3,2,2,3], end=2

2. Step 2: Trace subsequent iterations

   start=0, nums[0]=3 equals val, swap nums[0] and nums[2], array becomes [2,2,3,3], end=1; start=0, nums[0]=2 not val, start=1, nums[1]=2 not val, start=2 > end=1 loop ends; return start=2

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Final length 2 with first two elements [2, 2] [OK]

Hint: Swap val to end, increment start only if not val [OK]

Common Mistakes:

• Off-by-one errors in loop condition
• Not decrementing end after swap

3. The following code attempts to count pairs with absolute difference at most K using binary search. Identify the line containing the subtle bug that causes incorrect counting for some inputs.

import bisect

def count_pairs_buggy(nums, K):
    count = 0
    n = len(nums)
    for i in range(n - 1):
        target = nums[i] + K
        j = bisect.bisect_right(nums, target, i) - 1
        if j > i:
            count += j - i
    return count

medium

A. Line 5: for i in range(n - 1):

B. Line 7: target = nums[i] + K

C. Line 8: j = bisect.bisect_right(nums, target, i) - 1

D. Line 9: if j > i:

Solution

1. Step 1: Understand bisect_right usage

   bisect_right should start searching from i + 1 to avoid counting pairs where j ≤ i.

2. Step 2: Identify bug in line 8

   Using i as the start index includes nums[i] itself, causing pairs with i == j or double counting.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Changing i to i + 1 fixes the bug [OK]

Hint: bisect must start from i+1 to avoid invalid pairs [OK]

Common Mistakes:

• Starting binary search at i instead of i+1
• Off-by-one errors in bisect indices
• Counting pairs where i >= j

4. Identify the bug in the following code snippet for removing elements equal to val from nums in-place:

medium

A. The end pointer is not decremented after swapping, causing infinite loop

B. The start pointer is incremented even when a swap occurs

C. The condition in the while loop should be start < end, not start <= end

D. Swapping elements without checking if nums[end] is also val

Solution

1. Step 1: Analyze pointer updates after swap

   After swapping nums[start] and nums[end], end must be decremented to exclude the swapped val at the end.

2. Step 2: Consequence of missing end decrement

   Without end--, the loop may repeatedly swap the same elements, causing infinite loop or incorrect results.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing end decrement after swap breaks loop progress [OK]

Hint: Always decrement end after swapping val to end [OK]

Common Mistakes:

• Forgetting to decrement end after swap
• Incrementing start incorrectly after swap

5. Suppose you want to reverse a string but the input is a very large immutable string (e.g., Python str) instead of a mutable list. Which approach correctly handles this constraint efficiently?

hard

A. Convert the string to a list, reverse it using two pointers, then join back to a string.

B. Use a brute force approach creating a new reversed string by concatenation in a loop.

C. Use the recursive two-pointer approach on the string directly, swapping characters in-place.

D. Use a dynamic programming approach to build the reversed string from substrings.

Solution

1. Step 1: Understand immutability constraint

   Strings are immutable in Python, so in-place swaps are impossible directly on the string.

2. Step 2: Choose efficient workaround

   Converting to a list allows in-place two-pointer swaps, then joining back creates the reversed string efficiently in O(n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Only Convert the string to a list, reverse it using two pointers, then join back to a string. respects immutability and is efficient [OK]

Hint: Immutable strings require conversion to mutable type for in-place reversal [OK]

Common Mistakes:

• Trying to swap characters in immutable string
• Using inefficient string concatenation in loop
• Misapplying DP to string reversal