003 — Flood Fill

Source

• Original source: Classic paint-bucket / flood fill exercise
• Platform: LeetCode — https://leetcode.com/problems/flood-fill/
• Topic: graphs
• Difficulty: Easy
• Pattern: DFS on a grid (implicit graph)
• Basic idea inherited from: recursion (../../06-recursion-and-backtracking/); grid-as-graph

1. Problem in simple words

একটা image দেওয়া আছে — সংখ্যা দিয়ে ভরা একটা 2D grid, প্রতিটা সংখ্যা একটা pixel-এর রং। তোমাকে একটা শুরুর pixel (sr, sc) আর একটা নতুন রং color দেওয়া হবে। শুরুর pixel-টা আর তার সাথে 4-দিকে (উপর/নিচ/বাম/ডান) লেগে থাকা একই রঙের সব pixel-কে নতুন রঙে বদলে দাও — ঠিক image editor-এর paint-bucket tool যেভাবে কাজ করে।

আগে (start (1,1), new color 2):    পরে:
  1 1 1                               2 2 2
  1 1 0                               2 2 0
  1 0 1                               2 0 1

2. Which basic idea does this inherit from?

মূল ভিত হলো recursion (../../06-recursion-and-backtracking/) আর grid-as-graph। একটা grid আসলে একটা implicit graph: প্রতিটা cell একটা node, আর তার 4 প্রতিবেশী হলো তার edges (../concept.md)। DFS এই graph-এ এক pixel থেকে নেমে recursively একই-রঙা প্রতিবেশীতে ছড়ায় — ../dfs.md-এর "flood fill = pixels-এ DFS"।

3. What is the hidden math or logic?

লুকানো logic: যে সব pixel শুরুর pixel-এর সাথে একই-রঙা পথ ধরে connected, তারা মিলে একটা connected region তৈরি করে। DFS এই region-এর প্রতিটা pixel ঠিক একবার ছোঁয়। মোক্ষম জায়গা — recolor করাটাই visited-marking: একবার একটা pixel নতুন রং পেয়ে গেলে সে আর old রঙের সাথে match করে না, তাই আবার ছোঁয়া হয় না। এই কারণেই old == color হলে আগেই থামতে হয়, নাহলে কিছুই বদলায় না বলে DFS চিরকাল loop করবে।

4. Which data structure is needed?

• Grid নিজেই — কোনো আলাদা adjacency list লাগে না; 4-দিকের offset গুলোই edges।
• Recursion (call stack) — DFS-এর implicit stack; কোনো দৃশ্যমান visited set লাগে না কারণ recolor-ই mark।

5. Why this data structure fits

Grid implicit graph হিসেবে fit করে কারণ neighbor গুলো on the fly compute করা যায় — (r±1, c) আর (r, c±1); কোনো dict বানানোর দরকার নেই। আর recursion fit করে কারণ flood fill-এর গঠনটাই self-similar: "এই pixel রং করো, তারপর প্রতিটা প্রতিবেশীতে একই কাজ করো" — হুবহু recursive সংজ্ঞা।

6. Real-life analogy

একটা coloring book-এর একটা আবদ্ধ ঘরে এক ফোঁটা রং ফেলো। রংটা ছড়াতে থাকে যতক্ষণ না কোনো সীমারেখায় (ভিন্ন রঙে) আটকায়। flood fill ঠিক তাই: শুরুর pixel থেকে রং ততক্ষণ ছড়ায় যতক্ষণ একই-রঙা pixel পাওয়া যায়; ভিন্ন রং বা grid-এর প্রান্ত এলেই থেমে যায়।

7. Visual explanation

image এর (1,1), রং 1, নতুন রং 2 দিয়ে দেখি কীভাবে DFS ছড়ায়:

grid (. = ভিন্ন রং, সীমা):
  1 1 1                start = (1,1)
  1 1 .
  1 . 1

DFS ক্রম (recolor = mark):
  (1,1)->2  ->  (0,1)->2  ->  (0,0)->2  ->  (0,2)->2
            ->  (1,0)->2  ->  (2,0)->2
  (2,1)=. থামো,  (1,2)=. থামো,  (2,2) connected না

ফল:
  2 2 2
  2 2 .
  2 . 1

8. Example input and output

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]]

