1. Trapping Rain Water 3D
2. Sliding Window Maximum
3. Median of Two Sorted Arrays
4. First Missing Positive
5. Largest Rectangle in Histogram
6. Merge k Sorted Arrays
7. Longest Consecutive Sequence
8. Container With Most Water
9. Jump Game IV
10. Candy Distribution
11. Maximum Gap
12. Find Peak Element II
13. Shortest Unsorted Continuous Subarray
14. Minimum Operations to Reduce X to Zero
15. Count of Range Sum

16. Regular Expression Matching
17. Wildcard Matching
18. Longest Valid Parentheses
19. Minimum Window Substring
20. Substring Concatenation
21. Word Break II
22. Text Justification
23. Palindrome Partitioning II
24. Scramble String
25. Minimum Window Subsequence
26. Basic Calculator III
27. Integer to English Words
28. Distinct Subsequences II
29. String Transforms
30. Longest Chunked Palindrome

31. Burst Balloons
32. Cherry Pickup
33. Minimum Cost to Merge Stones
34. Count Palindromic Subsequences
35. Frog Jump
36. Maximum Profit Job Scheduling
37. Minimum Difficulty Job Schedule
38. Strange Printer
39. Tallest Billboard
40. Paint House III
41. Minimum Insertion Steps
42. Number of Ways to Paint Grid
43. Minimum Skips to Arrive on Time
44. Count Vowels Permutation
45. Reducing Dishes

46. Word Ladder II
47. Alien Dictionary
48. Swim in Rising Water
49. Sliding Puzzle
50. Bus Routes
51. Critical Connections
52. Cheapest Flights Within K Stops
53. Reconstruct Itinerary
54. Minimum Height Trees
55. Shortest Path with Obstacles
56. Network Delay Time
57. Parallel Courses
58. Minimum Refueling Stops
59. Find the City
60. Path with Maximum Probability

61. Serialize and Deserialize BST
62. Binary Tree Cameras
63. Recover BST
64. Sum of Distances in Tree
65. Vertical Order Traversal
66. Closest Leaf in Binary Tree
67. Delete Nodes And Return Forest
68. Lowest Common Ancestor Deepest Leaves
69. Maximum Difference Between Node and Ancestor
70. Distribute Coins in Binary Tree
71. Longest Univalue Path
72. Construct Tree from Preorder and Postorder
73. Path Sum IV
74. Smallest Subtree with Deepest Nodes
75. Binary Tree Maximum Path Sum
76. N-Queens II
77. Sudoku Solver
78. Expression Add Operators
79. Word Search II
80. Russian Doll Envelopes
81. LFU Cache
82. Design In-Memory File System
83. Robot Room Cleaner
84. Optimal Account Balancing
85. The Skyline Problem
86. Kth Smallest in Sorted Matrix
87. Range Sum Query 2D - Mutable
88. Minimum Arrows to Burst Balloons
89. Maximum Frequency Stack
90. Find Median from Data Stream
91. Minimum Cost to Connect Sticks
92. Minimum Deletions to Make Valid Sequence
93. Design Search Autocomplete System
94. Shortest Path in Hidden Graph
95. Minimum Operations to Make Subsequence
96. Minimum Number of Increments
97. Maximum Number of Non-Overlapping Substrings
98. Minimum Cost to Cut a Stick
99. Reconstruct Itinerary II
100. Swim in Rising Water II

#1 Trapping Rain Water 3D HARD

Hard

Array Heap BFS

Given an m x n matrix of positive integers representing the height of each unit cell in a 3D elevation map, compute the volume of water it is able to trap after raining. Water can only flow in four directions (up, down, left, right) to boundary cells.

Example:
Input: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
Output: 4
Explanation: After rain, water is trapped between the blocks. We have two small ponds (1 index unit and 3 index units) trapped.

Time: O(mn log(mn))

Space: O(mn)

Test Cases: 8

Acceptance: 32%

Time Complexity Space Complexity

Python Editor

import heapq
from typing import List

def trap_rain_water(heightMap: List[List[int]]) -> int:
    if not heightMap or not heightMap[0]:
        return 0
    
    m, n = len(heightMap), len(heightMap[0])
    heap = []
    visited = [[False] * n for _ in range(m)]
    
    # Add boundary cells to the heap
    for i in range(m):
        heapq.heappush(heap, (heightMap[i][0], i, 0))
        visited[i][0] = True
        heapq.heappush(heap, (heightMap[i][n-1], i, n-1))
        visited[i][n-1] = True
        
    for j in range(1, n-1):
        heapq.heappush(heap, (heightMap[0][j], 0, j))
        visited[0][j] = True
        heapq.heappush(heap, (heightMap[m-1][j], m-1, j))
        visited[m-1][j] = True
        
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    total_water = 0
    max_height = 0
    
    while heap:
        height, i, j = heapq.heappop(heap)
        max_height = max(max_height, height)
        
        for dx, dy in directions:
            ni, nj = i + dx, j + dy
            if 0 <= ni < m and 0 <= nj < n and not visited[ni][nj]:
                visited[ni][nj] = True
                if heightMap[ni][nj] < max_height:
                    total_water += max_height - heightMap[ni][nj]
                heapq.heappush(heap, (heightMap[ni][nj], ni, nj))
                
    return total_water

# Test the solution
if __name__ == "__main__":
    height_map = [
        [1, 4, 3, 1, 3, 2],
        [3, 2, 1, 3, 2, 4],
        [2, 3, 3, 2, 3, 1]
    ]
    print(trap_rain_water(height_map))  # Output: 4

Output

# Problem #1: Trapping Rain Water 3D

# Click "Run Code" to test your solution

# Output will appear here after execution

Solution Approach

Optimal Approach: Heap + BFS

This problem requires a heap to simulate the process of water trapping from boundaries to inner cells. The key insight is that the water height at each cell is determined by the minimum height of its boundary.

Add all boundary cells to a min-heap
Process cells in increasing height order
For each cell, update the max boundary height
For unvisited neighbors, calculate trapped water
Add neighbors to the heap for processing

Complexity Analysis

Time Complexity: O(mn log(mn)) - Each cell is processed once, and heap operations take log time
Space Complexity: O(mn) - For storing visited cells and the heap

Learning Progress: