How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

What difficulty level is this interview question?

This is a easy difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Apple.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Apple during technical interviews.

Implement flood fill using BFS and DFS | Apple Interview Question

Q: Implement flood fill using BFS and DFS

This question evaluates proficiency in graph traversal and matrix manipulation, specifically the implementation of BFS and DFS variants for flood fill along with handling recursion, iterative stacks, and in-place updates.

Problem

You are given a 2D grid image of size m × n, where each cell contains an integer color value. You are also given a starting cell (sr, sc) and an integer newColor.

Perform a flood fill starting from (sr, sc):

Let oldColor = image[sr][sc] .
Recolor (sr, sc) and every cell 4-directionally connected (up, down, left, right) to (sr, sc) that has color oldColor to newColor .
Return the modified image .

If oldColor == newColor, the grid should remain unchanged.

Requirements

Write the solution in three ways:

Using BFS .
Using recursive DFS .
Using iterative DFS (explicit stack; no recursion).

Inputs / Outputs

Input: image: int[m][n] , sr: int , sc: int , newColor: int
Output: Modified image after flood fill.

Constraints (typical)

1 ≤ m, n ≤ 50
0 ≤ sr < m , 0 ≤ sc < n
Color values are non-negative integers.

Example

Given:

image = [[1,1,1],[1,1,0],[1,0,1]] , sr = 1 , sc = 1 , newColor = 2

Output:

[[2,2,2],[2,2,0],[2,0,1]]

Problem

You are given a 2D grid image of size m × n, where each cell contains an integer color value. You are also given a starting cell (sr, sc) and an integer newColor.

Perform a flood fill starting from (sr, sc):

Let oldColor = image[sr][sc] .

Recolor (sr, sc) and every cell 4-directionally connected (up, down, left, right) to (sr, sc) that has color oldColor to newColor .

Return the modified image .

If oldColor == newColor, the grid should remain unchanged.

Implement flood fill using BFS and DFS

Quick Overview

Problem

Requirements

Inputs / Outputs

Constraints (typical)

Example

Comments (0)

Implement flood fill using BFS and DFS

Quick Overview

Problem

Requirements

Inputs / Outputs

Constraints (typical)

Example

Comments (0)