⭕✅Multi Source BFS🗝️||⭕✅2-Pass DP🗝️2 CODE SOLUTIONS⚡[C++/Java/Py3/JS] (BEATS 💯) w EXPLANATION🍨
Approach 1: Multi-Source BFSIntuition:This approach uses BFS to treat all water cells as sources and spreads out layer by layer. Starting from the water cells,
# **Approach 1: Multi-Source BFS**

# **Intuition**:  
This approach uses BFS to treat all water cells as sources and spreads out layer by layer. Starting from the water cells, the distance to the nearest water cell for each land cell is calculated. BFS guarantees that the shortest distance is computed for all cells, as it explores nodes level by level.

---
![Screenshot 2025-01-23 151858.png](https://assets.leetcode.com/users/images/4d82241c-731f-4070-9e81-c5a0f3bce5e2_1737625758.0943615.png)




# **Approach**:
1. Initialize a `queue` to store the coordinates of all water cells.
2. Traverse the grid:
    - If the cell is water (`1`), add its coordinates to the `queue` and set its value to `0`.
    - If the cell is land, set its value to `-1` (unvisited).
3. While the `queue` is not empty:
    - Create an empty list `temp` to hold the next layer of cells to process.
    - For each cell `[r, c]` in the `queue`:
        - Explore its neighbors (top, bottom, left, right).
        - For each neighbor:
            - If it is unvisited land (`-1`), update its value to `grid[r][c] + 1`.
            - Add the neighbor to `temp`.
    - Replace `queue` with `temp` (process the next layer).
4. Return the modified grid.

---

# **Complexity**:
- **Time Complexity**:  
  - Initial traversal to populate the `queue`: **O(m × n)**, where `m` and `n` are the grid dimensions.  
  - BFS processes each cell exactly once: **O(m × n)**.  
  - Total: **O(m × n)**.

- **Space Complexity**:  
  - Space for the queue, which in the worst case contains all land cells: **O(m × n)**.  
  - Total: **O(m × n)**.

---


# Pseudo explanation for the Approach

1. Start by identifying all water cells (`0`) in the grid. These are treated as initial points for distance calculation.
2. Use a queue to perform the BFS. Each water cell is added to the queue with an initial distance of `0`.
3. While processing the queue, dequeue a cell and check its neighbors in four directions: up, down, left, and right.
4. If a neighboring cell is land (`1`) and has not been visited yet:
   - Calculate the distance for this cell as `current cell distance + 1`.
   - Mark the cell as visited to avoid redundant processing.
   - Add this cell to the queue for further exploration.
5. Continue processing until the queue is empty, ensuring all land cells are updated with the shortest distance to the nearest water cell.
6. The process ensures that distances are calculated incrementally and layer by layer.

---


# **Code**:

```cpp []
class Solution {
public:
    vector<vector<int>> highestPeak(vector<vector<int>>& g) {
        int rows = g.size();
        int cols = g[0].size();
        int inf = rows+cols;

        for(int r=0;r<rows;r++) {
            for(int c=0;c<cols;c++) {
                if(g[r][c] == 1) g[r][c] = 0;
                else g[r][c] = 1;
            }
        }

        for(int r=0;r<rows;r++) {
            for(int c=0;c<cols;c++) {
                if(g[r][c] == 0)continue;
                int left = inf, top = inf;
                if(c-1 >=0) left = g[r][c-1];
                if(r-1 >=0) top = g[r-1][c];
                g[r][c] = min(left,top)+1;
            }
        }
        for(int r = rows-1; r>=0; r--) {
            for(int c= cols-1; c>=0; c--) {
                if(g[r][c] == 0)continue;
                int right = inf, bottom = inf;
                if(r+1 < rows) bottom = g[r+1][c];
                if(c+1 < cols) right = g[r][c+1];
                g[r][c] = min(g[r][c], min(right,bottom)+1);
            }
        }
        return g;
    }
};
```
```python []
class Solution:
    def highestPeak(self, g: List[List[int]]) -> List[List[int]]:
        rows, cols = len(g), len(g[0])
        inf = rows + cols

        # Step 1: Mark water cells as 0, and land cells as 1
        for r in range(rows):
            for c in range(cols):
                if g[r][c] == 1:
                    g[r][c] = 0
                else:
                    g[r][c] = 1

        # Step 2: Top-left to bottom-right pass
        for r in range(rows):
            for c in range(cols):
                if g[r][c] != 0:
                    top = inf
                    left = inf
                    if r - 1 >= 0:
                        top = g[r - 1][c]
                    if c - 1 >= 0:
                        left = g[r][c - 1]
                    g[r][c] = min(top, left) + 1

        # Step 3: Bottom-right to top-left pass
        for r in range(rows - 1, -1, -1):
            for c in range(cols - 1, -1, -1):
                if g[r][c] != 0:
                    bottom = inf
                    right = inf
                    if r + 1 < rows:
                        bottom = g[r + 1][c]
                    if c + 1 < cols:
                        right = g[r][c + 1]
                    g[r][c] = min(g[r][c], min(bottom, right) + 1)

        return g
```
```java []
class Solution {
    public int[][] highestPeak(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int maxVal = 2000;
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (matrix[r][c] == 1) matrix[r][c] = 0;
                else matrix[r][c] = 1;
            }
        }
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (matrix[r][c] != 0) {
                    int top = maxVal;
                    int left = maxVal;
                    if (r - 1 >= 0) top = matrix[r - 1][c];
                    if (c - 1 >= 0) left = matrix[r][c - 1];
                    matrix[r][c] = Math.min(top, left) + 1;
                }
            }
        }
        for (int r = m - 1; r >= 0; r--) {
            for (int c = n - 1; c >= 0; c--) {
                if (matrix[r][c] != 0) {
                    int bottom = maxVal;
                    int right = maxVal;
                    if (r + 1 < m) bottom = matrix[r + 1][c];
                    if (c + 1 < n) right = matrix[r][c + 1];
                    matrix[r][c] = Math.min(matrix[r][c], Math.min(bottom, right) + 1);
                }
            }
        }
        return matrix;
    }
}
```
```javascript []
/**
 * @param {number[][]} isWater
 * @return {number[][]}
 */
var highestPeak = function (g) {
    const rows = g.length;
    const cols = g[0].length;
    const inf = rows + cols;

    // Step 1: Mark water cells as 0, and land cells as 1
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (g[r][c] === 1) {
                g[r][c] = 0;
            } else {
                g[r][c] = 1;
            }
        }
    }

    // Step 2: Top-left to bottom-right pass
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (g[r][c] !== 0) {
                let top = inf;
                let left = inf;
                if (r - 1 >= 0) top = g[r - 1][c];
                if (c - 1 >= 0) left = g[r][c - 1];
                g[r][c] = Math.min(top, left) + 1;
            }
        }
    }

    // Step 3: Bottom-right to top-left pass
    for (let r = rows - 1; r >= 0; r--) {
        for (let c = cols - 1; c >= 0; c--) {
            if (g[r][c] !== 0) {
                let bottom = inf;
                let right = inf;
                if (r + 1 < rows) bottom = g[r + 1][c];
                if (c + 1 < cols) right = g[r][c + 1];
                g[r][c] = Math.min(g[r][c], Math.min(bottom, right) + 1);
            }
        }
    }

    return g;
};
```


---

# **Approach 2: Two-Pass DP**

# **Intuition**:  
This approach calculates the shortest distance from each land cell to the nearest water cell using two sweeps through the grid. By performing a top-left-to-bottom-right pass followed by a bottom-right-to-top-left pass, we ensure that the minimum distance to a water cell is propagated in all four directions.

---
![Screenshot 2025-01-23 151858.png](https://assets.leetcode.com/users/images/b85f6af3-d143-4beb-9f0b-9257f0ef4677_1737625793.380863.png)



# **Approach**:
1. Initialize the grid:
    - If a cell is water (`1`), set its value to `0` (distance is `0`).
    - If a cell is land (`0`), set its value to a large constant (`Infinity`) to indicate it is unprocessed.
    
2. Perform the **first pass** (top-left to bottom-right):
    - Iterate through the grid.
    - For each land cell, calculate its height as `1 + min(top, left)`:
        - `top`: The height of the cell directly above (if it exists).
        - `left`: The height of the cell directly to the left (if it exists).

3. Perform the **second pass** (bottom-right to top-left):
    - Iterate through the grid in reverse.
    - For each land cell, update its height as `min(current height, 1 + min(bottom, right))`:
        - `bottom`: The height of the cell directly below (if it exists).
        - `right`: The height of the cell directly to the right (if it exists).

4. Return the modified grid, where each land cell contains the shortest distance to a water cell.

---

# **Complexity**:
- **Time Complexity**:  
  - Each pass iterates over all cells in the grid once: **O(m × n)**.  
  - Total: **O(m × n)**.

- **Space Complexity**:  
  - The grid is updated in-place, requiring no additional space beyond the input grid: **O(1)**.  
  - Total: **O(1)**.

---
# Pseudo explanation for Two-Pass DP Approach

1. Perform the first pass by iterating from the top-left corner to the bottom-right corner of the grid.
2. For each cell:
   - If the cell is water (`0`), its distance remains `0`.
   - If the cell is land (`1`), compute its distance based on the top and left neighbors, if they exist.
   - Assign the distance as `1 + min(top neighbor distance, left neighbor distance)`.
3. After completing the first pass, start the second pass from the bottom-right corner to the top-left corner.
4. For each cell:
   - If the cell is land (`1`), refine its previously calculated distance by considering the distances of the bottom and right neighbors.
   - Update the distance as `min(current distance, 1 + min(bottom neighbor distance, right neighbor distance))`.
5. The combination of these two passes ensures that every land cell’s distance is calculated based on all possible water sources.
6. The grid now contains the shortest distance from each land cell to its nearest water cell.
---

This approach is efficient, concise, and avoids the overhead of managing a BFS queue while achieving the same result.



# **Code**:

```cpp []
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
        vector<pair<int, int>> array;

        // Initialize the array and set up the grid
        for (int row = 0; row < isWater.size(); row++) {
            for (int column = 0; column < isWater[0].size(); column++) {
                if (isWater[row][column] == 1) {
                    array.push_back({row, column});
                    isWater[row][column] = 0;
                } else {
                    isWater[row][column] = -1;
                }
            }
        }

        // Perform BFS
        while (!array.empty()) {
            vector<pair<int, int>> temp;
            for (auto [row, column] : array) {
                if (row - 1 >= 0 && isWater[row - 1][column] == -1) {
                    isWater[row - 1][column] = isWater[row][column] + 1;
                    temp.push_back({row - 1, column});
                }
                if (column + 1 < isWater[0].size() && isWater[row][column + 1] == -1) {
                    isWater[row][column + 1] = isWater[row][column] + 1;
                    temp.push_back({row, column + 1});
                }
                if (row + 1 < isWater.size() && isWater[row + 1][column] == -1) {
                    isWater[row + 1][column] = isWater[row][column] + 1;
                    temp.push_back({row + 1, column});
                }
                if (column - 1 >= 0 && isWater[row][column - 1] == -1) {
                    isWater[row][column - 1] = isWater[row][column] + 1;
                    temp.push_back({row, column - 1});
                }
            }
            array = temp;
        }

        return isWater;
    }
};
```
```python3 []
class Solution:
    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:
        array = []
        
        # Initialize the array and set up the grid
        for row in range(len(isWater)):
            for column in range(len(isWater[0])):
                if isWater[row][column] == 1:
                    array.append((row, column))
                    isWater[row][column] = 0
                else:
                    isWater[row][column] = -1
        
        # Perform BFS
        while array:
            temp = []
            for row, column in array:
                if row - 1 >= 0 and isWater[row - 1][column] == -1:
                    isWater[row - 1][column] = isWater[row][column] + 1
                    temp.append((row - 1, column))
                if column + 1 < len(isWater[0]) and isWater[row][column + 1] == -1:
                    isWater[row][column + 1] = isWater[row][column] + 1
                    temp.append((row, column + 1))
                if row + 1 < len(isWater) and isWater[row + 1][column] == -1:
                    isWater[row + 1][column] = isWater[row][column] + 1
                    temp.append((row + 1, column))
                if column - 1 >= 0 and isWater[row][column - 1] == -1:
                    isWater[row][column - 1] = isWater[row][column] + 1
                    temp.append((row, column - 1))
            array = temp
        
        return isWater
```
```java []
import java.util.*;

class Solution {
    public int[][] highestPeak(int[][] isWater) {
        List<int[]> array = new ArrayList<>();

        // Initialize the array and set up the grid
        for (int row = 0; row < isWater.length; row++) {
            for (int column = 0; column < isWater[0].length; column++) {
                if (isWater[row][column] == 1) {
                    array.add(new int[]{row, column});
                    isWater[row][column] = 0;
                } else {
                    isWater[row][column] = -1;
                }
            }
        }

        // Perform BFS
        while (!array.isEmpty()) {
            List<int[]> temp = new ArrayList<>();
            for (int[] cell : array) {
                int row = cell[0], column = cell[1];

                if (row - 1 >= 0 && isWater[row - 1][column] == -1) {
                    isWater[row - 1][column] = isWater[row][column] + 1;
                    temp.add(new int[]{row - 1, column});
                }
                if (column + 1 < isWater[0].length && isWater[row][column + 1] == -1) {
                    isWater[row][column + 1] = isWater[row][column] + 1;
                    temp.add(new int[]{row, column + 1});
                }
                if (row + 1 < isWater.length && isWater[row + 1][column] == -1) {
                    isWater[row + 1][column] = isWater[row][column] + 1;
                    temp.add(new int[]{row + 1, column});
                }
                if (column - 1 >= 0 && isWater[row][column - 1] == -1) {
                    isWater[row][column - 1] = isWater[row][column] + 1;
                    temp.add(new int[]{row, column - 1});
                }
            }
            array = temp;
        }

        return isWater;
    }
}
```
```javascript []
/**
 * @param {number[][]} isWater
 * @return {number[][]}
 */
var highestPeak = function (isWater) {
    let array = [];
    for (let row = 0; row < isWater.length; row++) {
        for (let column = 0; column < isWater[0].length; column++) {
            if (isWater[row][column] === 1) {
                array.push([row, column]);
                isWater[row][column] = 0;
            } else {
                isWater[row][column] = -1;
            }
        }
    }
    while (array.length !== 0) {
        let temp = [];
        for (let i = 0; i < array.length; i++) {
            let [row, column] = array[i];

            if (row - 1 >= 0 && isWater[row - 1][column] === -1) {
                isWater[row - 1][column] = isWater[row][column] + 1;
                temp.push([row - 1, column]);
            }
            if (column + 1 < isWater[0].length && isWater[row][column + 1] === -1) {
                isWater[row][column + 1] = isWater[row][column] + 1;
                temp.push([row, column + 1]);
            }
            if (row + 1 < isWater.length && isWater[row + 1][column] === -1) {
                isWater[row + 1][column] = isWater[row][column] + 1;
                temp.push([row + 1, column]);
            }
            if (column - 1 >= 0 && isWater[row][column - 1] === -1) {
                isWater[row][column - 1] = isWater[row][column] + 1;
                temp.push([row, column - 1]);
            }
        }
        array = temp;
    }
    return isWater;
};
```









```
✨ AN UPVOTE WILL BE APPRECIATED ^_~ ✨
```
['Dynamic Programming', 'Breadth-First Search', 'Python', 'C++', 'Java', 'Python3', 'JavaScript']