009 — 01 Matrix

Source

• Original source: Classic multi-source BFS distance exercise
• Platform: LeetCode — https://leetcode.com/problems/01-matrix/
• Topic: graphs
• Difficulty: Medium
• Pattern: multi-source BFS on a grid (distance to the nearest target)
• Basic idea inherited from: Rotting Oranges (এই tracker-এর #8, 008-rotting-oranges.md); multi-source BFS (../bfs.md)

1. Problem in simple words

তোমাকে একটা m x n binary matrix mat দেওয়া আছে — প্রতিটা cell হয় 0 নয় 1। প্রতিটা cell-এর জন্য বের করো তার সবচেয়ে কাছের 0-এর দূরত্ব কত, যেখানে দূরত্ব মাপা হয় চার দিকের (উপর-নিচ-বাম-ডান) পদক্ষেপে। উত্তর হিসেবে একই আকারের একটা matrix ফেরত দাও, যেখানে প্রতিটা ঘরে সেই দূরত্ব লেখা। (0-cell গুলোর দূরত্ব অবশ্যই 0।)

mat:              উত্তর (প্রতিটা cell -> nearest 0-এর দূরত্ব):
  0 0 0             0 0 0
  0 1 0             0 1 0
  1 1 1             1 2 1

2. Which basic idea does this inherit from?

মূল ভিত হলো multi-source BFS (#8 Rotting Oranges)। ওখানে সব পচা কমলা একসাথে seed করে ঢেউ ছড়িয়েছিলাম; এখানে সব 0-cell একসাথে seed করব (দূরত্ব 0), আর ঢেউ ছড়িয়ে প্রতিটা 1-cell-কে দেবে তার nearest 0 পর্যন্ত দূরত্ব। হুবহু একই trick — শুধু "source" এবার পচা কমলা নয়, প্রতিটা 0। BFS-এর first-arrival = shortest থিওরেমই নিশ্চিত করে প্রথম যে ঢেউ কোনো cell-কে ছোঁয়, সেটাই nearest।

3. What is the hidden math or logic?

লুকানো logic: "প্রতিটা cell-এর nearest source পর্যন্ত দূরত্ব" = সব source একসাথে seed করা multi-source BFS। ভুল পথ হবে প্রতিটা 1-cell থেকে আলাদা করে nearest 0 খোঁজা — তাতে বহুবার BFS, খরচ বিশাল। সঠিক উল্টো চিন্তা: 0-গুলো থেকে BFS শুরু করো; সব 0 queue-তে distance 0-তে; BFS layer ছড়ালে প্রতিটা 1-cell প্রথমবার যে layer-এ ছোঁয়া হয়, সেটাই তার nearest 0-এর দূরত্ব (first-arrival = shortest, কারণ সব edge cost সমান)।

4. Which data structure is needed?

• Grid নিজেই — implicit graph; neighbor চার দিকের cell।
• collections.deque — BFS frontier; multi-source বলে শুরুতেই সব 0-cell ঢোকে।
• distance matrix (dist) — উত্তর; একই সাথে visited-marker (যে cell-এর dist এখনো set হয়নি, সে unvisited)।

5. Why this data structure fits

Grid-কে graph ধরা fit করে কারণ neighbor চার দিকেই fixed আর দূরত্ব মাপা step গোনা। deque fit করে কারণ BFS-এর FIFO-ই first-arrival = shortest নিশ্চিত করে; heap লাগে না, কারণ সব edge-এর cost সমান (1)। dist matrix double-duty করে — উত্তর জমা রাখে আর dist[nr][nc] == -1 (বা সেট-হয়নি) দিয়ে visited চেক করে, আলাদা visited set বাঁচায়।

6. Real-life analogy

একটা মাঠে কয়েকটা পানির কল (0) ছড়িয়ে আছে, বাকি জায়গা শুকনো (1)। প্রতিটা শুকনো জায়গা থেকে সবচেয়ে কাছের কলে যেতে কত পা লাগে জানতে চাও। প্রতিটা শুকনো জায়গায় দাঁড়িয়ে কল খুঁজতে বেরোনোর বদলে উল্টোটা করো: সব কল থেকে একসাথে পানি ছড়াতে দাও। যে জায়গায় পানি যত মিনিটে পৌঁছাল, সেটাই সেই জায়গার nearest কলের দূরত্ব — কারণ সবচেয়ে কাছের কলের ঢেউই আগে পৌঁছায়।

7. Visual explanation

mat = [[0,0,0],[0,1,0],[1,1,1]] দিয়ে ঢেউ ছড়ানো (. = এখনো অসেট):

seed (সব 0, distance 0):     ঢেউ layer 1:           ঢেউ layer 2:
  0 0 0                        0 0 0                  0 0 0
  0 . 0                        0 1 0                  0 1 0
  . . .                        1 . 1                  1 2 1

(1,1) layer 1-এ ছোঁয়া (উপরের/পাশের 0 থেকে)।
(2,1) layer 2-এ ছোঁয়া (তার আগে layer 1-এর 1-cell গুলো থেকে)।
উত্তর = শেষ grid

8. Example input and output

Input : mat = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[0,0,0],[0,1,0],[0,0,0]]

Input : mat = [[0,0,0],[0,1,0],[1,1,1]]
Output: [[0,0,0],[0,1,0],[1,2,1]]

Edge case (একটাই 0, বাকি সব 1): mat = [[1,1],[1,0]] -> [[2,1],[1,0]]

9. Brute force thinking

প্রথম সরল চিন্তা: প্রতিটা 1-cell-এর জন্য আলাদা করে nearest 0 খোঁজা — যেমন প্রতিটা 1-cell থেকে একটা পুরো BFS চালিয়ে প্রথম 0-তে পৌঁছানো পর্যন্ত দূরত্ব মাপা, বা প্রতিটা 1-cell থেকে প্রতিটা 0-cell-এর Manhattan distance তুলনা করে minimum নেওয়া।

1) প্রতিটা cell (r,c) যেটা 1:
2)   (r,c) থেকে BFS চালিয়ে nearest 0-এর দূরত্ব মাপো
3)   সেই দূরত্ব dist[r][c]-এ লেখো

