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.

Optimize Trapping Rain Water | Tesla Coding Question

Quick Overview

This question evaluates algorithmic problem-solving with arrays and analysis of time-space trade-offs in the Coding & Algorithms domain, and is commonly asked to assess a candidate's ability to transform brute-force approaches into efficient linear-time solutions while reasoning about memory usage.

Optimize Trapping Rain Water

Company: Tesla

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

##### Question LeetCode 42. Trapping Rain Water – implement a brute-force solution, analyze its complexity, then optimize to an O(n) solution with O(n) space and discuss achieving O( 1) space. https://leetcode.com/problems/trapping-rain-water/description/

Quick Answer: This question evaluates algorithmic problem-solving with arrays and analysis of time-space trade-offs in the Coding & Algorithms domain, and is commonly asked to assess a candidate's ability to transform brute-force approaches into efficient linear-time solutions while reasoning about memory usage.

Given `n` non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining. The amount of water trapped above any index `i` is `min(maxLeft, maxRight) - height[i]`, where `maxLeft` is the tallest bar at or to the left of `i` and `maxRight` is the tallest bar at or to the right of `i` (water only accumulates if this value is positive). Write `trap(height)` returning the total units of trapped water. Approaches to consider: - Brute force: for each index scan left and right for the max bars — O(n^2) time, O(1) space. - Precompute prefix-max and suffix-max arrays — O(n) time, O(n) space. - Two-pointer sweep — O(n) time, O(1) space (the reference solution below). Example 1: Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 Example 2: Input: height = [4,2,0,3,2,5] Output: 9

Constraints

n == height.length
0 <= n <= 2 * 10^4
0 <= height[i] <= 10^5
An empty array returns 0.

Examples

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

Expected Output: 6

Explanation: Canonical LeetCode example; water pools in the dips between the taller bars for a total of 6 units.

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

Expected Output: 9

Explanation: Second canonical example; the bar of height 5 on the right and 4 on the left trap 9 units across the interior valley.

Input: ([],)

Expected Output: 0

Explanation: Empty elevation map traps no water.

Input: ([5],)

Expected Output: 0

Explanation: A single bar has no left/right pair to hold water.

Input: ([3,3],)

Expected Output: 0

Explanation: Two equal bars adjacent with nothing between them trap nothing.

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

Expected Output: 0

Explanation: Strictly decreasing: no bar to the right is tall enough to dam any water.

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

Expected Output: 0

Explanation: Strictly increasing: symmetric to the decreasing case, no water is trapped.

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

Expected Output: 2

Explanation: Simple valley: the single 0 is bounded by 2 on each side, trapping min(2,2)-0 = 2 units.

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

Expected Output: 1

Explanation: Asymmetric walls: index 1 holds min(4,3)-2 = 1 unit of water.

Hints

Water above index i equals min(maxLeft_i, maxRight_i) - height[i], counted only when positive.
Brute force recomputes maxLeft/maxRight per index in O(n) each, giving O(n^2). Precomputing both as prefix/suffix arrays drops it to O(n) time and O(n) space.
For O(1) space, walk two pointers inward from both ends. Whichever side has the smaller running max is the side whose water level is determined by that running max, so advance that pointer and accumulate runningMax - height.

Quick Overview