We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Trapping Rain Water II

Difficulty: Hard

Problem Description

Given an m x n integer matrix heightMap representing the height of each unit cell in a 2D elevation map, return the volume of water it can trap after raining.

Key Insights

  • Water can only be trapped in a cell if it is surrounded by taller cells.
  • The volume of water trapped in a cell depends on the height of the tallest cells surrounding it.
  • A priority queue (min-heap) can be used to efficiently track the lowest boundary of the surrounding cells.
  • A breadth-first search (BFS) can be employed to explore the height map and calculate the trapped water.

Space and Time Complexity

Time Complexity: O(m * n * log(m * n)), where m is the number of rows and n is the number of columns in the height map. Space Complexity: O(m * n) for the priority queue and visited array.

Solution

To solve the problem, we can use a priority queue (min-heap) to keep track of the cells' heights. We start by adding all the boundary cells to the queue, as these cannot trap any water. We then perform a BFS, popping the lowest cell from the heap and examining its neighbors. If a neighboring cell is lower than the current cell, we can trap water equal to the difference in height and mark that cell as visited. We then push the neighbor into the heap with its updated height (the maximum of its original height and the current cell's height). This process continues until all cells have been processed.

Code Solutions

import heapq

def trapRainWater(heightMap):
    if not heightMap or not heightMap[0]:
        return 0

    m, n = len(heightMap), len(heightMap[0])
    visited = [[False] * n for _ in range(m)]
    min_heap = []
    
    # Add all boundary cells to the heap
    for i in range(m):
        for j in range(n):
            if i == 0 or i == m - 1 or j == 0 or j == n - 1:
                heapq.heappush(min_heap, (heightMap[i][j], i, j))
                visited[i][j] = True

    water_trapped = 0
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    while min_heap:
        height, x, y = heapq.heappop(min_heap)
        
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            
            if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny]:
                visited[nx][ny] = True
                water_trapped += max(0, height - heightMap[nx][ny])
                heapq.heappush(min_heap, (max(height, heightMap[nx][ny]), nx, ny))

    return water_trapped
← Back to All Questions