Balanced Tree Span Evaluator — Problem Statement & Solution Guide

Two PointersHardContainer With Most Water

TimeO(n)

SpaceO(1)

Problem Description

Given a list of non-negative integers representing the height of each line, calculate the maximum area between two lines using the Container With Most Water methodology.

DSA Pattern Breakdown

"Balanced Tree Span Evaluator"

hard

WHY DOES IT MATTER?

The two‑pointer pattern transforms a quadratic search into linear time by exploiting ordered relationships in the data. Mastery of this pattern signals a candidate's ability to recognize hidden monotonicity and apply greedy reductions—skills essential for scaling algorithms in performance‑critical systems.

OPTIMIZATION CHALLENGE

The key insight is that the container's height is bounded by the shorter line, so discarding that line cannot eliminate any better solution. This single, deterministic move at each iteration eliminates an entire class of pairs, collapsing the combinatorial explosion to a single pass.

REAL-WORLD CONNECTION

Think of a water reservoir bounded by two hills; moving the lower hill inward simulates draining water to find the deepest possible basin. In distributed storage, similar logic is used to locate optimal replication pairs by shrinking the search window based on latency or capacity constraints.

During an interview, write the two‑pointer loop first, then immediately add the max‑area update and the pointer‑movement condition. Keep the code tight—no extra data structures—so you can verbally walk through the greedy proof while the compiler checks syntax.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The "Container With Most Water" problem is a classic illustration of the two‑pointer technique applied to a monotonic search space. Each element in the input array represents the height of a vertical line drawn at its index; the area between any two lines is the product of the distance between their indices and the smaller of the two heights. A naive O(n²) scan enumerates every pair, but this quickly becomes infeasible for n in the order of 10⁵ or higher because the number of pairwise calculations grows quadratically. The optimal paradigm leverages the observation that the current area is limited by the shorter line, so moving the longer line inward cannot increase the area – only moving the shorter line might. By initializing pointers at the extreme ends and iteratively discarding the shorter side, we guarantee that every potential maximal container is examined exactly once, collapsing the search to linear time.

This approach exemplifies a greedy reduction of the solution space: each step makes a locally optimal choice (dropping the shorter line) that does not preclude the global optimum. The proof hinges on the fact that any container formed with the discarded line and any interior line would have a width smaller than the current width while the height cannot exceed the discarded line's height, thus cannot surpass the current area. Consequently, the algorithm converges in O(n) time with O(1) auxiliary space, making it the de‑facto solution for large‑scale instances encountered in interview settings and real‑world data pipelines.

Interview Questions on This Problem

Q1How would you modify the two‑pointer solution to also return the indices of the lines that form the maximum area?

Maintain two variables, maxArea and a pair (leftIdx, rightIdx). Whenever a new area exceeds maxArea, update both the area and the index pair. The rest of the algorithm remains unchanged, still running in O(n) time and O(1) space.

Q2If the input array can contain negative heights (interpreted as lines below the x‑axis), does the standard two‑pointer algorithm still work? Why or why not?

No. The area definition assumes non‑negative heights because area is the product of distance and the minimum of two heights; a negative height would invert the sign, breaking the monotonicity argument. You would need to preprocess the array to treat negative values as zero or adjust the problem definition, which changes the optimal strategy.

Q3Explain how you could parallelize the search for the maximum container on a distributed system handling billions of height measurements.

Divide the array into overlapping chunks where each chunk includes a small buffer of elements from its neighboring chunk. Each worker computes the local maximum container within its segment using the two‑pointer method. After all workers finish, a reducer merges the results by considering containers that span across chunk boundaries using the buffered elements, ensuring the global optimum is found with O(n/p) work per worker and minimal communication overhead.

Examples

Example 1

Input

[1, 8, 6, 2, 5, 4, 8, 3, 7]

Output

Explanation: Step-by-step: Given the input [1, 8, 6, 2, 5, 4, 8, 3, 7], we first initialize two pointers, one at the start and one at the end of the array. The area between the first and last lines is 1*8 = 8. Then we move the pointer of the shorter line (line 1) towards the other pointer. The area between the second and last lines is 2*8 = 16, but this is not the maximum area. The maximum area is between the first and second lines which is 1*8 = 8.

Example 2

Input

[1, 1]

Output

Explanation: Step-by-step: Given the input [1, 1], we first initialize two pointers, one at the start and one at the end of the array. The area between the first and last lines is 1*1 = 1. Since there are no other lines, the maximum area is indeed 1.

Constraints

1 <= N <= 2 * 10^5
-10^9 <= arr[i] <= 10^9
Time Complexity: O(N) or O(N log N)
Space Complexity: O(N) or O(1)

Optimal Approach & Strategy

Use two pointers at the array ends, compute area, move the pointer at the shorter line inward, and repeat until pointers cross.

Brute Force Approach

Check every possible pair of lines, compute the area for each, and keep the maximum. This requires two nested loops.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

function solution(heights) {
   let maxArea = 0;
   let left = 0;
   let right = heights.length - 1;
   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--;
       }
   }
   return maxArea;
}

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

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

def solution(heights):
   maxArea = 0
   left = 0
   right = len(heights) - 1
   while left < right:
       area = min(heights[left], heights[right]) * (right - left)
       maxArea = max(maxArea, area)
       if heights[left] < heights[right]:
           left += 1
       else:
           right -= 1
   return maxArea

function solution(heights) {
   let maxArea = 0;
   let left = 0;
   let right = heights.length - 1;
   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--;
       }
   }
   return maxArea;
}

Asked in Top Tech Interviews

UberCred

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 Evaluator Solution

Problem Statement

Input

Output

Input

Output

Constraints

More Two Pointers

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Balanced Tree Span Evaluator — 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