This approach uses recursion to explore all connected pixels that need to be updated. Starting from the initial pixel, you recursively attempt to update all four possible directions (up, down, left, right) whenever the neighboring pixel has the same original color.
The recursion ensures that all connected and valid pixels are eventually updated. Make sure to handle the base case where the function stops if the pixel is out of bounds or if it doesn't need updating (either because it's already updated or has a different color).
Time Complexity: O(m * n) because in the worst case, all of the pixels will be connected and thus changed.
Space Complexity: O(m * n) due to the recursion call stack.
1#include <stdio.h>
2
3void dfs(int** image, int m, int n, int r, int c, int originalColor, int newColor) {
4 if (r < 0 || r >= m || c < 0 || c >= n || image[r][c] != originalColor) return;
5 image[r][c] = newColor;
6 dfs(image, m, n, r + 1, c, originalColor, newColor);
7 dfs(image, m, n, r - 1, c, originalColor, newColor);
8 dfs(image, m, n, r, c + 1, originalColor, newColor);
9 dfs(image, m, n, r, c - 1, originalColor, newColor);
10}
11
12int** floodFill(int** image, int m, int n, int sr, int sc, int color, int* returnSize, int** returnColumnSizes) {
13 int originalColor = image[sr][sc];
14 if (originalColor != color) {
15 dfs(image, m, n, sr, sc, originalColor, color);
16 }
17 return image;
18}This C solution implements DFS similarly to the Python version but requires direct pointer manipulations and array index bounds checking.
This approach employs an iterative breadth-first search (BFS) using a queue. Starting from the initial pixel, we enqueue it and begin the BFS process, updating connected pixels of the same original color to the new color.
For each pixel, check its adjacent pixels and enqueue them if they are valid and of the original color. This continues until the queue is empty, ensuring all pixels are updated appropriately.
Time Complexity: O(m * n), where m and n are the dimensions of the image (same as DFS).
Space Complexity: O(m * n), as we may store all pixels in the queue in the worst-case scenario.
1using System.Collections.Generic;
2
3public class Solution {
4 public int[][] FloodFill(int[][] image, int sr, int sc, int newColor) {
5 int originalColor = image[sr][sc];
6 if (originalColor == newColor) return image;
7
8 int rows = image.Length;
9 int cols = image[0].Length;
10 Queue<(int, int)> queue = new Queue<(int, int)>();
11 queue.Enqueue((sr, sc));
12
13 int[][] directions = new int[][] { new int[] {1, 0}, new int[] {-1, 0}, new int[] {0, 1}, new int[] {0, -1} };
14
15 while (queue.Count > 0) {
16 var (r, c) = queue.Dequeue();
17 if (image[r][c] == originalColor) {
18 image[r][c] = newColor;
19 foreach (var d in directions) {
20 int rr = r + d[0], cc = c + d[1];
21 if (rr >= 0 && rr < rows && cc >= 0 && cc < cols && image[rr][cc] == originalColor) {
22 queue.Enqueue((rr, cc));
23 }
24 }
25 }
26 }
27
28 return image;
29 }
30}The C# implementation employs a Queue for the BFS logic, exploring and updating pixels iteratively. It checks each adjacent pixel and enqueues eligible pixels until all are processed.