Balanced Tree Span Calculator 5 — Problem Statement & Solution Guide

Two PointersHardContainer With Most Water

TimeO(n)

SpaceO(1)

Problem Description

Balanced Tree Span Calculator 5

You are given an array of non‑negative integers where each element represents the height of a vertical line drawn at that index on a horizontal axis. Two lines together with the horizontal axis form a container that can hold a certain amount of liquid. The amount of liquid that can be held is determined by the width between the two lines (the difference of their indices) multiplied by the shorter of the two heights. Your task is to determine the maximum possible amount of liquid that can be contained by any pair of lines.

Input

The input consists of a single line containing space‑separated integers. The first integer, N, denotes the number of lines (1 ≤ N ≤ 10^5). The following N integers represent the heights of the lines (0 ≤ height ≤ 10^9).

Output

Print a single integer: the maximum area that can be formed by any two lines.

The problem is a classic two‑pointer challenge that requires an O(N) time solution and O(1) additional space.

DSA Pattern Breakdown

"Balanced Tree Span Calculator 5"

hard

WHY DOES IT MATTER?

Two‑pointer patterns turn quadratic pairwise comparisons into linear scans, a critical skill for any engineer dealing with large datasets where O(n²) is a deal‑breaker. Mastery of this pattern shows an ability to reason about monotonic constraints and greedy decisions.

OPTIMIZATION CHALLENGE

The key insight is that the area is bounded by the minimum height; therefore, any pair involving a line shorter than the current minimum cannot surpass the best area found so far, allowing us to safely discard it and move inward.

REAL-WORLD CONNECTION

Think of two water towers on a landscape: the amount of water you can store between them depends on the shorter tower and the distance. To maximize storage, you would start with the farthest towers and iteratively replace the shorter one with a taller one, mirroring the two‑pointer sweep in infrastructure planning.

During an interview, write the two‑pointer loop first, then add the max‑area update inside; this keeps the code short, avoids off‑by‑one errors, and demonstrates clear, incremental thinking.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The problem is a classic two‑pointer scenario often referred to as the "Container With Most Water". The naive solution examines every pair of lines, computing the area as the product of the distance between indices and the minimum of the two heights, which leads to O(n²) time – infeasible for large n (up to 10⁵ or more). The optimal paradigm leverages the monotonic property of the area function: for a fixed left pointer, moving the right pointer leftwards can only decrease the width, so the only way to potentially increase the area is to find a taller line. By initializing pointers at both ends and always moving the shorter side inward, we guarantee that any discarded pair could never yield a larger area than the best seen so far. This greedy two‑pointer sweep runs in linear time while using constant extra space, making it the optimal solution for this problem.

Interview Questions on This Problem

Q1How does the two‑pointer technique guarantee that we don't miss the optimal container when we always move the shorter line?

Because the area is limited by the shorter line, moving the longer line inward cannot increase the height bound; only a taller line on the shorter side can potentially increase the area despite the reduced width. Hence discarding the current shorter line is safe.

Q2If the input array contains duplicate heights, does the two‑pointer algorithm still work correctly?

Yes. Duplicate heights are treated like any other value; moving either pointer when heights are equal still preserves correctness because the width strictly decreases, and any future container must involve a line taller than the current minimum to beat the current max.

Q3Can you modify the algorithm to also return the indices of the lines that form the maximum container?

Maintain two variables to store the best left and right indices whenever a new maximum area is found; the rest of the algorithm remains unchanged.

Examples

Example 1

Input

9
1 8 6 2 5 4 8 3 7

Output

Explanation: Start with pointers at the ends (indices 0 and 8). The area is min(1,7)*8=8. Move the pointer at the smaller height (index 0). New area min(8,7)*7=49, which is larger. Continue moving pointers inward; no larger area is found. The maximum area is 49.

Example 2

Input

7
2 3 4 5 18 17 6

Output

Explanation: Initial pointers at indices 0 and 6 give area min(2,6)*6=12. Move the left pointer because 2 is smaller. New area min(3,6)*5=15. Move left pointer again: min(4,6)*4=16, which is the largest. Subsequent moves produce smaller areas. Thus the maximum area is 16.

Example 3

Input

2
1 1

Output

Explanation: Only one pair of lines exists. The width is 1 and the height is min(1,1)=1, so the area is 1.

Example 4

Input

5
4 3 2 1 4

Output

Explanation: Pointers start at indices 0 and 4: area min(4,4)*4=16. Moving either pointer inward only decreases the width or the minimum height, so 16 remains the maximum.

Constraints

1 <= N <= 100000
0 <= height <= 1000000000
The input array contains at least two elements
The algorithm must run in O(N) time and use O(1) extra space

Optimal Approach & Strategy

Use two pointers at the ends, move the pointer at the shorter line inward each step, updating the maximum area; this runs in O(n) time with O(1) extra space.

Brute Force Approach

Check every possible pair of lines, compute the area for each, and keep the maximum; this requires O(n²) time.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

function solution(nums) {
   let left = 0;
   let right = nums.length - 1;
   let maxSpan = 0;
   while (left < right) {
       let span = nums[left] * nums[right];
       maxSpan = Math.max(maxSpan, span);
       if (nums[left] < nums[right]) {
           left++;
       } else {
           right--;
       }
   }
   return maxSpan;
}

class Solution {
   public:
       int solution(vector<int>& nums) {
           int left = 0;
           int right = nums.size() - 1;
           int maxSpan = 0;
           while (left < right) {
               int span = nums[left] * nums[right];
               maxSpan = max(maxSpan, span);
               if (nums[left] < nums[right]) {
                   left++;
               } else {
                   right--;
               }
           }
           return maxSpan;
       }
   };

class Solution {
   public int solution(int[] nums) {
       int left = 0;
       int right = nums.length - 1;
       int maxSpan = 0;
       while (left < right) {
           int span = nums[left] * nums[right];
           maxSpan = Math.max(maxSpan, span);
           if (nums[left] < nums[right]) {
               left++;
           } else {
               right--;
           }
       }
       return maxSpan;
   }
}

def solution(nums):
   left = 0
   right = len(nums) - 1
   maxSpan = 0
   while left < right:
       span = nums[left] * nums[right]
       maxSpan = max(maxSpan, span)
       if nums[left] < nums[right]:
           left += 1
       else:
           right -= 1
   return maxSpan

function solution(nums) {
   let left = 0;
   let right = nums.length - 1;
   let maxSpan = 0;
   while (left < right) {
       let span = nums[left] * nums[right];
       maxSpan = Math.max(maxSpan, span);
       if (nums[left] < nums[right]) {
           left++;
       } else {
           right--;
       }
   }
   return maxSpan;
}

Asked in Top Tech Interviews

Morgan StanleyUber

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Balanced Tree Span Calculator 5 Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Two Pointers

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Balanced Tree Span Calculator 5 — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor