Grid-Based Graph

A comprehensive guide to grid-based graph algorithms and techniques for Data Structures and Algorithms in JavaScript.

Grid Fundamentals
Basic Grid Operations
Depth-First Search (DFS)
Breadth-First Search (BFS)
Pathfinding Algorithms
Island and Connected Components
Flood Fill Algorithms
Dynamic Programming on Grids
Advanced Grid Techniques
Multi-source and Multi-destination
Usage Examples

Grid Fundamentals

Grid-based problems are essentially graph problems where nodes are cells and edges represent valid movements between adjacent cells.

Basic Grid Setup

// Common grid directions (4-directional)
const DIRECTIONS_4 = [
    [-1, 0], // Up
    [1, 0],  // Down
    [0, -1], // Left
    [0, 1]   // Right
];

// 8-directional (including diagonals)
const DIRECTIONS_8 = [
    [-1, -1], [-1, 0], [-1, 1], // Top row
    [0, -1],           [0, 1],  // Middle row
    [1, -1],  [1, 0],  [1, 1]   // Bottom row
];

// Check if coordinates are valid
function isValid(grid, row, col) {
    return row >= 0 && row < grid.length &&
           col >= 0 && col < grid[0].length;
}

// Check if cell is valid and not blocked
function isValidCell(grid, row, col, blocked = '#') {
    return isValid(grid, row, col) && grid[row][col] !== blocked;
}

// Get all valid neighbors
function getNeighbors(grid, row, col, directions = DIRECTIONS_4) {
    const neighbors = [];

    for (const [dr, dc] of directions) {
        const newRow = row + dr;
        const newCol = col + dc;

        if (isValid(grid, newRow, newCol)) {
            neighbors.push([newRow, newCol]);
        }
    }

    return neighbors;
}

// Convert 2D coordinates to 1D (for hashing)
function coordToKey(row, col) {
    return `${row},${col}`;
}

// Convert 1D key back to coordinates
function keyToCoord(key) {
    return key.split(',').map(Number);
}

Grid Creation Utilities

// Create empty grid
function createGrid(rows, cols, defaultValue = 0) {
    return Array(rows).fill(null).map(() => Array(cols).fill(defaultValue));
}

// Create grid from string array
function parseGrid(gridString) {
    return gridString.trim().split('\n').map(row => row.split(''));
}

// Print grid for visualization
function printGrid(grid, highlight = null) {
    for (let i = 0; i < grid.length; i++) {
        let row = '';
        for (let j = 0; j < grid[i].length; j++) {
            if (highlight && highlight.has(coordToKey(i, j))) {
                row += `[${grid[i][j]}]`;
            } else {
                row += ` ${grid[i][j]} `;
            }
        }
        console.log(row);
    }
}

// Clone grid
function cloneGrid(grid) {
    return grid.map(row => [...row]);
}

Basic Grid Operations

1. Grid Traversal

// Traverse all cells
function traverseGrid(grid, callback) {
    for (let row = 0; row < grid.length; row++) {
        for (let col = 0; col < grid[0].length; col++) {
            callback(row, col, grid[row][col]);
        }
    }
}

// Find all cells with specific value
function findCells(grid, target) {
    const cells = [];
    traverseGrid(grid, (row, col, value) => {
        if (value === target) {
            cells.push([row, col]);
        }
    });
    return cells;
}

// Count cells with specific value
function countCells(grid, target) {
    let count = 0;
    traverseGrid(grid, (row, col, value) => {
        if (value === target) count++;
    });
    return count;
}

2. Boundary Checking

// Check if cell is on boundary
function isOnBoundary(grid, row, col) {
    return row === 0 || row === grid.length - 1 ||
           col === 0 || col === grid[0].length - 1;
}

// Get boundary cells
function getBoundaryCells(grid) {
    const boundary = [];
    const rows = grid.length;
    const cols = grid[0].length;

    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (isOnBoundary(grid, i, j)) {
                boundary.push([i, j]);
            }
        }
    }

    return boundary;
}

// Get corner cells
function getCornerCells(grid) {
    const rows = grid.length;
    const cols = grid[0].length;

    return [
        [0, 0],                    // Top-left
        [0, cols - 1],             // Top-right
        [rows - 1, 0],             // Bottom-left
        [rows - 1, cols - 1]       // Bottom-right
    ];
}

Depth-First Search (DFS)

DFS is perfect for exploring paths, finding connected components, and solving maze problems.

1. Basic DFS Implementation

// Recursive DFS
function dfsRecursive(grid, row, col, visited = new Set(), path = []) {
    const key = coordToKey(row, col);

    if (!isValid(grid, row, col) || visited.has(key)) {
        return;
    }

    visited.add(key);
    path.push([row, col]);

    // Process current cell
    console.log(`Visiting: ${row}, ${col}`);

    // Explore neighbors
    for (const [dr, dc] of DIRECTIONS_4) {
        const newRow = row + dr;
        const newCol = col + dc;
        dfsRecursive(grid, newRow, newCol, visited, path);
    }
}

// Iterative DFS
function dfsIterative(grid, startRow, startCol) {
    const visited = new Set();
    const stack = [[startRow, startCol]];
    const path = [];

    while (stack.length > 0) {
        const [row, col] = stack.pop();
        const key = coordToKey(row, col);

        if (!isValid(grid, row, col) || visited.has(key)) {
            continue;
        }

        visited.add(key);
        path.push([row, col]);

        // Add neighbors to stack
        for (const [dr, dc] of DIRECTIONS_4) {
            const newRow = row + dr;
            const newCol = col + dc;
            if (isValid(grid, newRow, newCol)) {
                stack.push([newRow, newCol]);
            }
        }
    }

    return path;
}

2. DFS with Conditions

// DFS only on valid cells (not blocked)
function dfsValidCells(grid, row, col, visited = new Set()) {
    const key = coordToKey(row, col);

    if (!isValidCell(grid, row, col) || visited.has(key)) {
        return [];
    }

    visited.add(key);
    const component = [[row, col]];

    for (const [dr, dc] of DIRECTIONS_4) {
        const newRow = row + dr;
        const newCol = col + dc;
        component.push(...dfsValidCells(grid, newRow, newCol, visited));
    }

    return component;
}

// DFS with path tracking
function dfsWithPath(grid, row, col, target, path = [], visited = new Set()) {
    const key = coordToKey(row, col);

    if (!isValid(grid, row, col) || visited.has(key)) {
        return null;
    }

    path.push([row, col]);
    visited.add(key);

    if (grid[row][col] === target) {
        return [...path]; // Found target, return path
    }

    for (const [dr, dc] of DIRECTIONS_4) {
        const newRow = row + dr;
        const newCol = col + dc;
        const result = dfsWithPath(grid, newRow, newCol, target, path, visited);
        if (result) return result;
    }

    path.pop(); // Backtrack
    return null;
}

3. DFS Applications

// Check if path exists between two points
function hasPath(grid, start, end) {
    const [startRow, startCol] = start;
    const [endRow, endCol] = end;

    function dfs(row, col, visited) {
        if (!isValidCell(grid, row, col) || visited.has(coordToKey(row, col))) {
            return false;
        }

        if (row === endRow && col === endCol) {
            return true;
        }

        visited.add(coordToKey(row, col));

        for (const [dr, dc] of DIRECTIONS_4) {
            if (dfs(row + dr, col + dc, visited)) {
                return true;
            }
        }

        return false;
    }

    return dfs(startRow, startCol, new Set());
}

// Find all paths between two points
function findAllPaths(grid, start, end) {
    const [startRow, startCol] = start;
    const [endRow, endCol] = end;
    const allPaths = [];

    function dfs(row, col, path, visited) {
        if (!isValidCell(grid, row, col) || visited.has(coordToKey(row, col))) {
            return;
        }

        const newPath = [...path, [row, col]];

        if (row === endRow && col === endCol) {
            allPaths.push(newPath);
            return;
        }

        const key = coordToKey(row, col);
        visited.add(key);

        for (const [dr, dc] of DIRECTIONS_4) {
            dfs(row + dr, col + dc, newPath, visited);
        }

        visited.delete(key); // Backtrack
    }

    dfs(startRow, startCol, [], new Set());
    return allPaths;
}

Breadth-First Search (BFS)

BFS is ideal for finding shortest paths, level-order traversal, and minimum step problems.

1. Basic BFS Implementation

// Standard BFS
function bfs(grid, startRow, startCol) {
    const queue = [[startRow, startCol, 0]]; // [row, col, distance]
    const visited = new Set();
    const result = [];

    while (queue.length > 0) {
        const [row, col, dist] = queue.shift();
        const key = coordToKey(row, col);

        if (!isValid(grid, row, col) || visited.has(key)) {
            continue;
        }

        visited.add(key);
        result.push([row, col, dist]);

        // Add neighbors
        for (const [dr, dc] of DIRECTIONS_4) {
            const newRow = row + dr;
            const newCol = col + dc;
            if (isValid(grid, newRow, newCol)) {
                queue.push([newRow, newCol, dist + 1]);
            }
        }
    }

    return result;
}

// BFS with level tracking
function bfsLevels(grid, startRow, startCol) {
    const queue = [[startRow, startCol]];
    const visited = new Set([coordToKey(startRow, startCol)]);
    const levels = [];

    while (queue.length > 0) {
        const levelSize = queue.length;
        const currentLevel = [];

        for (let i = 0; i < levelSize; i++) {
            const [row, col] = queue.shift();
            currentLevel.push([row, col]);

            for (const [dr, dc] of DIRECTIONS_4) {
                const newRow = row + dr;
                const newCol = col + dc;
                const key = coordToKey(newRow, newCol);

                if (isValidCell(grid, newRow, newCol) && !visited.has(key)) {
                    visited.add(key);
                    queue.push([newRow, newCol]);
                }
            }
        }

        levels.push(currentLevel);
    }

    return levels;
}

2. BFS for Shortest Path

// Find shortest path between two points
function shortestPath(grid, start, end) {
    const [startRow, startCol] = start;
    const [endRow, endCol] = end;

    const queue = [[startRow, startCol, 0, [[startRow, startCol]]]];
    const visited = new Set([coordToKey(startRow, startCol)]);

    while (queue.length > 0) {
        const [row, col, dist, path] = queue.shift();

        if (row === endRow && col === endCol) {
            return { distance: dist, path };
        }

        for (const [dr, dc] of DIRECTIONS_4) {
            const newRow = row + dr;
            const newCol = col + dc;
            const key = coordToKey(newRow, newCol);

            if (isValidCell(grid, newRow, newCol) && !visited.has(key)) {
                visited.add(key);
                queue.push([newRow, newCol, dist + 1, [...path, [newRow, newCol]]]);
            }
        }
    }

    return null; // No path found
}

// Find shortest distance to any target
function shortestDistanceToTarget(grid, start, targets) {
    const [startRow, startCol] = start;
    const targetSet = new Set(targets.map(([r, c]) => coordToKey(r, c)));

    const queue = [[startRow, startCol, 0]];
    const visited = new Set([coordToKey(startRow, startCol)]);

    while (queue.length > 0) {
        const [row, col, dist] = queue.shift();

        if (targetSet.has(coordToKey(row, col))) {
            return dist;
        }

        for (const [dr, dc] of DIRECTIONS_4) {
            const newRow = row + dr;
            const newCol = col + dc;
            const key = coordToKey(newRow, newCol);

            if (isValidCell(grid, newRow, newCol) && !visited.has(key)) {
                visited.add(key);
                queue.push([newRow, newCol, dist + 1]);
            }
        }
    }

    return -1; // No target reachable
}

3. Multi-source BFS

// BFS from multiple starting points simultaneously
function multiSourceBFS(grid, sources) {
    const queue = [];
    const visited = new Set();
    const distances = createGrid(grid.length, grid[0].length, -1);

    // Initialize with all sources
    for (const [row, col] of sources) {
        queue.push([row, col, 0]);
        visited.add(coordToKey(row, col));
        distances[row][col] = 0;
    }

    while (queue.length > 0) {
        const [row, col, dist] = queue.shift();

        for (const [dr, dc] of DIRECTIONS_4) {
            const newRow = row + dr;
            const newCol = col + dc;
            const key = coordToKey(newRow, newCol);

            if (isValidCell(grid, newRow, newCol) && !visited.has(key)) {
                visited.add(key);
                distances[newRow][newCol] = dist + 1;
                queue.push([newRow, newCol, dist + 1]);
            }
        }
    }

    return distances;
}

// Find nearest source for each cell
function nearestSource(grid, sources) {
    const queue = [];
    const visited = new Set();
    const nearest = createGrid(grid.length, grid[0].length, -1);

    // Initialize with all sources
    for (let i = 0; i < sources.length; i++) {
        const [row, col] = sources[i];
        queue.push([row, col, i]);
        visited.add(coordToKey(row, col));
        nearest[row][col] = i;
    }

    while (queue.length > 0) {
        const [row, col, sourceId] = queue.shift();

        for (const [dr, dc] of DIRECTIONS_4) {
            const newRow = row + dr;
            const newCol = col + dc;
            const key = coordToKey(newRow, newCol);

            if (isValidCell(grid, newRow, newCol) && !visited.has(key)) {
                visited.add(key);
                nearest[newRow][newCol] = sourceId;
                queue.push([newRow, newCol, sourceId]);
            }
        }
    }

    return nearest;
}

Pathfinding Algorithms

1. A* Algorithm

class PriorityQueue {
    constructor() {
        this.heap = [];
    }

    enqueue(item, priority) {
        this.heap.push({ item, priority });
        this.heapifyUp();
    }

    dequeue() {
        if (this.isEmpty()) return null;

        const top = this.heap[0];
        const last = this.heap.pop();

        if (!this.isEmpty()) {
            this.heap[0] = last;
            this.heapifyDown();
        }

        return top.item;
    }

    isEmpty() {
        return this.heap.length === 0;
    }

    heapifyUp() {
        let index = this.heap.length - 1;

        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);

            if (this.heap[index].priority >= this.heap[parentIndex].priority) {
                break;
            }

            [this.heap[index], this.heap[parentIndex]] =
            [this.heap[parentIndex], this.heap[index]];

            index = parentIndex;
        }
    }

    heapifyDown() {
        let index = 0;

        while (2 * index + 1 < this.heap.length) {
            let childIndex = 2 * index + 1;

            if (2 * index + 2 < this.heap.length &&
                this.heap[2 * index + 2].priority < this.heap[childIndex].priority) {
                childIndex = 2 * index + 2;
            }

            if (this.heap[index].priority <= this.heap[childIndex].priority) {
                break;
            }

            [this.heap[index], this.heap[childIndex]] =
            [this.heap[childIndex], this.heap[index]];

            index = childIndex;
        }
    }
}

// Manhattan distance heuristic
function manhattanDistance(pos1, pos2) {
    return Math.abs(pos1[0] - pos2[0]) + Math.abs(pos1[1] - pos2[1]);
}

// A* pathfinding algorithm
function aStar(grid, start, goal) {
    const [startRow, startCol] = start;
    const [goalRow, goalCol] = goal;

    const openSet = new PriorityQueue();
    const closedSet = new Set();
    const gScore = new Map();
    const fScore = new Map();
    const cameFrom = new Map();

    const startKey = coordToKey(startRow, startCol);
    gScore.set(startKey, 0);
    fScore.set(startKey, manhattanDistance(start, goal));
    openSet.enqueue([startRow, startCol], fScore.get(startKey));

    while (!openSet.isEmpty()) {
        const [row, col] = openSet.dequeue();
        const currentKey = coordToKey(row, col);

        if (row === goalRow && col === goalCol) {
            // Reconstruct path
            const path = [];
            let current = currentKey;

            while (current) {
                const [r, c] = keyToCoord(current);
                path.unshift([r, c]);
                current = cameFrom.get(current);
            }

            return path;
        }

        closedSet.add(currentKey);

        for (const [dr, dc] of DIRECTIONS_4) {
            const newRow = row + dr;
            const newCol = col + dc;
            const neighborKey = coordToKey(newRow, newCol);

            if (!isValidCell(grid, newRow, newCol) || closedSet.has(neighborKey)) {
                continue;
            }

            const tentativeGScore = gScore.get(currentKey) + 1;

            if (!gScore.has(neighborKey) || tentativeGScore < gScore.get(neighborKey)) {
                cameFrom.set(neighborKey, currentKey);
                gScore.set(neighborKey, tentativeGScore);
                const hScore = manhattanDistance([newRow, newCol], goal);
                fScore.set(neighborKey, tentativeGScore + hScore);

                openSet.enqueue([newRow, newCol], fScore.get(neighborKey));
            }
        }
    }

    return null; // No path found
}

2. Dijkstra's Algorithm for Weighted Grids

// Dijkstra for weighted grids
function dijkstra(grid, start, end) {
    const [startRow, startCol] = start;
    const [endRow, endCol] = end;

    const distances = createGrid(grid.length, grid[0].length, Infinity);
    const previous = new Map();
    const pq = new PriorityQueue();

    distances[startRow][startCol] = 0;
    pq.enqueue([startRow, startCol], 0);

    while (!pq.isEmpty()) {
        const [row, col] = pq.dequeue();

        if (row === endRow && col === endCol) {
            // Reconstruct path
            const path = [];
            let current = coordToKey(row, col);

            while (current) {
                const [r, c] = keyToCoord(current);
                path.unshift([r, c]);
                current = previous.get(current);
            }

            return {
                distance: distances[endRow][endCol],
                path
            };
        }

        for (const [dr, dc] of DIRECTIONS_4) {
            const newRow = row + dr;
            const newCol = col + dc;

            if (!isValid(grid, newRow, newCol)) continue;

            // Weight is the value in the cell (or 1 for unweighted)
            const weight = typeof grid[newRow][newCol] === 'number' ?
                          grid[newRow][newCol] : 1;

            if (weight === Infinity) continue; // Blocked cell

            const newDistance = distances[row][col] + weight;

            if (newDistance < distances[newRow][newCol]) {
                distances[newRow][newCol] = newDistance;
                previous.set(coordToKey(newRow, newCol), coordToKey(row, col));
                pq.enqueue([newRow, newCol], newDistance);
            }
        }
    }

    return null; // No path found
}

Island and Connected Components

1. Count Islands

// Count number of islands (connected components of 1s)
function numIslands(grid) {
    if (!grid || grid.length === 0) return 0;

    const visited = new Set();
    let count = 0;

    function dfs(row, col) {
        const key = coordToKey(row, col);

        if (!isValid(grid, row, col) ||
            visited.has(key) ||
            grid[row][col] === '0') {
            return;
        }

        visited.add(key);

        for (const [dr, dc] of DIRECTIONS_4) {
            dfs(row + dr, col + dc);
        }
    }

    for (let row = 0; row < grid.length; row++) {
        for (let col = 0; col < grid[0].length; col++) {
            if (grid[row][col] === '1' && !visited.has(coordToKey(row, col))) {
                count++;
                dfs(row, col);
            }
        }
    }

    return count;
}

// Get all islands with their cells
function getAllIslands(grid) {
    const visited = new Set();
    const islands = [];

    function dfs(row, col, island) {
        const key = coordToKey(row, col);

        if (!isValid(grid, row, col) ||
            visited.has(key) ||
            grid[row][col] === '0') {
            return;
        }

        visited.add(key);
        island.push([row, col]);

        for (const [dr, dc] of DIRECTIONS_4) {
            dfs(row + dr, col + dc, island);
        }
    }

    for (let row = 0; row < grid.length; row++) {
        for (let col = 0; col < grid[0].length; col++) {
            if (grid[row][col] === '1' && !visited.has(coordToKey(row, col))) {
                const island = [];
                dfs(row, col, island);
                islands.push(island);
            }
        }
    }

    return islands;
}

2. Largest Island

// Find size of largest island
function maxAreaOfIsland(grid) {
    const visited = new Set();
    let maxArea = 0;

    function dfs(row, col) {
        const key = coordToKey(row, col);

        if (!isValid(grid, row, col) ||
            visited.has(key) ||
            grid[row][col] === 0) {
            return 0;
        }

        visited.add(key);
        let area = 1;

        for (const [dr, dc] of DIRECTIONS_4) {
            area += dfs(row + dr, col + dc);
        }

        return area;
    }

    for (let row = 0; row < grid.length; row++) {
        for (let col = 0; col < grid[0].length; col++) {
            if (grid[row][col] === 1 && !visited.has(coordToKey(row, col))) {
                maxArea = Math.max(maxArea, dfs(row, col));
            }
        }
    }

    return maxArea;
}

// Find perimeter of all islands
function islandPerimeter(grid) {
    let perimeter = 0;

    for (let row = 0; row < grid.length; row++) {
        for (let col = 0; col < grid[0].length; col++) {
            if (grid[row][col] === 1) {
                // Check all 4 directions
                for (const [dr, dc] of DIRECTIONS_4) {
                    const newRow = row + dr;
                    const newCol = col + dc;

                    // If neighbor is out of bounds or water, add to perimeter
                    if (!isValid(grid, newRow, newCol) || grid[newRow][newCol] === 0) {
                        perimeter++;
                    }
                }
            }
        }
    }

    return perimeter;
}

3. Island Shape Matching

// Check if two islands have the same shape
function sameIslandShape(island1, island2) {
    if (island1.length !== island2.length) return false;

    // Normalize both islands to start from (0,0)
    function normalize(island) {
        if (island.length === 0) return [];

        const minRow = Math.min(...island.map(([r]) => r));
        const minCol = Math.min(...island.map(([, c]) => c));

        return island
            .map(([r, c]) => [r - minRow, c - minCol])
            .sort((a, b) => a[0] - b[0] || a[1] - b[1]);
    }

    const norm1 = normalize(island1);
    const norm2 = normalize(island2);

    return JSON.stringify(norm1) === JSON.stringify(norm2);
}

// Get unique island shapes
function getUniqueShapes(grid) {
    const islands = getAllIslands(grid);
    const uniqueShapes = [];

    for (const island of islands) {
        const isUnique = uniqueShapes.every(shape =>
            !sameIslandShape(island, shape)
        );

        if (isUnique) {
            uniqueShapes.push(island);
        }
    }

    return uniqueShapes.length;
}

Flood Fill Algorithms

1. Basic Flood Fill

// Classic flood fill algorithm
function floodFill(grid, row, col, newColor) {
    if (!isValid(grid, row, col)) return grid;

    const originalColor = grid[row][col];
    if (originalColor === newColor) return grid;

    function fill(r, c) {
        if (!isValid(grid, r, c) || grid[r][c] !== originalColor) {
            return;
        }

        grid[r][c] = newColor;

        for (const [dr, dc] of DIRECTIONS_4) {
            fill(r + dr, c + dc);
        }
    }

    fill(row, col);
    return grid;
}

// Iterative flood fill
function floodFillIterative(grid, row, col, newColor) {
    if (!isValid(grid, row, col)) return grid;

    const originalColor = grid[row][col];
    if (originalColor === newColor) return grid;

    const stack = [[row, col]];

    while (stack.length > 0) {
        const [r, c] = stack.pop();

        if (!isValid(grid, r, c) || grid[r][c] !== originalColor) {
            continue;
        }

        grid[r][c] = newColor;

        for (const [dr, dc] of DIRECTIONS_4) {
            stack.push([r + dr, c + dc]);
        }
    }

    return grid;
}

