DSA Visualizations | Hello Interview

Trapping Rain Water

DESCRIPTION (credit Leetcode.com)

Write a function to calculate the total amount of water trapped between bars on an elevation map, where each bar's width is 1. The input is given as an array of n non-negative integers height representing the height of each bar.

EXAMPLES

Input:


height = [3, 4, 1, 2, 2, 5, 1, 0, 2]

Output:

Run your code to see results here

Explanation

We can use the two-pointer technique to solve this problem in O(n) time and O(1) space.

In order for any index in the array to be able to trap rain water, there must be higher bars on both the left and right side of the index. For example, index 2 in the following array has height 1. It can trap water because there are higher bars to the left and right of it.

To calculate the exact amount of water that can be trapped at index 2, we first take the minimum height of the highest bars to the left and right of it, which in this case is 4. We then subtract the height of the bar at index 2, which is 1,

So if we knew the height of the highest bars to the left and right of every index, we could iterate through the array and calculate the amount of water that can be trapped at each index.

But we don't need to know the exact height of both the highest bars to the left and right of every index. For example, let's say we know the highest bar to the right of index 7 with height 0 has a height of 2.

If we also knew that there exists a higher bar than 2 anywhere to the left of index 7, then we also know that the minimum height of the highest bars to the left and right of index 7 is 2. This means that we have enough information to calculate the amount of water that can be trapped at index 7, which is 2 - 0 = 2.

This is the insight behind how the two-pointer technique can be used to solve this problem. We initialize two pointers left and right at opposite ends of the array. We also keep two variables leftMax and rightMax to keep track of the highest bars each pointer has seen.


def trappingWater(heights):
  left, right = 0, len(heights) - 1
  leftMax, rightMax = heights[left], heights[right]
  count = 0

  while left + 1 < right:
    if rightMax > leftMax:
      left += 1
      if heights[left] > leftMax:
        leftMax = heights[left]
      else:
        count += leftMax - heights[left]
    else:
      right -= 1
      if heights[right] > rightMax:
        rightMax = heights[right]
      else:
        count += rightMax - heights[right]

  return count

trapping rain water

0 / 1

We now use the values of leftMax and rightMax to visit every single index in the array exactly once. We start by comparing leftMax and rightMax. In this case, leftMax is smaller than rightMax, so we know that:

The maximum height of the highest bar to the right of right - 1 is rightMax
There exists a higher bar than rightMax somewhere to the left of right

These two facts mean that we have enough information to calculate the amount of water that can be trapped at index right - 1. So first we move the right pointer back by 1:


def trappingWater(heights):
  left, right = 0, len(heights) - 1
  leftMax, rightMax = heights[left], heights[right]
  count = 0

  while left + 1 < right:
    if rightMax > leftMax:
      left += 1
      if heights[left] > leftMax:
        leftMax = heights[left]
      else:
        count += leftMax - heights[left]
    else:
      right -= 1
      if heights[right] > rightMax:
        rightMax = heights[right]
      else:
        count += rightMax - heights[right]

  return count

Count:

initialize pointers

0 / 1

There are two possible cases to consider when calculating the amount of water that can be trapped at the current index of right:

The height of the bar at index right is smaller than rightMax
The height of the bar at index right is greater than or equal to rightMax

In our case, the height of the bar at index right is smaller than rightMax, so we know that the amount of water that can be trapped at index 1 is rightMax - height[right], and we can move to the next iteration, which follows the same logic:


def trappingWater(heights):
  left, right = 0, len(heights) - 1
  leftMax, rightMax = heights[left], heights[right]
  count = 0

  while left + 1 < right:
    if rightMax > leftMax:
      left += 1
      if heights[left] > leftMax:
        leftMax = heights[left]
      else:
        count += leftMax - heights[left]
    else:
      right -= 1
      if heights[right] > rightMax:
        rightMax = heights[right]
      else:
        count += rightMax - heights[right]

  return count

Count:

move right pointer

0 / 4

Now, we run into case 2, where height[right] is greater than or equal to rightMax. This means we can't trap any water at this index, so instead we update rightMax to the height of the bar at index right to prepare for the next iteration.


def trappingWater(heights):
  left, right = 0, len(heights) - 1
  leftMax, rightMax = heights[left], heights[right]
  count = 0

  while left + 1 < right:
    if rightMax > leftMax:
      left += 1
      if heights[left] > leftMax:
        leftMax = heights[left]
      else:
        count += leftMax - heights[left]
    else:
      right -= 1
      if heights[right] > rightMax:
        rightMax = heights[right]
      else:
        count += rightMax - heights[right]

  return count

Count:

move right pointer

0 / 2

The same logic applies when leftMax is less than rightMax, and this continues until every index has been visited exactly once, for a total time complexity of O(n) and a space complexity of O(1).


def trappingWater(heights):
  left, right = 0, len(heights) - 1
  leftMax, rightMax = heights[left], heights[right]
  count = 0

  while left + 1 < right:
    if rightMax > leftMax:
      left += 1
      if heights[left] > leftMax:
        leftMax = heights[left]
      else:
        count += leftMax - heights[left]
    else:
      right -= 1
      if heights[right] > rightMax:
        rightMax = heights[right]
      else:
        count += rightMax - heights[right]

  return count

Count:

update leftMax

0 / 7

Solution


def trappingWater(heights):
  left, right = 0, len(heights) - 1
  leftMax, rightMax = heights[left], heights[right]
  count = 0

  while left + 1 < right:
    if rightMax > leftMax:
      left += 1
      if heights[left] > leftMax:
        leftMax = heights[left]
      else:
        count += leftMax - heights[left]
    else:
      right -= 1
      if heights[right] > rightMax:
        rightMax = heights[right]
      else:
        count += rightMax - heights[right]

  return count

trapping rain water

0 / 16

Next: Overview

Your account is free and you can post anonymously if you choose.

Loading comments...

Back to Home

Eliminating Pairs

Overview

Container With Most Water

3-Sum

Triangle Numbers

Pointers as Regions

Move Zeroes

Sort Colors

Trapping Rain Water

Variable-Length

Overview

Longest Substring Without Repeating Characters

Longest Repeating Character Replacement

Fixed-Length

Overview

Maximum Sum of Subarrays of Size K

Max Points You Can Obtain From Cards

Max Sum of Distinct Subarrays Length k

Overview

Can Attend Meetings

Insert Interval

Non-Overlapping Intervals

Merge Intervals

Employee Free Time

Overview

Valid Parentheses

Decode String

Longest Valid Parentheses

Monotonic Stack

Overview

Daily Temperatures

Largest Rectangle in Histogram

Overview

Linked List Cycle

Palindrome Linked List

Remove Nth Node From End of List

Reorder List

Swap Nodes in Pairs

Overview

Apple Harvest (Koko Eating Bananas)

Search in Rotated Sorted Array

Overview

Kth Largest Element in an Array

K Closest Points to Origin

Find K Closest Elements

Merge K Sorted Lists

Introduction

Binary Trees

Overview

Level Order Sum

Rightmost Node

Zigzag Level Order

Maximum Width of Binary Tree

Graphs

Overview

Minimum Knight Moves

Rotting Oranges

01-Matrix

Bus Routes

Overview

Word Search

Solution Space Trees

Subsets

Generate Parentheses

Combination Sum

Topological Sort

Overview

Course Schedule

Course Schedule II

Fundamentals

Solving a Question with Dynamic Programming

Counting Bits

Decode Ways

Maximal Square

Unique Paths

Longest Increasing Subsequence

Word Break

Maximum Profit in Job Scheduling

Overview

Best Time to Buy and Sell Stock

Gas Station

Jump Game

Overview

Implement Trie Methods

Prefix Matching

Overview

Count Vowels in Substrings

Subarray Sum Equals K

Spiral Matrix

Rotate Image

Set Matrix Zeroes

Sort Colors

Sliding Window: Overview

Trapping Rain Water

DESCRIPTION (credit Leetcode.com)

EXAMPLES

Input:


height = [3, 4, 1, 2, 2, 5, 1, 0, 2]

Output:

Run your code to see results here

Explanation

We can use the two-pointer technique to solve this problem in O(n) time and O(1) space.

So if we knew the height of the highest bars to the left and right of every index, we could iterate through the array and calculate the amount of water that can be trapped at each index.


