:orphan:

Trapping Rain Water
===================

.. highlight:: none

Problem
-------
https://leetcode.com/problems/trapping-rain-water/

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 1:**

|image1|

::


   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.

**Example 2:**

::


   Input: height = [4,2,0,3,2,5]
   Output: 9

 

**Constraints:**

- ``n == height.length``
- ``1 <= n <= 2 * 10``\ :sup:```4```
- ``0 <= height[i] <= 10``\ :sup:```5```

.. |image1| image:: https://assets.leetcode.com/uploads/2018/10/22/rainwatertrap.png

.. highlight:: python

Pattern
-------
Array, Two Pointers, Dynamic Programming, Stack, Monotonic Stack

Approaches
----------

.. tab-set::

    .. tab-item:: Two Pointers

        **Code**

        .. literalinclude:: ../problems/hard/trapping-rain-water/trapping_rain_water__two_pointers.py
            :language: python
            :lines: 10-

        **Test**

        >>> from trapping_rain_water__two_pointers import trap
        >>> trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])
        6
        >>> trap([4, 2, 0, 3, 2, 5])
        9

        .. autofunction:: trapping_rain_water__two_pointers.trap