Solving Walls and Gates in Go: Step-by-Step Guide

Introduction to Walls and Gates

The Walls and Gates problem is a classic graph traversal challenge frequently encountered in coding interviews and algorithmic problem-solving. You are given a 2D grid representing a building's floor plan, where each cell can be a gate, a wall, or an empty room. Your task is to fill every empty room with the distance to its nearest gate. If a room cannot reach any gate, it should remain at its initial value (typically represented as infinity).

In this tutorial, you will learn how to solve this problem efficiently in Go using Breadth-First Search (BFS). We will walk through the problem statement, the reasoning behind the chosen algorithm, a complete implementation, and best practices to keep your code clean and performant.

Problem Statement

Given an m x n grid filled with three possible values:

• -1 — A wall or obstacle that you cannot pass through.
• 0 — A gate.
• INF (represented as 2^31 - 1 or a large number) — An empty room.

You must modify the grid in place so that every empty room contains the distance to its nearest gate. If no gate is reachable, the room keeps its INF value. Distance is measured as the number of steps required to move from the room to the gate, moving only up, down, left, or right.

Why This Problem Matters

The Walls and Gates problem is more than an interview exercise. It models real-world scenarios such as:

• Indoor navigation — computing shortest paths from any point to exits in a building.
• Game development — calculating influence maps or distance fields for AI movement.
• Robotics — path planning where multiple goal locations exist.
• Network routing — finding the closest service node from any point in a topology.

The key insight is that you have multiple sources (the gates) and you need the shortest distance from each cell to any one of them. This is a textbook case for a multi-source BFS, which is significantly more efficient than running BFS from every empty room.

Choosing the Right Algorithm

Why Not DFS or Dijkstra?

A naive approach would be to iterate over every empty room and run BFS or DFS to find the nearest gate. This results in O((m * n)^2) time complexity, which is wasteful because you recompute overlapping paths repeatedly.

Dijkstra's algorithm is overkill here because all moves have uniform cost (each step costs 1). BFS naturally handles unweighted shortest-path problems in O(m * n) time.

Multi-Source BFS

The optimal strategy is to start BFS from all gates simultaneously. By enqueuing every gate at the start with distance 0, the BFS wavefront expands outward uniformly. The first time a room is reached, it is guaranteed to be via the shortest path from its nearest gate. This gives us O(m * n) time and O(m * n) space complexity in the worst case.

Step-by-Step Implementation in Go

Let's build the solution incrementally. First, we define the constants and helper structures, then implement the BFS, and finally wire everything together with a test.

Step 1: Define Constants and the Grid Type

package main

import (
	"fmt"
	"math"
)

const (
	Empty = math.MaxInt32
	Wall  = -1
	Gate  = 0
)

// Direction vectors for up, down, left, right
var directions = [4][2]int{
	{-1, 0}, // up
	{1, 0},  // down
	{0, -1}, // left
	{0, 1},  // right
}

type Grid [][]int

Using named constants instead of magic numbers makes the code self-documenting and reduces the chance of bugs. The directions array lets us iterate over neighbors cleanly without writing four separate conditionals.

Step 2: Implement Multi-Source BFS

type Cell struct {
	row, col, dist int
}

func WallsAndGates(grid Grid) {
	if len(grid) == 0 {
		return
	}

	rows := len(grid)
	cols := len(grid[0])

	// Initialize the queue with all gates
	queue := make([]Cell, 0)
	for r := 0; r < rows; r++ {
		for c := 0; c < cols; c++ {
			if grid[r][c] == Gate {
				queue = append(queue, Cell{r, c, 0})
			}
		}
	}

	// BFS expansion
	for len(queue) > 0 {
		current := queue[0]
		queue = queue[1:]

		for _, dir := range directions {
			nr := current.row + dir[0]
			nc := current.col + dir[1]

			// Skip out-of-bounds cells
			if nr < 0 || nr >= rows || nc < 0 || nc >= cols {
				continue
			}

			// Only update empty rooms that haven't been visited yet
			if grid[nr][nc] == Empty {
				grid[nr][nc] = current.dist + 1
				queue = append(queue, Cell{nr, nc, current.dist + 1})
			}
		}
	}
}

Notice that we only enqueue cells that are still marked as Empty. This ensures each cell is processed exactly once, which is what gives us linear time complexity. Walls and already-visited rooms are skipped, and gates are never re-enqueued because they are not Empty.

Step 3: Add a Helper to Print the Grid

func (g Grid) Print() {
	for _, row := range g {
		for _, val := range row {
			if val == Empty {
				fmt.Printf("INF ")
			} else {
				fmt.Printf("%3d ", val)
			}
		}
		fmt.Println()
	}
	fmt.Println()
}

This helper makes it easier to visualize the results during development and debugging.

Step 4: Write a Complete Example

func main() {
	grid := Grid{
		{Empty, Wall,  Gate,  Empty},
		{Empty, Empty, Empty, Wall},
		{Empty, Wall,  Empty, Wall},
		{Gate,  Wall,  Empty, Empty},
	}

	fmt.Println("Before:")
	grid.Print()

	WallsAndGates(grid)

	fmt.Println("After:")
	grid.Print()
}

