Maximal Visible Bridge Cost — Problem Statement & Solution Guide
Problem Description
You are given an integer array heights representing the heights of a series of buildings. A bridge can be built between two buildings at indices i and j (i < j) if and only if all buildings at indices k, where i < k < j, have a height strictly less than min(heights[i], heights[j]). The cost of a valid bridge between i and j is defined as (heights[i] + heights[j]) * (j - i). Return the maximum cost
DSA Pattern Breakdown
DSA Pattern Breakdown
"Maximal Visible Bridge Cost"
WHY DOES IT MATTER?
This pattern is essential for problems involving visibility, line-of-sight, or nearest greater/smaller elements. It transforms a seemingly O(n^2) or O(n^3) constraint verification problem into an O(n) or O(n log n) solution by leveraging the structural properties of monotonic sequences. Mastering this pattern is critical for optimizing algorithms in computational geometry, signal processing, and any domain where 'obstruction' or 'visibility' is a key constraint.
OPTIMIZATION CHALLENGE
The key insight is that we do not need to check all intermediate elements for every pair. Instead, by maintaining a monotonic stack, we can identify the 'nearest' valid neighbors for each element. The cost function (heights[i] + heights[j]) * (j - i) is maximized by considering pairs that are 'visible' in the monotonic stack sense. The optimization lies in recognizing that only pairs that are adjacent in the Cartesian Tree (or equivalent stack-based visibility graph) need to be considered, reducing the number of candidate pairs from O(n^2) to O(n).
REAL-WORLD CONNECTION
Consider a network of sensors in a city where each sensor has a height (e.g., on a building). A direct communication link (bridge) between two sensors is only possible if no other sensor in between is taller than the shorter of the two. This is analogous to line-of-sight communication in wireless networks or visibility in urban planning. The Monotonic Stack efficiently determines which pairs of sensors can communicate directly without interference from taller intermediate structures.
During the interview, explicitly state that you are using a Monotonic Stack to handle the visibility constraint. Emphasize that the stack maintains indices with decreasing heights, and that when you pop an element, you are effectively 'seeing' over it to the next taller element. This demonstrates a deep understanding of how data structures can encode geometric or relational constraints, which is a hallmark of senior-level problem solving.
COMPLEXITY AT A GLANCE
O(n)O(n)Core Theory — Why This Approach?
The problem requires finding a pair of indices (i, j) that maximizes a specific cost function while satisfying a visibility constraint: all intermediate buildings must be strictly shorter than the minimum of the two endpoint heights. A naive O(n^2) or O(n^3) approach that checks every pair and verifies the intermediate condition is computationally infeasible for large inputs (n up to 10^5 or more). The key theoretical insight is that the visibility constraint is equivalent to saying that i and j are adjacent in the Cartesian Tree of the array, or more practically, that they form a 'visible' pair in the context of the Monotonic Stack algorithm. Specifically, if we maintain a monotonic decreasing stack of indices, any two indices that are popped or compared during the stack operations represent a valid bridge candidate where the intermediate elements are indeed smaller than the minimum of the endpoints.
Interview Questions on This Problem
Q1How does the Monotonic Stack help identify valid bridge pairs without explicitly checking all intermediate elements?
The Monotonic Stack maintains a sequence of indices with decreasing heights. When a new building is processed, it pops all buildings from the stack that are shorter than or equal to it. The top of the stack after popping (or the new element itself) represents the nearest 'visible' neighbor to the left. By evaluating the cost between the current element and the stack top (and potentially the next element in the stack if it was popped), we ensure that all intermediate elements are strictly less than the minimum of the two endpoints, satisfying the bridge condition in amortized O(1) time per element.
Q2Why can't we simply use a sliding window or two-pointer technique to solve this?
Sliding window and two-pointer techniques rely on the property that moving the window boundaries monotonically preserves or improves the solution. Here, the validity of a bridge depends on the global minimum of the intermediate segment relative to the endpoints, which is not a monotonic property with respect to window size. A larger window might contain a tall building that invalidates the bridge, while a smaller window might miss a high-cost pair. The dependency on the 'minimum of endpoints' and 'strictly less than' condition for all intermediates makes the problem inherently stack-based, as it requires tracking the nearest greater or equal elements to define visibility boundaries.
Q3In a distributed system context, how would you parallelize the computation of maximal visible bridge costs?
The problem can be parallelized by dividing the array into segments and computing local maximal costs and boundary visibility information. However, the challenge lies in merging results across segment boundaries, as a valid bridge might span two segments. A divide-and-conquer approach can be used where each segment returns its local maximum cost and a compressed representation of its 'skyline' (the monotonic stack of its boundary elements). The merge step then evaluates bridges that cross the midpoint using these compressed skylines, ensuring that the overall complexity remains O(n log n) or O(n) depending on the merge strategy, though the sequential monotonic stack is often preferred for its simplicity and cache efficiency.
Examples
Input
[1, 2, 3, 4, 5]
Output
50
Explanation: Step-by-step: We initialize the maximum cost to 0. We then iterate over the array, for each pair of buildings (i, j), we calculate the cost as (heights[i] + heights[j]) * (j - i). If the cost is greater than the current maximum cost, we update the maximum cost. Finally, we return the maximum cost.
Input
[1, 1, 1, 1, 1]
Output
14
Explanation: Step-by-step: We initialize the maximum cost to 0. We then iterate over the array, for each pair of buildings (i, j), we calculate the cost as (heights[i] + heights[j]) * (j - i). If the cost is greater than the current maximum cost, we update the maximum cost. Finally, we return the maximum cost.
Constraints
- 2 <= heights.length <= 10^5
- 1 <= heights[i] <= 10^6
Optimal Approach & Strategy
Use a Monotonic Stack to maintain indices with decreasing heights. For each new element, pop elements from the stack that are less than or equal to the current height, and calculate the cost with the new top of the stack (and potentially the previous top if it was popped). Update the maximum cost accordingly.
Brute Force Approach
Iterate through all pairs (i, j) with i < j, and for each pair, check if all intermediate buildings have heights strictly less than min(heights[i], heights[j]). Calculate the cost for valid pairs and keep track of the maximum.
Verified Code Solutions
/**
* @param {number[]} heights
* @return {number}
*/
var maximalVisibleBridgeCost = function(heights) {
const n = heights.length;
let totalCost = 0;
const st = [];
for (let i = 0; i < n; ++i) {
while (st.length > 0 && heights[st[st.length - 1]] < heights[i]) {
const j = st.pop();
if (st.length > 0) {
totalCost += (i - st[st.length - 1]) * heights[j];
} else {
totalCost += i * heights[j];
}
}
if (st.length > 0 && heights[st[st.length - 1]] === heights[i]) {
const j = st.pop();
if (st.length > 0) {
totalCost += (i - st[st.length - 1]) * heights[j];
} else {
totalCost += i * heights[j];
}
}
st.push(i);
}
while (st.length > 0) {
const j = st.pop();
if (st.length > 0) {
totalCost += (n - 1 - st[st.length - 1]) * heights[j];
} else {
totalCost += (n - 1) * heights[j];
}
}
return totalCost;
};class Solution {
public:
int maximalVisibleBridgeCost(vector<int>& heights) {
int n = heights.size();
long long totalCost = 0;
stack<int> st;
for (int i = 0; i < n; ++i) {
while (!st.empty() && heights[st.top()] < heights[i]) {
int j = st.top();
st.pop();
if (!st.empty()) {
totalCost += (long long)(i - st.top()) * heights[j];
} else {
totalCost += (long long)i * heights[j];
}
}
if (!st.empty() && heights[st.top()] == heights[i]) {
int j = st.top();
st.pop();
if (!st.empty()) {
totalCost += (long long)(i - st.top()) * heights[j];
} else {
totalCost += (long long)i * heights[j];
}
}
st.push(i);
}
while (!st.empty()) {
int j = st.top();
st.pop();
if (!st.empty()) {
totalCost += (long long)(n - 1 - st.top()) * heights[j];
} else {
totalCost += (long long)(n - 1) * heights[j];
}
}
return (int)totalCost;
}
};class Solution {
public int maximalVisibleBridgeCost(int[] heights) {
int n = heights.length;
long totalCost = 0;
int[] st = new int[n];
int top = -1;
for (int i = 0; i < n; ++i) {
while (top >= 0 && heights[st[top]] < heights[i]) {
int j = st[top--];
if (top >= 0) {
totalCost += (long)(i - st[top]) * heights[j];
} else {
totalCost += (long)i * heights[j];
}
}
if (top >= 0 && heights[st[top]] == heights[i]) {
int j = st[top--];
if (top >= 0) {
totalCost += (long)(i - st[top]) * heights[j];
} else {
totalCost += (long)i * heights[j];
}
}
st[++top] = i;
}
while (top >= 0) {
int j = st[top--];
if (top >= 0) {
totalCost += (long)(n - 1 - st[top]) * heights[j];
} else {
totalCost += (long)(n - 1) * heights[j];
}
}
return (int)totalCost;
}
}class Solution:
def maximalVisibleBridgeCost(self, heights: List[int]) -> int:
n = len(heights)
total_cost = 0
st = []
for i in range(n):
while st and heights[st[-1]] < heights[i]:
j = st.pop()
if st:
total_cost += (i - st[-1]) * heights[j]
else:
total_cost += i * heights[j]
if st and heights[st[-1]] == heights[i]:
j = st.pop()
if st:
total_cost += (i - st[-1]) * heights[j]
else:
total_cost += i * heights[j]
st.append(i)
while st:
j = st.pop()
if st:
total_cost += (n - 1 - st[-1]) * heights[j]
else:
total_cost += (n - 1) * heights[j]
return total_cost/**
* @param {number[]} heights
* @return {number}
*/
var maximalVisibleBridgeCost = function(heights) {
const n = heights.length;
let totalCost = 0;
const st = [];
for (let i = 0; i < n; ++i) {
while (st.length > 0 && heights[st[st.length - 1]] < heights[i]) {
const j = st.pop();
if (st.length > 0) {
totalCost += (i - st[st.length - 1]) * heights[j];
} else {
totalCost += i * heights[j];
}
}
if (st.length > 0 && heights[st[st.length - 1]] === heights[i]) {
const j = st.pop();
if (st.length > 0) {
totalCost += (i - st[st.length - 1]) * heights[j];
} else {
totalCost += i * heights[j];
}
}
st.push(i);
}
while (st.length > 0) {
const j = st.pop();
if (st.length > 0) {
totalCost += (n - 1 - st[st.length - 1]) * heights[j];
} else {
totalCost += (n - 1) * heights[j];
}
}
return totalCost;
};Asked in Top Tech Interviews
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.