10. Why brute force is slow

প্রতিটা 1-cell থেকে আলাদা BFS মানে O(m·n) cell-এর প্রত্যেকটার জন্য O(m·n) কাজ — মোট O((m·n)^2), বড় matrix-এ অসহনীয়। সব 0-cell-এর সাথে দূরত্ব তুলনা করলেও একই রকম খারাপ। অথচ একটাই multi-source BFS — সব 0 একসাথে seed করে — প্রতিটা cell ঠিক একবার ছোঁয়, মোট O(m·n)। মূল ভুল: দিক উল্টো; 1 থেকে 0 না খুঁজে 0 থেকে ঢেউ ছড়াও।

11. Key observation

মূল observation: BFS-টা উল্টো দিকে চালাও — 0-গুলো থেকে, 1-গুলো থেকে নয়। সব 0 একসাথে distance 0-তে seed করলে এক BFS-ই প্রতিটা 1-cell-কে তার nearest 0-এর দূরত্ব দিয়ে দেয়, কারণ সবচেয়ে কাছের source-এর ঢেউ আগে পৌঁছায় (first-arrival = shortest)।

12. Optimized intuition

dist matrix বানাও — সব 0-cell-এ 0, বাকি সব -1 (অসেট/unvisited)। সব 0-cell queue-তে ঢোকাও। তারপর সাধারণ BFS: front pop করো, প্রতিটা প্রতিবেশী যার dist == -1, তাকে dist[cur] + 1 দাও আর enqueue করো। queue খালি হলে dist-ই উত্তর। প্রতিটা cell একবার set হয় (first arrival), একবার pop হয় — O(m·n)।

13. Thinking tweak

মোচড়: "প্রতিটা 1 থেকে nearest 0 খুঁজব" না ভেবে দিকটা উল্টে দাও — "সব 0 থেকে একসাথে ঢেউ ছড়াই, প্রতিটা 1 প্রথম যে ঢেউ ছোঁয় সেটাই তার উত্তর।" বহু BFS থেকে নেমে এসো একটাই reverse multi-source BFS-এ। কোন দিক থেকে শুরু করছ — সেটাই এই problem-এর আসল মোচড়।

14. Step-by-step dry run

mat = [[1,1],[1,0]]:

1. dist = [[-1,-1],[-1,0]]। queue = [(1,1)] (একমাত্র 0)।
2. pop (1,1) → প্রতিবেশী (0,1) (dist -1) → dist[0][1] = 1, enqueue; (1,0) (dist -1) → dist[1][0] = 1, enqueue।
3. pop (0,1) → প্রতিবেশী (0,0) (dist -1) → dist[0][0] = 2, enqueue; (1,1) already 0।
4. pop (1,0) → প্রতিবেশী (0,0) already 2 (set), (1,1) already 0। নতুন কিছু না।
5. pop (0,0) → প্রতিবেশী সব set। queue খালি।
6. return dist = [[2,1],[1,0]]।

15. Python solution

from collections import deque


def update_matrix(mat):
    R, C = len(mat), len(mat[0])
    dist = [[-1] * C for _ in range(R)]   # -1 মানে এখনো অসেট (unvisited)
    q = deque()
    # multi-source seeding: সব 0-cell distance 0-তে
    for r in range(R):
        for c in range(C):
            if mat[r][c] == 0:
                dist[r][c] = 0
                q.append((r, c))

    while q:
        r, c = q.popleft()
        for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            nr, nc = r + dr, c + dc
            if (0 <= nr < R and 0 <= nc < C and dist[nr][nc] == -1):
                dist[nr][nc] = dist[r][c] + 1   # first arrival = nearest 0
                q.append((nr, nc))              # mark করার সময়ই enqueue
    return dist