def trappingWater(heights):
  left, right = 0, len(heights) - 1
  leftMax, rightMax = heights[left], heights[right]
  count = 0

  while left + 1 < right:
    if rightMax > leftMax:
      left += 1
      if heights[left] > leftMax:
        leftMax = heights[left]
      else:
        count += leftMax - heights[left]
    else:
      right -= 1
      if heights[right] > rightMax:
        rightMax = heights[right]
      else:
        count += rightMax - heights[right]

  return count

trapping rain water

0 / 1

The maximum height of the highest bar to the right of right - 1 is rightMax
There exists a higher bar than rightMax somewhere to the left of right

These two facts mean that we have enough information to calculate the amount of water that can be trapped at index right - 1. So first we move the right pointer back by 1:


def trappingWater(heights):
  left, right = 0, len(heights) - 1
  leftMax, rightMax = heights[left], heights[right]
  count = 0

  while left + 1 < right:
    if rightMax > leftMax:
      left += 1
      if heights[left] > leftMax:
        leftMax = heights[left]
      else:
        count += leftMax - heights[left]
    else:
      right -= 1
      if heights[right] > rightMax:
        rightMax = heights[right]
      else:
        count += rightMax - heights[right]

  return count

Count:

initialize pointers

0 / 1

There are two possible cases to consider when calculating the amount of water that can be trapped at the current index of right:

The height of the bar at index right is smaller than rightMax
The height of the bar at index right is greater than or equal to rightMax


def trappingWater(heights):
  left, right = 0, len(heights) - 1
  leftMax, rightMax = heights[left], heights[right]
  count = 0

  while left + 1 < right:
    if rightMax > leftMax:
      left += 1
      if heights[left] > leftMax:
        leftMax = heights[left]
      else:
        count += leftMax - heights[left]
    else:
      right -= 1
      if heights[right] > rightMax:
        rightMax = heights[right]
      else:
        count += rightMax - heights[right]

  return count

Count:

move right pointer

0 / 4


def trappingWater(heights):
  left, right = 0, len(heights) - 1
  leftMax, rightMax = heights[left], heights[right]
  count = 0

  while left + 1 < right:
    if rightMax > leftMax:
      left += 1
      if heights[left] > leftMax:
        leftMax = heights[left]
      else:
        count += leftMax - heights[left]
    else:
      right -= 1
      if heights[right] > rightMax:
        rightMax = heights[right]
      else:
        count += rightMax - heights[right]

  return count

Count:

move right pointer

0 / 2

The same logic applies when leftMax is less than rightMax, and this continues until every index has been visited exactly once, for a total time complexity of O(n) and a space complexity of O(1).


def trappingWater(heights):
  left, right = 0, len(heights) - 1
  leftMax, rightMax = heights[left], heights[right]
  count = 0

  while left + 1 < right:
    if rightMax > leftMax:
      left += 1
      if heights[left] > leftMax:
        leftMax = heights[left]
      else:
        count += leftMax - heights[left]
    else:
      right -= 1
      if heights[right] > rightMax:
        rightMax = heights[right]
      else:
        count += rightMax - heights[right]

  return count

Count:

update leftMax

0 / 7

Solution


def trappingWater(heights):
  left, right = 0, len(heights) - 1
  leftMax, rightMax = heights[left], heights[right]
  count = 0

  while left + 1 < right:
    if rightMax > leftMax:
      left += 1
      if heights[left] > leftMax:
        leftMax = heights[left]
      else:
        count += leftMax - heights[left]
    else:
      right -= 1
      if heights[right] > rightMax:
        rightMax = heights[right]
      else:
        count += rightMax - heights[right]

  return count

trapping rain water

0 / 16

Next: Overview

Your account is free and you can post anonymously if you choose.

Loading comments...

BlogBehavioral Interview Examples Interviewing for Experienced SWEs All Blog Posts

Compare UsCompare to Interviewing.io

LinksFAQ Schedule Mock Interviews Pricing Become a Coach Our Coaches Learn System Design Learn DSA

LegalTerms and Conditions Privacy Policy

Contactsupport@hellointerview.com7511 Greenwood Ave North
Unit #4238 Seattle, WA 98103