286. Walls and Gates

📝 Problem Details

• Title: 286. Walls and Gates
• Link: https://leetcode.com/problems/walls-and-gates/
• Difficulty: Medium
• Tags/Categories: BFS Matrix

input matrix rooms of size n x m elements in the matrix can have three possible values -1 ⇒ a wall or an obstacle 0 ⇒ a gate INF ⇒ infinity which represents and empty room - 2^31 -1 represents INF

fill each empty room with the distance to the nearest gate if its impossible to reach a gate, have it filled with INF

💭What Were My Initial Thoughts?

- originally thought a DFS approach would work
- we need to find the **shortest path** from a given grid position to a gate
- suggests a BFS is the better approach
- BFS should guarantee the shortest distance in a single pass because it expands level by level

💡 Explanation of Solution

1. first pass through, finding all gates (0) and enqueue them 
2. perform BFS:
	1. process each gate first
	2. expand in all 4 directions (up,down,left,right)
	3. if an empty room (INF) is found, update its distance and enqueue it

⌛ Complexity Analysis

Time Complexity: O(m*n)
Space Complexity: O(m*n) worst case queue size

💻 Implementation of Solution

class Solution {
public:
    void wallsAndGates(vector<vector<int>>& rooms) {
        // base case: if the input array is empty
        if(rooms.empty()) return;
 
        // init traversal variables
        int rows = rooms.size();
        int cols = rooms[0].size();
 
        // init bfs queue
        queue<pair<int,int>> q;
 
        // first pass through: push each gate location into q
        for(int r = 0; r < rows; r++) {
            for(int c = 0; c < cols; c++) {
                if(rooms[r][c] == 0)
                    q.push({r,c});
            }
        }
 
        // possible directions
        vector<pair<int,int>> directions = {
            {1,0}, // up
            {-1,0},// down
            {0,1}, // left
            {0,-1} // right
        };
 
        // second pass through: bfs from each gate position
        while(!q.empty()) {
            auto [row, col] = q.front();
            q.pop();
 
            // for each possible direction we can take
            for(auto [dr, dc] : directions) {
                int newRow = row + dr;
                int newCol = col + dc;
 
                if(newRow < 0 || newRow >= rows  // if out of bounds
                || newCol < 0 || newCol >= cols
                || rooms[newRow][newCol] != INT_MAX) { // or not an empty room
                    continue;   // skip
                }
 
                // update distance (from the original gate)
                // this will also create a progressively growing distance for adjacent elements that we process next 
                rooms[newRow][newCol] = rooms[row][col] + 1;
 
                // push new position into queue
                q.push({newRow, newCol});
            }
        }
    }
};