# ---- tests ----
m1 = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
m2 = [[0, 0, 0], [0, 1, 0], [1, 1, 1]]
m3 = [[1, 1], [1, 0]]
m4 = [[0, 1, 1, 0]]

assert update_matrix(m1) == [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
assert update_matrix(m2) == [[0, 0, 0], [0, 1, 0], [1, 2, 1]]
assert update_matrix(m3) == [[2, 1], [1, 0]]
assert update_matrix(m4) == [[0, 1, 1, 0]]
print("সব test pass!")

16. Line-by-line code explanation

• dist = [[-1] * C ...] — -1 দ্বৈত কাজ করে: উত্তরের placeholder আর "এখনো visit হয়নি" চিহ্ন।
• প্রথম double loop — সব 0-cell-কে dist = 0 দিয়ে queue-তে (multi-source seeding)।
• q.popleft() — deque-এর O(1) front pop; FIFO-ই first-arrival = shortest নিশ্চিত করে।
• if 0 <= nr < R and 0 <= nc < C and dist[nr][nc] == -1 — bounds আগে, তারপর শুধু অসেট প্রতিবেশী।
• dist[nr][nc] = dist[r][c] + 1 — current cell-এর দূরত্ব + 1; প্রথম যে ঢেউ ছোঁয় সেটাই nearest।
• enqueue ঠিক set করার পাশে — mark-on-push, যাতে একই cell queue-তে বারবার না ঢোকে।

17. Output walkthrough

update_matrix(m2): সব 0 seed হয়; ঢেউ ছড়িয়ে (1,1) পায় 1, (2,0) ও (2,2) পায় 1, আর (2,1) পায় 2 → [[0,0,0],[0,1,0],[1,2,1]]। m3-এ একমাত্র 0 থেকে ছড়িয়ে [[2,1],[1,0]]। m1 সব 0/একা-1 → অপরিবর্তিত। সব assert pass, শেষে print: সব test pass!।

18. Time complexity

O(m · n) — initial scan সব cell একবার; BFS-এ প্রতিটা cell ঠিক একবার set ও একবার pop হয়, প্রতিটা প্রতিবেশী constant-বার দেখা হয়।

19. Space complexity

O(m · n) — dist matrix O(m·n), আর queue worst case একটা পুরো level (গ্রিড-আকারের) ধরে রাখতে পারে।

20. Common mistakes

• দিক উল্টো ধরা — 1 থেকে 0 খোঁজা; এতে multi-source-এর সুবিধাই হারায়, খরচ ফুলে যায়। সবসময় 0 থেকে ছড়াও।
• 0-cell গুলোকে আলাদা আলাদা seed না করে একটাই super-source ভেবে গোলমাল করা — সবগুলোকে distance 0-তে queue-তে ঢোকাও।
• visited চেক বাদ দিয়ে already-set cell আবার আপডেট করা — dist == -1 শর্তই প্রথম (nearest) মান রক্ষা করে।
• list.pop(0) ব্যবহার করা — প্রতি pop O(n), BFS quadratic; deque নাও।

21. Which basic problem this inherits from

ভিত্তি: multi-source BFS (#8 Rotting Oranges) আর BFS distance theorem (../bfs.md)। Rotting Oranges-এ উত্তর ছিল level সংখ্যা; এখানে উত্তর প্রতিটা cell-এর দূরত্ব — তাই সময় না গুনে cell-এ distance store করি। মূল নতুন শিক্ষা: কখনো BFS-এর দিক উল্টো চালাতে হয় (target থেকে, source থেকে নয়) — এটাই multi-source-এর সবচেয়ে শক্তিশালী চিন্তা।

22. Similar harder problems

• Rotting Oranges (multi-source, level = সময়) — https://leetcode.com/problems/rotting-oranges/ (এই tracker-এর #8)
• Walls and Gates (প্রতিটা ঘর থেকে nearest gate) — https://leetcode.com/problems/walls-and-gates/
• Map of Highest Peak (multi-source BFS height assignment) — https://leetcode.com/problems/map-of-highest-peak/

23. Pattern learned

Multi-source BFS for nearest-target distance: "প্রতিটা cell থেকে nearest X-এর দূরত্ব" = সব X একসাথে seed করে BFS, আর distance cell-এ store করো। চাবি হলো দিক উল্টো ধরা — target থেকে ছড়াও, প্রতিটা cell থেকে আলাদা খুঁজো না। সব edge cost সমান বলে heap লাগে না, খরচ O(m·n)।

24. Final summary

ভবিষ্যতের আমাকে: "01 Matrix = reverse multi-source BFS; সব 0 একসাথে seed করো, প্রতিটা 1 প্রথম যে ঢেউ ছোঁয় সেটাই উত্তর।" যখনই 'nearest X পর্যন্ত দূরত্ব প্রতিটা cell-এ' দেখবে — দিক উল্টে target থেকে ঢেউ ছড়াও; বহু BFS-এর ফাঁদ এড়িয়ে একটাই multi-source BFS চালাও।

---

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