Edge case (নতুন রং == পুরোনো রং): image = [[0,0,0],[0,0,0]], sr=0, sc=0, color=0
Output: [[0,0,0],[0,0,0]]   (কোনো পরিবর্তন নেই; infinite loop এড়াতে আগেই return)

9. Brute force thinking

সরল চিন্তা: পুরো grid বারবার scan করো; যতবার এমন কোনো old-রঙা pixel পাও যে ইতিমধ্যে রং-হওয়া কোনো pixel-এর প্রতিবেশী, তাকে রং করো — যতক্ষণ না একটা পুরো pass-এ আর কিছু বদলায়।

পুনরাবৃত্তি করো:
  grid scan করো
  rang-হওয়া কোনো cell-এর প্রতিবেশী old-রঙা cell পেলে রং করো
যতক্ষণ একটা pass-এ কোনো পরিবর্তন না হয়

10. Why brute force is slow

বারবার পুরো grid scan করা মানে region-এর প্রতিটা cell রং হতে পুরো একেকটা O(R·C) pass লাগতে পারে — সবমিলে অনেক বেশি কাজ। DFS (বা BFS) প্রতিটা cell ঠিক একবার ছোঁয়, পুরো region O(R·C)-তেই শেষ — repeated scanning সম্পূর্ণ অপ্রয়োজনীয়।

11. Key observation

মূল observation: রং করা মানেই দেখা-হয়ে-গেছে চিহ্নিত করা। আলাদা visited set লাগে না — একটা pixel নতুন রং পাওয়ার পর সে আর old-এর সাথে match করে না, তাই স্বাভাবিকভাবেই আর প্রক্রিয়া হয় না। শুধু খেয়াল: old == color হলে এই চিহ্নিতকরণটাই কাজ করে না, তাই আগে থামতে হবে।

12. Optimized intuition

শুরুর pixel-এর old রং মনে রাখো। যদি old == color, কিছু করার নেই — return। নাহলে DFS: cell-টা bounds-এর ভেতরে আর old-রঙা হলে তাকে নতুন রং দাও, তারপর তার 4 প্রতিবেশীতে recurse করো। recolor নিজেই mark, তাই কোনো loop হয় না।

13. Thinking tweak

মোচড়: "কোন pixel গুলো একই region-এ আছে আগে বের করব, তারপর রং করব" না ভেবে ভাবো "এই pixel রং করো, তারপর হুবহু একই কাজ চার প্রতিবেশীতে চালাও।" region খোঁজা আর রং করা একই recursive পদক্ষেপে মিলে যায়।

14. Step-by-step dry run

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

1. old = image[1][1] = 1। old != color (2), তাই এগোও।
2. dfs(1,1): bounds OK, value 1 == old → রং 2। প্রতিবেশী: (0,1),(2,1),(1,0),(1,2)।
3. dfs(0,1): 1 == old → রং 2। প্রতিবেশী (0,0),(0,2) পরে রং পাবে।
4. dfs(0,0): 1 → 2। dfs(0,2): 1 → 2।
5. dfs(2,1): value 0 ≠ old → থামো। dfs(1,2): value 0 ≠ old → থামো।
6. dfs(1,0): 1 → 2। প্রতিবেশী dfs(2,0): 1 → 2।
7. (2,2) কখনো connected না, রং 1-ই থাকে। ফল: [[2,2,2],[2,2,0],[2,0,1]]।

15. Python solution

def flood_fill(image, sr, sc, color):
    R, C = len(image), len(image[0])
    old = image[sr][sc]
    if old == color:                 # crucial: একই রং হলে infinite loop এড়াও
        return image

    def dfs(r, c):
        # grid = implicit graph; recolor করাটাই visited-mark
        if 0 <= r < R and 0 <= c < C and image[r][c] == old:
            image[r][c] = color
            for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                dfs(r + dr, c + dc)  # recursion = call stack DFS

    dfs(sr, sc)
    return image

# ---- tests ----
assert flood_fill([[1, 1, 1], [1, 1, 0], [1, 0, 1]], 1, 1, 2) == [[2, 2, 2], [2, 2, 0], [2, 0, 1]]
assert flood_fill([[0, 0, 0], [0, 0, 0]], 0, 0, 0) == [[0, 0, 0], [0, 0, 0]]   # same color
assert flood_fill([[0, 0, 0], [0, 1, 0]], 1, 1, 2) == [[0, 0, 0], [0, 2, 0]]   # একা pixel
print("সব test pass!")

16. Line-by-line code explanation

• R, C = len(image), len(image[0]) — grid-এর মাপ, bounds check-এর জন্য।
• old = image[sr][sc] — যে রংটা flood করতে হবে; এটাই DFS-এর match শর্ত।
• if old == color: return image — নতুন রং পুরোনোটার সমান হলে কিছু বদলায় না, আর mark কাজ না করায় infinite loop হতো; তাই আগে থামো।
• if 0 <= r < R and 0 <= c < C and image[r][c] == old — bounds-এর ভেতরে আর old-রঙা হলেই এগোও; index করার আগে bounds check।
• image[r][c] = color — recolor; এটাই visited-marking।
• for dr, dc in (...) — চার প্রতিবেশীতে recurse; offset list-ই হলো implicit edges।

17. Output walkthrough

flood_fill([[1,1,1],[1,1,0],[1,0,1]], 1, 1, 2): old = 1, color = 2, আলাদা। (1,1) থেকে DFS ছড়িয়ে সব connected 1-কে 2 করে; 0 আর বিচ্ছিন্ন কোণার 1 অছোঁয়া থাকে → [[2,2,2],[2,2,0],[2,0,1]]। same-color test কিছু না বদলে return করে। শেষে print: সব test pass!।

18. Time complexity

O(R · C) — সবচেয়ে খারাপ ক্ষেত্রে (পুরো grid এক রঙ) প্রতিটা cell ঠিক একবার visit হয়।

19. Space complexity

O(R · C) — recursion-এর call stack সবচেয়ে খারাপ ক্ষেত্রে পুরো region গভীরে নামতে পারে (এক লম্বা snake-আকৃতির region)। আলাদা visited structure লাগে না।

20. Common mistakes

• old == color check বাদ দেওয়া — তখন recolor mark হিসেবে কাজ করে না, DFS চিরকাল loop করে।
• index করার আগে bounds check না করা — Python negative index-কে চুপিচুপি wrap করে ভুল cell ছোঁয়।
• recolor করার আগে recurse করা — region আবার আবার ছোঁয়া হয়ে loop হয়।
• diagonal প্রতিবেশী যোগ করে ফেলা যখন শুধু 4-direction চাওয়া।

21. Which basic problem this inherits from

ভিত্তি: recursion (../../06-recursion-and-backtracking/) আর grid-as-graph (../concept.md-এর neighbors snippet)। ../dfs.md-এর flood_fill snippet হুবহু এই pattern — paint-bucket = DFS, recolor = mark। এর ঠিক উপরেই দাঁড়ায় Number of Islands (#4): flood fill plus একটা counter।

22. Similar harder problems

• Number of Islands (flood fill + component counter) — https://leetcode.com/problems/number-of-islands/ (এই tracker-এর #4)
• Max Area of Island (flood fill + size গোনা) — https://leetcode.com/problems/max-area-of-island/ (#5)
• Pacific Atlantic Water Flow (border থেকে reverse flood) — https://leetcode.com/problems/pacific-atlantic-water-flow/ (#14)

23. Pattern learned

DFS flood fill on a grid: grid কে implicit graph ধরে এক cell থেকে recursively connected region ছড়ানো, যেখানে cell mutate করাই (recolor / sink) visited-marking। এটাই গোটা grid-component পরিবারের মূল building block।

24. Final summary

ভবিষ্যতের আমাকে: "flood fill = grid-এ DFS, যেখানে রং বদলানোটাই দেখা-হলো চিহ্ন।" old == color হলে আগেই থামবে; নাহলে bounds + match check করে cell রং করে চার প্রতিবেশীতে recurse করবে। এই reflex পাকা হলে islands, area, reverse-flood — সব এর উপর গড়ে উঠবে।

25. JavaScript solution (with test cases)

const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };

function floodFill(image, sr, sc, color) {
  const R = image.length, C = image[0].length;
  const old = image[sr][sc];
  if (old === color) return image;             // crucial: একই রং হলে infinite loop এড়াও

  const dfs = (r, c) => {
    // grid = implicit graph; recolor করাটাই visited-mark
    if (r >= 0 && r < R && c >= 0 && c < C && image[r][c] === old) {
      image[r][c] = color;
      dfs(r - 1, c); dfs(r + 1, c); dfs(r, c - 1); dfs(r, c + 1);  // চার প্রতিবেশী
    }
  };
  dfs(sr, sc);
  return image;
}