// Boundary flood fill (fill area surrounded by boundary)
function boundaryFill(grid, row, col, fillColor, boundaryColor) {
    if (!isValid(grid, row, col) ||
        grid[row][col] === boundaryColor ||
        grid[row][col] === fillColor) {
        return;
    }

    grid[row][col] = fillColor;

    for (const [dr, dc] of DIRECTIONS_4) {
        boundaryFill(grid, row + dr, col + dc, fillColor, boundaryColor);
    }
}

2. Advanced Flood Fill Variants

// Flood fill with pattern
function patternFill(grid, row, col, pattern) {
    const originalColor = grid[row][col];
    const patternHeight = pattern.length;
    const patternWidth = pattern[0].length;

    function fill(r, c, patternR, patternC) {
        if (!isValid(grid, r, c) || grid[r][c] !== originalColor) {
            return;
        }

        grid[r][c] = pattern[patternR % patternHeight][patternC % patternWidth];

        for (const [dr, dc] of DIRECTIONS_4) {
            fill(r + dr, c + dc, patternR + dr, patternC + dc);
        }
    }

    fill(row, col, 0, 0);
    return grid;
}

// Gradient flood fill
function gradientFill(grid, row, col, startValue, endValue, maxDistance) {
    const visited = new Set();
    const queue = [[row, col, 0]];

    while (queue.length > 0) {
        const [r, c, dist] = queue.shift();
        const key = coordToKey(r, c);

        if (!isValid(grid, r, c) || visited.has(key) || dist > maxDistance) {
            continue;
        }

        visited.add(key);

        // Calculate gradient value
        const ratio = dist / maxDistance;
        const value = startValue + (endValue - startValue) * ratio;
        grid[r][c] = Math.round(value);

        for (const [dr, dc] of DIRECTIONS_4) {
            queue.push([r + dr, c + dc, dist + 1]);
        }
    }

    return grid;
}

// Conditional flood fill
function conditionalFill(grid, row, col, newColor, condition) {
    const originalColor = grid[row][col];

    function fill(r, c) {
        if (!isValid(grid, r, c) || grid[r][c] !== originalColor) {
            return;
        }

        if (!condition(r, c, grid[r][c])) {
            return;
        }

        grid[r][c] = newColor;

        for (const [dr, dc] of DIRECTIONS_4) {
            fill(r + dr, c + dc);
        }
    }

    fill(row, col);
    return grid;
}

Dynamic Programming on Grids

1. Path Counting Problems

// Count unique paths from top-left to bottom-right
function uniquePaths(m, n) {
    const dp = createGrid(m, n, 0);

    // Initialize first row and column
    for (let i = 0; i < m; i++) dp[i][0] = 1;
    for (let j = 0; j < n; j++) dp[0][j] = 1;

    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }

    return dp[m-1][n-1];
}

// Unique paths with obstacles
function uniquePathsWithObstacles(grid) {
    const m = grid.length;
    const n = grid[0].length;

    if (grid[0][0] === 1 || grid[m-1][n-1] === 1) return 0;

    const dp = createGrid(m, n, 0);
    dp[0][0] = 1;

    // Initialize first row
    for (let j = 1; j < n; j++) {
        dp[0][j] = grid[0][j] === 1 ? 0 : dp[0][j-1];
    }

    // Initialize first column
    for (let i = 1; i < m; i++) {
        dp[i][0] = grid[i][0] === 1 ? 0 : dp[i-1][0];
    }

    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            if (grid[i][j] === 1) {
                dp[i][j] = 0;
            } else {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
    }

    return dp[m-1][n-1];
}

// Minimum path sum
function minPathSum(grid) {
    const m = grid.length;
    const n = grid[0].length;

    const dp = cloneGrid(grid);

    // Initialize first row
    for (let j = 1; j < n; j++) {
        dp[0][j] += dp[0][j-1];
    }

    // Initialize first column
    for (let i = 1; i < m; i++) {
        dp[i][0] += dp[i-1][0];
    }

    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[i][j] += Math.min(dp[i-1][j], dp[i][j-1]);
        }
    }

    return dp[m-1][n-1];
}

2. Maximum/Minimum Problems

// Maximum path sum (can move in 4 directions)
function maxPathSum(grid) {
    const m = grid.length;
    const n = grid[0].length;
    const memo = new Map();

    function dfs(row, col) {
        const key = coordToKey(row, col);

        if (!isValid(grid, row, col)) return -Infinity;
        if (memo.has(key)) return memo.get(key);

        let maxSum = grid[row][col];

        for (const [dr, dc] of DIRECTIONS_4) {
            const newRow = row + dr;
            const newCol = col + dc;
            maxSum = Math.max(maxSum, grid[row][col] + dfs(newRow, newCol));
        }

        memo.set(key, maxSum);
        return maxSum;
    }

    let globalMax = -Infinity;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            globalMax = Math.max(globalMax, dfs(i, j));
        }
    }

    return globalMax;
}

// Minimum falling path sum
function minFallingPathSum(grid) {
    const m = grid.length;
    const n = grid[0].length;

    const dp = cloneGrid(grid);

    for (let i = 1; i < m; i++) {
        for (let j = 0; j < n; j++) {
            let minPrev = dp[i-1][j]; // From directly above

            if (j > 0) minPrev = Math.min(minPrev, dp[i-1][j-1]); // From left diagonal
            if (j < n-1) minPrev = Math.min(minPrev, dp[i-1][j+1]); // From right diagonal

            dp[i][j] += minPrev;
        }
    }

    return Math.min(...dp[m-1]);
}

