How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Tesla.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Tesla during technical interviews.

Calculate trapped water between elevation bars

Company: Tesla

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Given an array of non-negative integers representing the heights of unit-width vertical bars, compute the total water retained after rainfall. Start by presenting a brute-force approach and analyze its time and space complexity. Then optimize to a linear-time solution that uses constant extra space, explain the intuition, and implement the final method.

Quick Answer: This question evaluates array manipulation, algorithmic optimization, and complexity analysis, specifically the ability to reason about time and space trade-offs and design a linear-time, constant-space approach for computing trapped water.

Given an array of non-negative integers `height` representing the heights of unit-width vertical bars laid side by side, compute the total amount of water that is trapped after it rains. Water collects in the dips between bars. For each position, the water held above it is bounded by the tallest bar to its left and the tallest bar to its right: the water level at that position is `min(maxLeft, maxRight)`, and the trapped water there is `min(maxLeft, maxRight) - height[i]` (never negative). The interviewer first asks for a brute-force approach and its complexity, then asks you to optimize to a linear-time, constant-extra-space solution and explain the intuition. Example: Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 Return the total units of trapped water.

Constraints

0 <= height.length <= 2 * 10^4
0 <= height[i] <= 10^5
The array may be empty, in which case the answer is 0.

Examples

Input: ([0,1,0,2,1,0,1,3,2,1,2,1],)

Expected Output: 6

Explanation: The canonical LeetCode 42 example: 6 units of water collect in the valleys between the bars.

Input: ([4,2,0,3,2,5],)

Expected Output: 9

Explanation: Water is bounded by the height-4 bar on the left and the height-5 bar on the right; the dip holds 9 units.

Input: ([],)

Expected Output: 0

Explanation: Empty array — no bars, so no water can be trapped.

Input: ([5],)

Expected Output: 0

Explanation: A single bar has no neighbors to trap water against.

Input: ([3,3,3,3],)

Expected Output: 0

Explanation: All bars are equal height — there are no dips, so no water collects.

Input: ([5,4,3,2,1],)

Expected Output: 0

Explanation: Strictly decreasing — water always spills off the right edge, trapping nothing.

Input: ([1,2,3,4,5],)

Expected Output: 0

Explanation: Strictly increasing — water spills off the left edge, trapping nothing.

Input: ([2,0,2],)

Expected Output: 2

Explanation: A minimal valley: the height-0 dip is bounded by two height-2 bars, trapping 2 units.

Input: ([5,0,0,0,5],)

Expected Output: 15

Explanation: A wide basin: three height-0 cells bounded by height-5 walls, each holding 5 units, for 15 total.

Hints

Brute force: for each index i, scan left and right to find the tallest bar on each side; the water above i is max(0, min(maxLeft, maxRight) - height[i]). This is O(n^2) time, O(1) space.
Precomputing prefix-max-from-left and suffix-max-from-right arrays drops the per-index scan to O(1), giving O(n) time but O(n) extra space.
To reach O(1) space, use two pointers from both ends. Track left_max and right_max as you move inward; always advance the side whose running max is smaller, because that side's water level is fully determined by it.
When left_max <= right_max, the water at the left pointer depends only on left_max (right_max is at least as tall), so you can safely add left_max - height[left] and step left forward. Symmetric reasoning applies on the right.

Quick Overview

This question evaluates array manipulation, algorithmic optimization, and complexity analysis, specifically the ability to reason about time and space trade-offs and design a linear-time, constant-space approach for computing trapped water.