Why Container With Most Water in DSA Typescript?

The Big Idea

Discover how a simple two-pointer trick saves you from endless, tiring checks!

The Scenario

Imagine you have a row of vertical lines on a graph, each with different heights. You want to find two lines that, together with the x-axis, can hold the most water. Doing this by checking every possible pair manually is like trying to find the biggest container by measuring every pair of walls one by one.

The Problem

Checking every pair of lines manually means a lot of repeated work. For example, if you have 100 lines, you would need to check 4,950 pairs! This is slow and tiring, and easy to make mistakes. It's like trying to find the tallest person in a crowd by asking every pair if they are taller than the other.

The Solution

The "Container With Most Water" approach uses two pointers starting at both ends of the line array. It moves the pointer with the smaller height inward, skipping unnecessary checks. This way, it quickly finds the best container without checking every pair, saving time and effort.

Before vs After

✗ Before

let maxArea = 0;
for (let i = 0; i < heights.length; i++) {
  for (let j = i + 1; j < heights.length; j++) {
    let area = Math.min(heights[i], heights[j]) * (j - i);
    if (area > maxArea) maxArea = area;
  }
}

✓ After

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

What It Enables

This method lets you find the largest container quickly, even with thousands of lines, making your program fast and efficient.

Real Life Example

Think of trying to find the widest and tallest gap between buildings to hold the most water during a rainstorm. Instead of measuring every gap, you start from the edges and move inward, quickly spotting the best spot.

Key Takeaways

Manual checking every pair is slow and inefficient.

Two-pointer technique smartly skips unnecessary checks.

Efficiently finds the maximum water container in linear time.

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