// Maximum square area
function maximalSquare(grid) {
    const m = grid.length;
    const n = grid[0].length;

    const dp = createGrid(m + 1, n + 1, 0);
    let maxSide = 0;

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (grid[i-1][j-1] === '1') {
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1;
                maxSide = Math.max(maxSide, dp[i][j]);
            }
        }
    }

    return maxSide * maxSide;
}

3. Range and Area Problems

// Largest rectangle in histogram (for each row)
function largestRectangleArea(heights) {
    const stack = [];
    let maxArea = 0;

    for (let i = 0; i <= heights.length; i++) {
        const h = i === heights.length ? 0 : heights[i];

        while (stack.length > 0 && h < heights[stack[stack.length - 1]]) {
            const height = heights[stack.pop()];
            const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
            maxArea = Math.max(maxArea, height * width);
        }

        stack.push(i);
    }

    return maxArea;
}

// Maximal rectangle in binary grid
function maximalRectangle(grid) {
    if (!grid || grid.length === 0) return 0;

    const m = grid.length;
    const n = grid[0].length;
    const heights = Array(n).fill(0);
    let maxArea = 0;

    for (let i = 0; i < m; i++) {
        // Update heights for current row
        for (let j = 0; j < n; j++) {
            heights[j] = grid[i][j] === '1' ? heights[j] + 1 : 0;
        }

        // Find max rectangle in current histogram
        maxArea = Math.max(maxArea, largestRectangleArea(heights));
    }

    return maxArea;
}

Advanced Grid Techniques

1. Rotations and Transformations

// Rotate grid 90 degrees clockwise
function rotateGrid(grid) {
    const n = grid.length;
    const rotated = createGrid(n, n);

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            rotated[j][n - 1 - i] = grid[i][j];
        }
    }

    return rotated;
}

// Flip grid horizontally
function flipHorizontal(grid) {
    return grid.map(row => [...row].reverse());
}

// Flip grid vertically
function flipVertical(grid) {
    return [...grid].reverse();
}

// Transpose grid
function transposeGrid(grid) {
    const m = grid.length;
    const n = grid[0].length;
    const transposed = createGrid(n, m);

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            transposed[j][i] = grid[i][j];
        }
    }

    return transposed;
}

// Get all rotations and reflections
function getAllTransformations(grid) {
    const transformations = [];
    let current = grid;

    // 4 rotations
    for (let i = 0; i < 4; i++) {
        transformations.push(cloneGrid(current));
        transformations.push(flipHorizontal(current));
        current = rotateGrid(current);
    }

    return transformations;
}

2. Spiral Traversal

// Spiral traversal of grid
function spiralOrder(grid) {
    if (!grid || grid.length === 0) return [];

    const result = [];
    let top = 0, bottom = grid.length - 1;
    let left = 0, right = grid[0].length - 1;

    while (top <= bottom && left <= right) {
        // Traverse right
        for (let col = left; col <= right; col++) {
            result.push(grid[top][col]);
        }
        top++;

        // Traverse down
        for (let row = top; row <= bottom; row++) {
            result.push(grid[row][right]);
        }
        right--;

        // Traverse left (if we have rows left)
        if (top <= bottom) {
            for (let col = right; col >= left; col--) {
                result.push(grid[bottom][col]);
            }
            bottom--;
        }

        // Traverse up (if we have columns left)
        if (left <= right) {
            for (let row = bottom; row >= top; row--) {
                result.push(grid[row][left]);
            }
            left++;
        }
    }

    return result;
}

// Generate spiral grid
function generateSpiralGrid(n) {
    const grid = createGrid(n, n, 0);
    let top = 0, bottom = n - 1;
    let left = 0, right = n - 1;
    let num = 1;

    while (top <= bottom && left <= right) {
        // Fill right
        for (let col = left; col <= right; col++) {
            grid[top][col] = num++;
        }
        top++;

        // Fill down
        for (let row = top; row <= bottom; row++) {
            grid[row][right] = num++;
        }
        right--;

        // Fill left
        if (top <= bottom) {
            for (let col = right; col >= left; col--) {
                grid[bottom][col] = num++;
            }
            bottom--;
        }

        // Fill up
        if (left <= right) {
            for (let row = bottom; row >= top; row--) {
                grid[row][left] = num++;
            }
            left++;
        }
    }

    return grid;
}

3. Convex Hull and Geometry

// Find convex hull of points in grid
function convexHull(points) {
    if (points.length < 3) return points;

    // Sort points lexicographically
    points.sort((a, b) => a[0] - b[0] || a[1] - b[1]);

    // Build lower hull
    const lower = [];
    for (const point of points) {
        while (lower.length >= 2 &&
               cross(lower[lower.length - 2], lower[lower.length - 1], point) <= 0) {
            lower.pop();
        }
        lower.push(point);
    }

    // Build upper hull
    const upper = [];
    for (let i = points.length - 1; i >= 0; i--) {
        const point = points[i];
        while (upper.length >= 2 &&
               cross(upper[upper.length - 2], upper[upper.length - 1], point) <= 0) {
            upper.pop();
        }
        upper.push(point);
    }

    // Remove last point of each half because it's repeated
    lower.pop();
    upper.pop();

    return lower.concat(upper);
}

// Cross product for convex hull
function cross(O, A, B) {
    return (A[0] - O[0]) * (B[1] - O[1]) - (A[1] - O[1]) * (B[0] - O[0]);
}

// Find all points inside polygon
function pointsInPolygon(grid, polygon) {
    const inside = [];

    for (let row = 0; row < grid.length; row++) {
        for (let col = 0; col < grid[0].length; col++) {
            if (isPointInPolygon([row, col], polygon)) {
                inside.push([row, col]);
            }
        }
    }

    return inside;
}