When you run this program, the output will show each empty room replaced with its distance to the nearest gate:

Before:
INF  -1   0  INF
INF INF INF  -1
INF  -1 INF  -1
  0  -1 INF INF

After:
  3  -1   0   1
  2   2   1  -1
  1  -1   2  -1
  0  -1   3   4

Optimizing the Queue

The implementation above uses a Go slice as a queue with queue = queue[1:]. While simple, this approach never shrinks the underlying array, which can lead to unnecessary memory usage on large grids. For production code, consider using a ring buffer or a more efficient queue implementation.

A Ring Buffer Queue

type Queue struct {
	data []Cell
	head int
}

func NewQueue(capacity int) *Queue {
	return &Queue{data: make([]Cell, 0, capacity)}
}

func (q *Queue) Enqueue(c Cell) {
	q.data = append(q.data, c)
}

func (q *Queue) Dequeue() Cell {
	c := q.data[q.head]
	q.head++
	// Reset when fully drained to reclaim memory
	if q.head > 0 && q.head == len(q.data) {
		q.data = q.data[:0]
		q.head = 0
	}
	return c
}

func (q *Queue) Len() int {
	return len(q.data) - q.head
}

You can then replace the slice-based queue in WallsAndGates with this structure. The amortized cost of enqueue and dequeue remains O(1), but memory is reclaimed once the queue drains, which matters when processing very large grids.

Best Practices

Validate Input Early

Always check for empty grids or nil inputs at the top of your function. This prevents panics and makes the function's contract explicit:

func WallsAndGates(grid Grid) {
	if len(grid) == 0 || grid == nil {
		return
	}
	// ... rest of the function
}

Avoid Magic Numbers

Use named constants like Empty, Wall, and Gate instead of raw integers. This improves readability and makes future changes safer — if the representation of infinity changes, you only update one constant.

Prefer In-Place Modification

The problem explicitly asks for in-place modification. Even if it did not, modifying the grid in place avoids allocating a second m x n matrix, which keeps memory usage at O(m * n) for the queue rather than doubling it.

Use Direction Arrays

Defining a directions array keeps neighbor iteration concise and less error-prone than writing four separate if blocks. It also makes it trivial to add diagonal movement later if the problem evolves.

Write Table-Driven Tests

Go's testing package shines with table-driven tests. Cover edge cases such as a grid with no gates, a grid with only walls, a single-cell grid, and a grid where some rooms are unreachable:

func TestWallsAndGates(t *testing.T) {
	tests := []struct {
		name     string
		input    Grid
		expected Grid
	}{
		{
			name:     "empty grid",
			input:    Grid{},
			expected: Grid{},
		},
		{
			name: "no gates",
			input: Grid{
				{Empty, Wall},
				{Wall, Empty},
			},
			expected: Grid{
				{Empty, Wall},
				{Wall, Empty},
			},
		},
		{
			name: "single gate",
			input: Grid{
				{Empty, Empty},
				{Empty, Gate},
			},
			expected: Grid{
				{2, 1},
				{1, 0},
			},
		},
	}

	for _, tt := range tests {
		t.Run(tt.name, func(t *testing.T) {
			WallsAndGates(tt.input)
			if !gridsEqual(tt.input, tt.expected) {
				t.Errorf("got %v, want %v", tt.input, tt.expected)
			}
		})
	}
}

func gridsEqual(a, b Grid) bool {
	if len(a) != len(b) {
		return false
	}
	for i := range a {
		if len(a[i]) != len(b[i]) {
			return false
		}
		for j := range a[i] {
			if a[i][j] != b[i][j] {
				return false
			}
		}
	}
	return true
}

Complexity Analysis

• Time complexity: O(m * n) — each cell is enqueued and dequeued at most once.
• Space complexity: O(m * n) — in the worst case, the queue holds every cell in the grid (for example, when the entire grid is gates).

This is asymptotically optimal because you must inspect every cell at least once to determine whether it is a gate, wall, or room.

Common Pitfalls

• Enqueuing visited cells — if you enqueue a cell every time you encounter it rather than only when it is Empty, you will process cells multiple times and degrade performance.
• Forgetting boundary checks — always validate that neighbor coordinates are within bounds before accessing the grid.
• Using DFS for shortest paths — DFS does not guarantee shortest paths in unweighted graphs and requires additional bookkeeping to avoid revisiting cells with longer paths.
• Mutating gates — gates should remain 0. Because we only update cells equal to Empty, gates are naturally preserved.

Conclusion

The Walls and Gates problem is an elegant demonstration of how reframing a question can dramatically improve efficiency. By flipping the perspective from "find the nearest gate for each room" to "expand outward from all gates simultaneously," a multi-source BFS reduces the time complexity from quadratic to linear. In Go, the implementation is straightforward thanks to slices, structs, and clean iteration patterns. By following the best practices outlined here — validating input, avoiding magic numbers, using direction arrays, and writing table-driven tests — you will produce a solution that is not only correct and fast but also maintainable and easy to extend to related problems such as rotting oranges, shortest path in binary matrices, or multi-agent pathfinding.