Container With Most Water in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main goal of the "Container With Most Water" problem?

To find two lines in an array that together with the x-axis form a container, such that the container holds the maximum amount of water.

intermediate

Why do we use two pointers in the optimal solution for "Container With Most Water"?

Two pointers start at both ends of the array and move inward to find the maximum area efficiently by comparing heights and moving the pointer with the smaller height.

beginner

How is the area calculated between two lines at positions i and j?

Area = (distance between i and j) * (minimum height of lines at i and j).

intermediate

What happens when the pointer at the smaller height moves inward in the two-pointer approach?

Moving the smaller height pointer inward may find a taller line that can increase the area, since the width decreases but height might increase.

intermediate

What is the time complexity of the two-pointer solution for "Container With Most Water"?

O(n), where n is the number of lines, because each pointer moves at most n times inward.

In the "Container With Most Water" problem, what does the height array represent?

A Water levels

B Widths of containers

C Distances between lines

D Heights of vertical lines on the x-axis

The height array represents the heights of vertical lines placed at each index on the x-axis.

Which pointer should move when comparing two heights in the two-pointer approach?

A Both pointers simultaneously

B Pointer at the taller line

C Pointer at the smaller line

D Neither pointer

Moving the pointer at the smaller height may find a taller line and potentially increase the area.

What is the initial position of the two pointers in the optimal solution?

A One at the start, one at the end

B Both at the start

C Both at the end

D Random positions

One pointer starts at the beginning and the other at the end of the array.

What does the area between two lines depend on?

A Minimum height and distance between lines

B Distance only

C Maximum height only

D Sum of heights

Area is calculated as the minimum height of the two lines multiplied by the distance between them.

What is the time complexity of the brute force approach for this problem?

A O(n log n)

B O(n^2)

C O(n)

D O(log n)

The brute force approach checks all pairs, resulting in O(n^2) time complexity.

Explain how the two-pointer technique works to solve the "Container With Most Water" problem efficiently.

Think about how moving the smaller height pointer can help find a bigger container.

Describe how to calculate the area between two lines and why the minimum height is used.

Imagine water filling between two walls of different heights.

Practice

1. What does the "Container With Most Water" problem ask you to find given an array of heights?

easy

A. The maximum area formed between two lines representing heights

B. The minimum height in the array

C. The sum of all heights in the array

D. The number of lines taller than a given height

Solution

1. Step 1: Understand the problem goal

   The problem asks to find two lines that together with the x-axis form a container holding the most water, which means the largest area between two heights.

2. Step 2: Identify what area means here

   The area is calculated by the distance between two lines multiplied by the smaller height of the two lines.

3. Final Answer:

   The maximum area formed between two lines representing heights -> Option A

4. Quick Check:

   Container area = max area between two heights [OK]

Hint: Look for two lines maximizing width and min height [OK]

Common Mistakes:

• Confusing area with sum of heights
• Choosing tallest lines without considering distance
• Ignoring the smaller height between two lines

2. Which of the following TypeScript function signatures correctly represents a function to solve the Container With Most Water problem?

easy

A. function maxArea(height: number[]): number

B. function maxArea(height: string): string

C. function maxArea(height: number): number[]

D. function maxArea(height: boolean[]): boolean

Solution

1. Step 1: Identify input and output types

   The input is an array of numbers representing heights, so type is number[]. The output is a single number representing max area.

2. Step 2: Match function signature

   function maxArea(height: number[]): number matches input as number[] and output as number, which is correct for this problem.

3. Final Answer:

   function maxArea(height: number[]): number -> Option A

4. Quick Check:

   Input array of numbers, output number [OK]

Hint: Input is array of numbers, output is a number [OK]

Common Mistakes:

• Using wrong input type like string or boolean
• Returning array instead of single number
• Mismatching input and output types

3. What will be the output of the following TypeScript code?

function maxArea(height: number[]): number {
  let left = 0, right = height.length - 1;
  let max = 0;
  while (left < right) {
    const area = Math.min(height[left], height[right]) * (right - left);
    max = Math.max(max, area);
    if (height[left] < height[right]) left++;
    else right--;
  }
  return max;
}

console.log(maxArea([1,8,6,2,5,4,8,3,7]));

medium

A. 56

B. 49

C. 64

D. 72

Solution

1. Step 1: Understand the two-pointer approach

   Start with left=0 and right=8 (length-1). Calculate area = min(height[left], height[right]) * (right-left). Move pointer with smaller height inward.

2. Step 2: Trace key iterations

   Initial area: min(1,7)*8=8
   Move left to 1 (height=8), area: min(8,7)*7=49 (max updated)
   Move right to 7 (height=3), area: min(8,3)*6=18
   Move right to 6 (height=8), area: min(8,8)*5=40
   Move right to 5 (height=4), area: min(8,4)*4=16
   Move right to 4 (height=5), area: min(8,5)*3=15
   Move right to 3 (height=2), area: min(8,2)*2=4
   Move right to 2 (height=6), area: min(8,6)*1=6
   Max area found is 49.
   Continue moving left pointer:
   left=2 (height=6), right=2 (height=6) loop ends.
   Actually, the maximum area is found earlier at 49, but let's check if any larger area exists.
   Check area at left=1, right=8: min(8,7)*7=49
   Check area at left=1, right=6: min(8,8)*5=40
   Check area at left=2, right=8: min(6,7)*6=42
   Check area at left=1, right=7: min(8,3)*6=18
   Check area at left=0, right=8: min(1,7)*8=8
   Check area at left=1, right=5: min(8,4)*4=16
   Check area at left=1, right=4: min(8,5)*3=15
   Check area at left=1, right=3: min(8,2)*2=4
   Check area at left=1, right=2: min(8,6)*1=6
   Check area at left=2, right=7: min(6,3)*5=15
   Check area at left=2, right=6: min(6,8)*4=24
   Check area at left=3, right=6: min(2,8)*3=6
   Check area at left=4, right=6: min(5,8)*2=10
   Check area at left=5, right=6: min(4,8)*1=4
   Maximum area is 49.
   However, the known correct answer for this input is 49, but the official LeetCode solution and common knowledge say the max area is 49.
   Therefore, correct answer is 49.

3. Final Answer:

   49 -> Option B

4. Quick Check:

   Max area = 49 [OK]

Hint: Use two pointers, move smaller height inward [OK]

Common Mistakes:

• Calculating area with max height instead of min
• Not updating max area correctly
• Moving wrong pointer in the loop

4. Identify the bug in this TypeScript function for Container With Most Water:

function maxArea(height: number[]): number {
  let left = 0;
  let right = height.length - 1;
  let max = 0;
  while (left <= right) {
    const area = Math.min(height[left], height[right]) * (right - left);
    max = Math.max(max, area);
    if (height[left] > height[right]) left++;
    else right--;
  }
  return max;
}

medium

A. The loop condition should be left < right, not left <= right

B. The area calculation should use max instead of min height

C. The pointers should move based on height[left] < height[right], not >

D. The max variable should be initialized to -Infinity

Solution

1. Step 1: Check pointer movement logic

   The algorithm moves the pointer with smaller height inward to try larger area. The code moves left pointer if height[left] > height[right], which is incorrect.

2. Step 2: Correct pointer movement condition

   It should move left pointer if height[left] < height[right], else move right pointer. This ensures we discard the smaller height side.

3. Final Answer:

   The pointers should move based on height[left] < height[right], not > -> Option C

4. Quick Check:

   Move pointer of smaller height [OK]

Hint: Move pointer at smaller height side [OK]

Common Mistakes:

• Using wrong comparison operator for pointer movement
• Including equal condition in loop causing extra iteration
• Using max height instead of min for area

5. Given an array of heights, how would you modify the two-pointer approach to find the maximum container area if the container must include the first line (index 0)?

hard

A. Calculate area for all pairs including index 0 using nested loops

B. Fix right pointer at 0 and move left pointer from start to end, calculating max area

C. Use two pointers starting at 1 and end-1, ignoring index 0

D. Fix left pointer at 0 and move right pointer from end to start, calculating max area

Solution

1. Step 1: Understand the constraint

   The container must include the first line at index 0, so left pointer stays fixed at 0.

2. Step 2: Move right pointer from the end towards 0

   Move right pointer from the last index towards 1, calculating area with fixed left pointer at 0, updating max area.

3. Step 3: Avoid nested loops for efficiency

   This approach keeps O(n) time by moving only one pointer, unlike nested loops which are O(n²).

4. Final Answer:

   Fix left pointer at 0 and move right pointer from end to start, calculating max area -> Option D

5. Quick Check:

   Fix one pointer, move other to find max area [OK]

Hint: Fix one pointer, move other to maximize area [OK]

Common Mistakes:

• Moving wrong pointer fixed at 0
• Using nested loops causing slow performance
• Ignoring the fixed pointer constraint