// Ray casting algorithm for point in polygon
function isPointInPolygon(point, polygon) {
    const [x, y] = point;
    let inside = false;

    for (let i = 0, j = polygon.length - 1; i < polygon.length; j = i++) {
        const [xi, yi] = polygon[i];
        const [xj, yj] = polygon[j];

        if (((yi > y) !== (yj > y)) &&
            (x < (xj - xi) * (y - yi) / (yj - yi) + xi)) {
            inside = !inside;
        }
    }

    return inside;
}

Multi-source and Multi-destination

1. Multiple Sources BFS

// Shortest distance from any source
function shortestDistanceMultiSource(grid, sources) {
    const queue = [];
    const visited = new Set();
    const distances = createGrid(grid.length, grid[0].length, -1);

    // Initialize all sources
    for (const [row, col] of sources) {
        queue.push([row, col, 0]);
        visited.add(coordToKey(row, col));
        distances[row][col] = 0;
    }

    while (queue.length > 0) {
        const [row, col, dist] = queue.shift();

        for (const [dr, dc] of DIRECTIONS_4) {
            const newRow = row + dr;
            const newCol = col + dc;
            const key = coordToKey(newRow, newCol);

            if (isValidCell(grid, newRow, newCol) && !visited.has(key)) {
                visited.add(key);
                distances[newRow][newCol] = dist + 1;
                queue.push([newRow, newCol, dist + 1]);
            }
        }
    }

    return distances;
}

// Find meeting point of multiple sources
function findMeetingPoint(grid, sources) {
    const distanceMaps = sources.map(source =>
        shortestDistanceMultiSource(grid, [source])
    );

    let minMaxDistance = Infinity;
    let meetingPoint = null;

    for (let row = 0; row < grid.length; row++) {
        for (let col = 0; col < grid[0].length; col++) {
            if (!isValidCell(grid, row, col)) continue;

            const maxDistance = Math.max(
                ...distanceMaps.map(distMap => distMap[row][col])
            );

            if (maxDistance < minMaxDistance && maxDistance !== -1) {
                minMaxDistance = maxDistance;
                meetingPoint = [row, col];
            }
        }
    }

    return { point: meetingPoint, distance: minMaxDistance };
}

2. Multiple Destinations

// Find shortest path to any destination
function shortestPathToAnyDestination(grid, start, destinations) {
    const [startRow, startCol] = start;
    const destSet = new Set(destinations.map(([r, c]) => coordToKey(r, c)));

    const queue = [[startRow, startCol, 0, [[startRow, startCol]]]];
    const visited = new Set([coordToKey(startRow, startCol)]);

    while (queue.length > 0) {
        const [row, col, dist, path] = queue.shift();

        if (destSet.has(coordToKey(row, col))) {
            return { destination: [row, col], distance: dist, path };
        }

        for (const [dr, dc] of DIRECTIONS_4) {
            const newRow = row + dr;
            const newCol = col + dc;
            const key = coordToKey(newRow, newCol);

            if (isValidCell(grid, newRow, newCol) && !visited.has(key)) {
                visited.add(key);
                queue.push([newRow, newCol, dist + 1, [...path, [newRow, newCol]]]);
            }
        }
    }

    return null; // No destination reachable
}

// Find all reachable destinations with distances
function allReachableDestinations(grid, start, destinations) {
    const [startRow, startCol] = start;
    const destSet = new Set(destinations.map(([r, c]) => coordToKey(r, c)));
    const results = [];

    const queue = [[startRow, startCol, 0]];
    const visited = new Set([coordToKey(startRow, startCol)]);

    while (queue.length > 0) {
        const [row, col, dist] = queue.shift();

        if (destSet.has(coordToKey(row, col))) {
            results.push({ destination: [row, col], distance: dist });
        }

        for (const [dr, dc] of DIRECTIONS_4) {
            const newRow = row + dr;
            const newCol = col + dc;
            const key = coordToKey(newRow, newCol);

            if (isValidCell(grid, newRow, newCol) && !visited.has(key)) {
                visited.add(key);
                queue.push([newRow, newCol, dist + 1]);
            }
        }
    }

    return results;
}

Usage Examples

console.log("=== Grid-Based Graph Algorithms Demo ===");

// Create sample grids
const binaryGrid = [
    ['1', '1', '0', '0', '0'],
    ['1', '1', '0', '0', '0'],
    ['0', '0', '1', '0', '0'],
    ['0', '0', '0', '1', '1']
];

const pathGrid = [
    [0, 0, 0, 1, 0],
    [1, 1, 0, 1, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0]
]; // 0 = walkable, 1 = blocked

console.log("Original binary grid:");
printGrid(binaryGrid);

// Count islands
const islandCount = numIslands(binaryGrid);
console.log("Number of islands:", islandCount);

// Find all islands
const allIslands = getAllIslands(binaryGrid);
console.log("All islands:", allIslands);

// Largest island area
const maxArea = maxAreaOfIsland(binaryGrid.map(row =>
    row.map(cell => cell === '1' ? 1 : 0)
));
console.log("Largest island area:", maxArea);

// Shortest path finding
console.log("\nPath finding demo:");
printGrid(pathGrid);

const start = [0, 0];
const end = [4, 4];
const shortestPathResult = shortestPath(pathGrid, start, end);

if (shortestPathResult) {
    console.log("Shortest path distance:", shortestPathResult.distance);
    console.log("Path:", shortestPathResult.path);
} else {
    console.log("No path found");
}

// A* pathfinding
const aStarPath = aStar(pathGrid, start, end);
console.log("A* path:", aStarPath);

// Flood fill demo
const floodGrid = [
    [1, 1, 1],
    [1, 1, 0],
    [1, 0, 1]
];

console.log("\nBefore flood fill:");
printGrid(floodGrid);

floodFill(floodGrid, 1, 1, 2);
console.log("After flood fill:");
printGrid(floodGrid);

// Multi-source BFS
const multiSourceGrid = createGrid(5, 5, 0);
const sources = [[0, 0], [4, 4]];
const distances = shortestDistanceMultiSource(multiSourceGrid, sources);

