How hard is LeetCode 42. Trapping Rain Water?

LeetCode 42. Trapping Rain Water is rated Hard on LeetCode.

What is the time complexity of LeetCode 42. Trapping Rain Water?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 42. Trapping Rain Water?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 42. Trapping Rain Water cover?

LeetCode 42. Trapping Rain Water is tagged Stack, Array, Two Pointers, Dynamic Programming and Monotonic Stack on LeetCode.

Trapping Rain Water — LeetCode 42 Python Solution

HardStackArrayTwo PointersDynamic ProgrammingMonotonic Stack

Problem: #42
Pattern: Stack
Reading time: 2 min
Source: leetcode.com

The problem

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.

Example

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Python solution

Python

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        left = [height[0]] * n
        right = [height[-1]] * n
        for i in range(1, n):
            left[i] = max(left[i - 1], height[i])
            right[n - i - 1] = max(right[n - i], height[n - i - 1])
        return sum(min(l, r) - h for l, r, h in zip(left, right, height))

Complexity

Measure	Complexity
Time	O(n)
Space	O(n) auxiliary

Pattern: Stack

When the most recent unresolved thing is the one that matters, use a stack. LeetCode 42. Trapping Rain Water is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Stack.

The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.

On study lists

This problem is on NeetCode 150, Grind 75 and Top Interview 150.

Frequently asked questions

How hard is LeetCode 42. Trapping Rain Water?: LeetCode 42. Trapping Rain Water is rated Hard on LeetCode.
What is the time complexity of LeetCode 42. Trapping Rain Water?: The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 42. Trapping Rain Water?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 42. Trapping Rain Water cover?: LeetCode 42. Trapping Rain Water is tagged Stack, Array, Two Pointers, Dynamic Programming and Monotonic Stack on LeetCode.