Priority Queue solution (with explanation) - 100% Faster - Rust
Explanation\nI will use this input as an example\n\nInput:\n[\n\t[12, 13, 01, 12],\n\t[13, 04, 12, 12],\n\t[13, 08, 10, 12],\n\t[12, 13, 12, 12],\n\t[13, 13, 13
## Explanation\nI will use this input as an example\n```\nInput:\n[\n\t[12, 13, 01, 12],\n\t[13, 04, 12, 12],\n\t[13, 08, 10, 12],\n\t[12, 13, 12, 12],\n\t[13, 13, 13, 13]\n]\n\nOutput: 14\n```\nThe idea is using Priority Queue (implemented with Min Heap) to polling out the node with minimum value. Then applying BFS algorithm to traverse through neighbor nodes. These illustration below is well-explained:\n\n### Step 1: Understand states and initialize visited matrix\nTo avoid traversing visited node twice, we must have a visited matrix (O(MN) => Space complexity). The reason why in the image below, I mark all boundary node as visited and in priority queue because rain water can\'t be contain in those nodes. Rain water must be contained by a container (formed by boundary nodes). In that way, we will add all boundary nodes to priority queue.\n![image](https://assets.leetcode.com/users/images/e4dbc89e-ceba-4b5e-b244-50db8a423183_1656921318.9581015.png)\n### Step 2: Polling node with minimum value\nA node with minimum value is like a hole of the container. Therefore, rain water can only contain up to the height of the hole. So we must get the node with minimum value aka a hole. That is the reason why Min heap is applied into priority queue implementation to solve this problem.\n![image](https://assets.leetcode.com/users/images/5bf29368-416a-44a9-b4a1-cc9c8578f9ae_1656921558.3742485.png)\n### Step 3: Get and validate neighbor node of polled node\n#### Case 1: Invalid neighbor node (is a boundary node and is visited already)\nTo check if the current node is suitable for containing water, we must check its neighbors, if these neighbors are higher than the current node then it is suitable to contain water. However, if the current node is the boundary, it can no longer a boundary node and we should update the neighbor which has a value higher than the current node as a boundary node.\n![image](https://assets.leetcode.com/users/images/3023eb0b-6ad2-4351-afcb-0d0f9940ac05_1656921934.1067417.png)\n#### Case 2: Valid neighbor node and is an inbound node\nKeep traversing the matrix and we will get another case when the neighbor node is valid and it is an inbound node (heigh is smaller than the current node). Facing the case, we will then update the boundary via updaing the neighbor node\'s height as the boundary. And because this neighbor node meets all requirement, ANSWER will be updated with a simple operation\n```\nANSWER += current_node.height - neighbor_node.height\n```\n![image](https://assets.leetcode.com/users/images/4df04ce9-3ac3-4495-a44d-5a42e5b54c25_1656922208.7913456.png)\n\nKeep repeating the whole steps until there is no node to visit. Here is a full image to illustrate all steps of the above input/output.\n![image](https://assets.leetcode.com/users/images/b673162b-ed61-46d5-a9b9-1b748902d94e_1656922291.039001.png)\n\n## Implementation\nTo implement Min Heap in Rust, you can use Binary Heap from the standard collection package combines with std::cmp::Reverse. See the documentation for an example: https://doc.rust-lang.org/stable/std/collections/struct.BinaryHeap.html#min-heap\n\nNote: The solution uses Priority Queue (implemented with Min Heap). This is similar to BFS, however, to solve the problme, we must apply Min Heap into the solution to select a correct next node to operate.\n\n```\nuse std::cmp::Reverse;\nuse std::collections::binary_heap::BinaryHeap;\n\npub struct Solution;\n\nimpl Solution {\n /// ## Trapping Rain Water II\n /// - **Time complexity**: O(m*n*long(m*n)) | Each cell will be pushed into and popped out of the queue only once,\n /// which will cost O(log(queue_size)). (*Time complexity of Min heap operation*)\n /// Iterate the 2D matrix will cost M*N time complexity (M: rows, N: columns)\n ///\n /// - **Space complexity**: O(m*n) | Because priority queue will store all the node of the matrix\n ///\n /// Note: Using Min Heap (std::cmp::Reverse + std::collections::binary_heap::BinaryHeap)\n pub fn trap_rain_water(height_map: Vec<Vec<i32>>) -> i32 {\n  let mut ans = 0;\n  let dirs: Vec<(i32, i32)> = vec![(0, 1), (0, -1), (1, 0), (-1, 0)];\n  let (r, c) = (height_map.len(), height_map[0].len());\n  let mut visited: Vec<Vec<bool>> = vec![vec![false; c]; r];\n\n  // The element in the PriorityQueue is an array with three elements encoding\n  // the row number, column number and the height of the cell on the boundary.\n  let mut pq = BinaryHeap::new();\n\n  // We first build the initial boundary by enqueuing all cells\n  // on the outer edges of the input matrix and mark them as visited\n  for r in 0..height_map.len() {\n   for c in 0..height_map[r].len() {\n    if r > 0 && r < height_map.len() - 1 && c > 0 && c < height_map[r].len() - 1 {\n     continue;\n    }\n    visited[r][c] = true;\n    // Using Reverse to construct a Min Heap in Rust\n    pq.push(Reverse((height_map[r][c], r, c)));\n   }\n  }\n\n  while !pq.is_empty() {\n   // Polling the cell with minimum height\n   match pq.pop() {\n    Some(node) => {\n     let (cur_height, cur_row, cur_col) = ((node.0).0, (node.0).1, (node.0).2);\n\n     for dir in dirs.iter() {\n      let dr = (cur_row as i32 + dir.0) as usize;\n      let dc = (cur_col as i32 + dir.1) as usize;\n\n      let is_not_border = dr > 0 && dr < r - 1 && dc > 0 && dc < c - 1;\n      if is_not_border && !visited[dr][dc] {\n       // After obtaining the water contained for each of its neighbor,\n       // we replace it with its neighbor and form a new boundary.\n       // Again we continue until the container shrinks to a point.\n       ans += std::cmp::max(0, cur_height - height_map[dr][dc]);\n       visited[dr][dc] = true;\n       pq.push(Reverse((\n        std::cmp::max(cur_height, height_map[dr][dc]),\n        dr,\n        dc,\n       )));\n      }\n     }\n    }\n    None => {\n     unreachable!();\n    }\n   }\n  }\n\n  ans\n }\n}\n```
['Heap (Priority Queue)', 'Rust']