mediumTwo PointersPure DSA~22 min
Max Bandwidth Container
A network planner models link capacities as vertical bars on a chart. Picking any two links forms a 'channel' whose usable bandwidth is the shorter of the two heights times the distance between them. Find the maximum bandwidth achievable by any pair.
Problem
Given an array height of n non-negative integers, choose two indices i < j to maximise min(height[i], height[j]) * (j - i). Return that maximum value.
Input
An array height of length n (2 ≤ n ≤ 10^5), each value in [0, 10^4].
Output
A single integer — the maximum container area.
Constraints
- 2 ≤ n ≤ 100,000
- 0 ≤ height[i] ≤ 10,000
- Width is the index distance j − i
Examples
Example 1
Input
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output
49
Indices 1 and 8 (heights 8 and 7) give min(8,7) * (8−1) = 7 * 7 = 49, the maximum.
Example 2
Input
height = [1, 1]
Output
1
min(1,1) * (1−0) = 1.