DFS on Matrix

This technique uses recursion to traverse a matrix (or 2D array) 4-directionally in a depth-first search manner.

How to Identify

• Data Structure Involves: Matrix
• Question Type: If the problem requires searching for something in a matrix.

Example

Flood Fill

An image is represented by a m x n integer grid image where image[i][j] represents the pixel value of the image.

Given an image, the location of a pixel in the image and a new color, replace the color of the given pixel and all adjacent (4-directionally) same-colored pixels with the given color.

Example

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]

Typescript

function floodFill(image: number[][], sr: number, sc: number, newColor: number): number[][] {
    const oldColor = image[sr][sc]
    fill(image, oldColor, newColor, image.length, image[0].length, sr, sc)
    return image
}

function fill(image: number[][], oldColor: number, newColor: number, ROWS: number, COLS: number, r: number, c: number){
    // base case
    if(r < 0 ||  r  >= ROWS || c < 0 || c >= COLS || image[r][c] != oldColor || image[r][c] == newColor) return
    
    image[r][c] = newColor

    // recursive case
    fill(image, oldColor, newColor, ROWS, COLS, r, c - 1) //left
    fill(image, oldColor, newColor, ROWS, COLS, r, c + 1) //right
    fill(image, oldColor, newColor, ROWS, COLS, r - 1, c) //Top
    fill(image, oldColor, newColor, ROWS, COLS, r + 1, c) //Bottom
}

Related Problems

	Problems	Difficulty
1	Flood Fill	Easy
2	Number of Islands	Medium
3	Pacific Atlantic Water Flow	Medium