const eq = (a, b) => JSON.stringify(a) === JSON.stringify(b);

// ---- test cases ----
assert(eq(floodFill([[1, 1, 1], [1, 1, 0], [1, 0, 1]], 1, 1, 2), [[2, 2, 2], [2, 2, 0], [2, 0, 1]]), "basic");
assert(eq(floodFill([[0, 0, 0], [0, 0, 0]], 0, 0, 0), [[0, 0, 0], [0, 0, 0]]), "same color");
assert(eq(floodFill([[0, 0, 0], [0, 1, 0]], 1, 1, 2), [[0, 0, 0], [0, 2, 0]]), "একা pixel");
console.log("সব JS test pass!");

JS টীকা: old === color check-টা গুরুত্বপূর্ণ — JS-এও recolor-ই হলো visited-mark, তাই নতুন রং পুরোনোটার সমান হলে mark কাজ করে না আর DFS অসীম loop করবে; তাই আগেই return। bounds check অবশ্যই index করার আগে করতে হয়, কারণ JS-এ out-of-range index undefined দেয় (Python-এর negative-wrap-এর মতো নয়, কিন্তু তবু ভুল)। 2D array তুলনায় JSON.stringify।

26. TypeScript solution (with test cases)

type Image = number[][];

function floodFill(image: Image, sr: number, sc: number, color: number): Image {
  const R = image.length, C = image[0].length;
  const old = image[sr][sc];
  if (old === color) return image;

  const dfs = (r: number, c: number): void => {
    if (r >= 0 && r < R && c >= 0 && c < C && image[r][c] === old) {
      image[r][c] = color;
      dfs(r - 1, c); dfs(r + 1, c); dfs(r, c - 1); dfs(r, c + 1);
    }
  };
  dfs(sr, sc);
  return image;
}

const expect = (cond: boolean, msg = ""): void => { if (!cond) throw new Error("FAIL " + msg); };
const eq = (a: Image, b: Image): boolean =>
  a.length === b.length && a.every((row, i) => row.length === b[i].length && row.every((v, j) => v === b[i][j]));

expect(eq(floodFill([[1, 1, 1], [1, 1, 0], [1, 0, 1]], 1, 1, 2), [[2, 2, 2], [2, 2, 0], [2, 0, 1]]), "basic");
expect(eq(floodFill([[0, 0, 0], [0, 0, 0]], 0, 0, 0), [[0, 0, 0], [0, 0, 0]]), "same");
expect(eq(floodFill([[0, 0, 0], [0, 1, 0]], 1, 1, 2), [[0, 0, 0], [0, 2, 0]]), "একা");
console.log("সব TS test pass!");

TS টীকা: type Image = number[][] grid-এর আকার type-এ লিখে দেয়, তাই image[r][c]-এ ভুল করে string তুলনা করলে compiler ধরবে। sr, sc, color সব number — coordinate আর রং একই ধরনের, ভুল argument-order সহজে আটকায়। return type Image নিশ্চিত করে function পরিবর্তিত grid-ই ফেরত দেয়।

27. কোথায় কাজে লাগে (real-world use)

• Paint-bucket tool: যেকোনো image editor (Photoshop, MS Paint)-এ একটা region একই রঙে ভরে দেওয়া — এটাই আক্ষরিক flood fill।
• Region selection / magic wand: একটা pixel ক্লিক করলে তার সাথে একই-রঙা connected অঞ্চল select করা।
• Maze / connectivity check: একটা কোষ থেকে শুরু করে কোন কোষগুলোতে পৌঁছানো যায় তা বের করা (reachability)।
• Game mechanics: Minesweeper-এ খালি ঘর খোলা, বা match-3/puzzle গেমে connected একই-রঙা গুচ্ছ চিহ্নিত করা।
• Terrain / GIS labeling: একটা মানচিত্রে একই ধরনের ভূমি (পানি, বন) connected অঞ্চল হিসেবে রং করা।

মূল সুর: "একটা শুরু-বিন্দু থেকে connected একই-ধরনের region ছড়াও/রং করো" — grid-কে implicit graph ধরে DFS/BFS, আর cell mutate করাই visited-mark। এর উপরেই islands, area, reverse-flood দাঁড়ায়।

---

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।