Glaze Channel Portions
Trapped volume at each index from height and width arrays
A recipe app models a long decorating channel as adjacent solid columns. Column i has height heights[i] and horizontal width widths[i]. All columns have the same front-to-back depth of one unit.
Glaze is poured until every hollow between the columns is filled. Excess glaze escapes beyond the two ends of the channel. The glaze settles horizontally, and the solid columns do not absorb it.
Return a list whose element at index i is the volume of glaze resting directly above column i.
More precisely, define the left boundary height for column i as the maximum height among columns 0 through i, inclusive. Define its right boundary height as the maximum height among columns i through the last column, inclusive. The retained glaze depth is the smaller of these two boundary heights minus heights[i]. Multiply this depth by widths[i] to obtain that column's volume.
Keep the result in the original column order. If the channel is empty, return an empty list.
Examples
Example 1
Input: heights = [4,1,2,4], widths = [1,2,1,3] Output: [0,6,2,0]
The two end columns contain the glaze. Both interior columns retain glaze, and the wider interior column contributes more volume for each unit of depth.
Example 2
Input: heights = [0,1,3,5], widths = [2,1,4,2] Output: [0,0,0,0]
The column heights never decrease, so glaze can escape toward the left without being trapped above any column.
Example 3
Input: heights = [3,0,5,1,4], widths = [1,3,2,2,1] Output: [0,9,0,6,0]
The tall middle column divides the channel into two hollows. Each hollow's fill level is limited by its shorter outer boundary.
Constraints
- 0 <= heights.length <= 8000
- widths.length == heights.length
- 0 <= heights[i] <= 1000000000
- 1 <= widths[i] <= 1000
The intended solution runs in O(n) time and uses O(1) auxiliary space beyond the returned list. Every individual returned volume is an integer that is exactly representable by a JavaScript Number.
Hints
Show hint 1Hint 1
Start with one pointer at each end. Which side can have its retained depth determined without examining all remaining columns?
Show hint 2Hint 2
Track the tallest column seen from each end. Advance the pointer at the shorter current column and calculate that column's volume immediately.
Follow-up questions
What an interviewer might ask once you have a working solution.
- Can you return only the total retained volume using constant auxiliary space?
- How would you solve the problem using prefix and suffix maximum arrays, and how would its memory usage compare?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem