Walls and Gates - LC Premium

Problem Statement

You are given an m x n grid rooms initialized with these three possible values.

• -1 A wall or an obstacle.
• 0 A gate.
• INF Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

Example 1

Input: rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]
Output: [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]

Example 2

Input: rooms = [[-1]]
Output: [[-1]]

Try here before watching the video.

Video Explanation

Java Code

import java.util.*;

class Node {
    int row, col, distance;
    public Node(int row, int col, int distance) {
        this.row = row;
        this.col = col;
        this.distance = distance;
    }
}

class Solution {

    private boolean isValid(int row, int col, int rows, int cols) {
        return (row < rows && row >= 0 && col < cols && col >= 0);
    }
    
    public void wallsAndGates(int[][] rooms) {
        int[][] directions = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        int rows = rooms.length;
        int cols = rooms[0].length;

        Queue<Node> queue = new LinkedList<>();

        for(int i = 0; i < rows; i++) {
            for(int j = 0; j < cols; j++) {
                if(rooms[i][j] == 0) {
                    queue.add(new Node(i, j, 0));
                }
            }
        }

        while(!queue.isEmpty()) {
            Node currNode = queue.poll();
            for(int[] direction : directions) {
                int newRow = currNode.row + direction[0];
                int newCol = currNode.col + direction[1];
                if(isValid(newRow, newCol, rows, cols) && rooms[newRow][newCol] == Integer.MAX_VALUE) {
                    rooms[newRow][newCol] = currNode.distance + 1;
                    queue.add(new Node(newRow, newCol, currNode.distance + 1));
                }
            }
        }
    }
}

C++ Code

#include <bits/stdc++.h>
using namespace std;

class Node {
public:
    int row, col, distance;
    Node(int row, int col, int distance) {
        this->row = row;
        this->col = col;
        this->distance = distance;
    }
};

class Solution {
public:
    void wallsAndGates(vector<vector<int>>& rooms) {
        int directions[][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        int rows = rooms.size();
        int cols = rooms[0].size();

        queue<Node> q;

        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (rooms[i][j] == 0) {
                    q.push(Node(i, j, 0));
                }
            }
        }

        while (!q.empty()) {
            Node currNode = q.front();
            q.pop();

            for (auto& direction : directions) {
                int newRow = currNode.row + direction[0];
                int newCol = currNode.col + direction[1];

                if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols &&
                    rooms[newRow][newCol] == INT_MAX) {
                    rooms[newRow][newCol] = currNode.distance + 1;
                    q.push(Node(newRow, newCol, currNode.distance + 1));
                }
            }
        }
    }
};

Python Code

from typing import List
from collections import deque

class Node:
    def __init__(self, row, col, distance):
        self.row = row
        self.col = col
        self.distance = distance

class Solution:
    def wallsAndGates(self, rooms: List[List[int]]) -> None:
        MAX = 2147483647
        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        rows = len(rooms)
        cols = len(rooms[0])

        queue = deque()

        for i in range(rows):
            for j in range(cols):
                if rooms[i][j] == 0:
                    queue.append(Node(i, j, 0))

        while queue:
            curr_node = queue.popleft()

            for direction in directions:
                new_row = curr_node.row + direction[0]
                new_col = curr_node.col + direction[1]
                
                if 0 <= new_row < rows and 0 <= new_col < cols and rooms[new_row][new_col] == MAX:
                    rooms[new_row][new_col] = curr_node.distance + 1
                    queue.append(Node(new_row, new_col, curr_node.distance + 1))

Javascript Code

var wallsAndGates = function(rooms) {
    const directions = [[-1, 0], [0, 1], [1, 0], [0, -1]];
    const isValid = (row, col, rows, cols) => row < rows && row >= 0 && col < cols && col >= 0;

    const queue = [];

    for (let i = 0; i < rooms.length; i++) {
        for (let j = 0; j < rooms[0].length; j++) {
            if (rooms[i][j] === 0) {
                queue.push([i, j, 0]);
            }
        }
    }

    while (queue.length > 0) {
        const [currRow, currCol, distance] = queue.shift();

        for (const [rowDir, colDir] of directions) {
            const newRow = currRow + rowDir;
            const newCol = currCol + colDir;
            if (isValid(newRow, newCol, rooms.length, rooms[0].length) && rooms[newRow][newCol] === 2147483647) {
                rooms[newRow][newCol] = distance + 1;
                queue.push([newRow, newCol, distance + 1]);
            }
        }
    }
};

Go Code

func wallsAndGates(rooms [][]int) {
	directions := [][]int{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}

	isValid := func(row, col, rows, cols int) bool {
		return row < rows && row >= 0 && col < cols && col >= 0
	}

	queue := make([][]int, 0)

	for i := 0; i < len(rooms); i++ {
		for j := 0; j < len(rooms[0]); j++ {
			if rooms[i][j] == 0 {
				queue = append(queue, []int{i, j, 0})
			}
		}
	}

	for len(queue) > 0 {
		currRow, currCol, distance := queue[0][0], queue[0][1], queue[0][2]
		queue = queue[1:]

		for _, dir := range directions {
			newRow, newCol := currRow + dir[0], currCol + dir[1]
			if isValid(newRow, newCol, len(rooms), len(rooms[0])) && rooms[newRow][newCol] == int(2147483647) {
				rooms[newRow][newCol] = distance + 1
				queue = append(queue, []int{newRow, newCol, distance + 1})
			}
		}
	}
}

Complexity Analysis

Time Complexity: O(m × n). The breadth-first search takes at most m × n steps to reach all rooms, therefore the time complexity is O(m × n).
Space Complexity: O(m × n). The space complexity depends on the queue's size. We insert at most m × n points into the queue.