console.log("\nDistances from multiple sources:");
printGrid(distances);

// DFS applications
console.log("\nDFS path finding:");
const dfsPath = dfsWithPath(pathGrid, 0, 0, 0); // Find any 0 (walkable cell)
if (dfsPath) {
    console.log("DFS found path to walkable cell:", dfsPath.slice(0, 5)); // Show first 5 steps
}

// Unique paths counting
const pathCount = uniquePaths(3, 3);
console.log("Unique paths in 3x3 grid:", pathCount);

// Spiral traversal
const spiralGrid = generateSpiralGrid(4);
console.log("\nSpiral grid:");
printGrid(spiralGrid);

const spiral = spiralOrder(spiralGrid);
console.log("Spiral order:", spiral);

// Grid transformations
const originalGrid = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
];

console.log("\nOriginal grid:");
printGrid(originalGrid);

console.log("Rotated 90° clockwise:");
printGrid(rotateGrid(originalGrid));

console.log("Flipped horizontally:");
printGrid(flipHorizontal(originalGrid));

// Dynamic programming example
const dpGrid = [
    [1, 3, 1],
    [1, 5, 1],
    [4, 2, 1]
];

const minSum = minPathSum(cloneGrid(dpGrid));
console.log("Minimum path sum:", minSum);

// Meeting point example
const meetingPointResult = findMeetingPoint(
    createGrid(5, 5, 0),
    [[0, 0], [4, 4], [2, 0]]
);
console.log("Optimal meeting point:", meetingPointResult);

Time Complexity Summary

Algorithm	Time Complexity	Space Complexity
DFS	O(V + E) = O(mn)	O(mn)
BFS	O(V + E) = O(mn)	O(mn)
A*	O(E log V)	O(V)
Dijkstra	O(E log V)	O(V)
Flood Fill	O(mn)	O(mn)
Island Count	O(mn)	O(mn)
Union Find	O(mnα(n))	O(mn)
Multi-source BFS	O(mn)	O(mn)
Unique Paths	O(mn)	O(mn)
Min Path Sum	O(mn)	O(1)

Where m = number of rows, n = number of columns, V = vertices (mn), E = edges (≤ 4mn)

Common Patterns to Remember

1. Boundary Checks Pattern

if (!isValid(grid, row, col) || visited.has(key) || grid[row][col] === blocked) {
    return;
}

2. Direction Iteration Pattern

for (const [dr, dc] of DIRECTIONS_4) {
    const newRow = row + dr;
    const newCol = col + dc;
    // Process neighbor
}

3. Visited Set Pattern

const visited = new Set();
const key = coordToKey(row, col);
if (visited.has(key)) return;
visited.add(key);

4. BFS Level Processing Pattern

while (queue.length > 0) {
    const levelSize = queue.length;
    for (let i = 0; i < levelSize; i++) {
        // Process all nodes at current level
    }
}

5. Multi-source Initialization Pattern

for (const [row, col] of sources) {
    queue.push([row, col, 0]);
    visited.add(coordToKey(row, col));
}

6. Path Reconstruction Pattern

const path = [];
let current = endKey;
while (current) {
    const [r, c] = keyToCoord(current);
    path.unshift([r, c]);
    current = parent.get(current);
}

Key Interview Tips

Always validate coordinates: Use isValid() before accessing grid cells
Choose right traversal: DFS for paths/connectivity, BFS for shortest distance
Use proper data structures: Set for visited, Map for distances/parents
Handle edge cases: Empty grid, single cell, no path exists
Consider 4 vs 8 directions: Clarify movement rules with interviewer
Optimize space: Use in-place modifications when possible
Test with examples: Draw small grids and trace through algorithm
Time vs Space tradeoffs: Sometimes recursion limit requires iterative approach

Real-World Applications

1. Game Development

Pathfinding for NPCs
Line of sight calculations
Procedural map generation

2. Image Processing

Connected component analysis
Flood fill tools
Edge detection

3. Geographic Information Systems

Route planning
Watershed analysis
Land use classification

4. Robotics

Navigation in grid environments
Obstacle avoidance
Coverage path planning

5. Network Analysis

Social network clustering
Infrastructure planning
Facility location problems

This comprehensive guide covers all essential grid-based graph algorithms needed for coding interviews and real-world applications!

Table of Contents​

Grid Fundamentals​

Basic Grid Setup​

Grid Creation Utilities​

Basic Grid Operations​

1. Grid Traversal​

2. Boundary Checking​

Depth-First Search (DFS)​

1. Basic DFS Implementation​

2. DFS with Conditions​

3. DFS Applications​

Breadth-First Search (BFS)​

1. Basic BFS Implementation​

2. BFS for Shortest Path​

3. Multi-source BFS​

Pathfinding Algorithms​

1. A* Algorithm​

2. Dijkstra's Algorithm for Weighted Grids​

Island and Connected Components​

1. Count Islands​

2. Largest Island​

3. Island Shape Matching​

Flood Fill Algorithms​

1. Basic Flood Fill​

2. Advanced Flood Fill Variants​

Dynamic Programming on Grids​

1. Path Counting Problems​

2. Maximum/Minimum Problems​

3. Range and Area Problems​

Advanced Grid Techniques​

1. Rotations and Transformations​

2. Spiral Traversal​

3. Convex Hull and Geometry​

Multi-source and Multi-destination​

1. Multiple Sources BFS​

2. Multiple Destinations​

Usage Examples​

Time Complexity Summary​

Common Patterns to Remember​

1. Boundary Checks Pattern​

2. Direction Iteration Pattern​

3. Visited Set Pattern​

4. BFS Level Processing Pattern​

5. Multi-source Initialization Pattern​

6. Path Reconstruction Pattern​

Key Interview Tips​

Real-World Applications​

1. Game Development​

2. Image Processing​

3. Geographic Information Systems​

4. Robotics​

5. Network Analysis​

Table of Contents