028 — Longest Increasing Path in a Matrix

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

• Original source: Classic capstone interview problem (memoized DFS on an implicit DAG)
• Platform: LeetCode — https://leetcode.com/problems/longest-increasing-path-in-a-matrix/
• Topic: graphs + dynamic programming + recursion
• Difficulty: Hard
• Pattern: DP on an implicit DAG (memoized DFS, প্রতিটা cell থেকে দীর্ঘতম বাড়তি পথ)
• Basic idea inherited from: এটা একটা cross-topic capstone — এখানে মেশে 09 graphs (grid = implicit graph, cell-গুলো node), 12 dynamic programming (প্রতিটা cell-এর উত্তর cache করা), আর 06 recursion (DFS দিয়ে neighbour-এ নামা)। তিন tool মিলে O(m·n)।

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

তোমাকে একটা m × n integer matrix দেওয়া আছে। একটা cell থেকে তুমি চার দিকে (উপর, নিচ, বাঁ, ডান) যেতে পারো — শর্ত: পরের cell-এর মান কঠোরভাবে বড় হতে হবে। কোনো cell থেকে শুরু করে এমন একটা strictly increasing path-এর দৈর্ঘ্য (কতগুলো cell) সর্বোচ্চ কত হতে পারে, সেটা বের করো।

কোনো wrap-around নেই, diagonal চলা নেই। উত্তর হলো পুরো matrix জুড়ে সবচেয়ে লম্বা increasing path-এর cell-সংখ্যা।

উদাহরণ

matrix:
  9  9  4
  6  6  8
  2  1  1

দীর্ঘতম increasing path: 1 -> 2 -> 6 -> 9  (দৈর্ঘ্য 4)

Input ও output

উদাহরণ

Input : [[9,9,4],[6,6,8],[2,1,1]]   -> Output: 4   (1->2->6->9)
Input : [[3,4,5],[3,2,6],[2,2,1]]   -> Output: 4   (3->4->5->6)
Input : [[1]]                       -> Output: 1
Edge case (সব সমান): [[5,5],[5,5]]  -> 1   (strictly বাড়ে না, একটাই cell)

চেনা উদাহরণে বোঝা

ভাবো একটা পাহাড়ি অঞ্চলের উচ্চতা-মানচিত্র, প্রতিটা ঘর এক একটা জায়গার উচ্চতা। তুমি শুধু উপরের দিকে (উঁচু প্রতিবেশীতে) হাঁটতে পারো। প্রশ্ন: সবচেয়ে লম্বা একটানা চড়াই-পথ কত ঘর লম্বা?

যেহেতু সবসময় উঁচুতে উঠছ, কখনো একই জায়গায় ঘুরে ফিরে আসতে পারবে না (পানি যেমন নিচে গড়ায়, তুমি ঠিক উল্টো)। আর প্রতিটা জায়গা থেকে "এখান থেকে দীর্ঘতম চড়াই" একবার মেপে নোটবুকে টুকে রাখলে, পরে আবার এলে নতুন করে মাপতে হয় না — সেটাই memo।

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

এই problem তিনটা আগের ধারণা জোড়া দেয়:

• 09 graphs থেকে: matrix-কে একটা implicit directed graph ভাবা — প্রতিটা cell একটা node, আর u → v edge আছে যদি v পাশের cell আর value[v] > value[u]। "strictly increasing" শর্ত graph-টাকে DAG বানায় (cycle অসম্ভব)।
• 12 dynamic programming থেকে: প্রতিটা cell-এর "এখান থেকে দীর্ঘতম path" উত্তর একবার হিসাব করে cache করা — overlapping subproblem।
• 06 recursion থেকে: প্রতিটা cell থেকে neighbour-এ DFS নামা, child-দের উত্তর থেকে নিজের উত্তর গড়া।

একা graph দেয় node+edge ছবি; একা DP দেয় reuse; recursion দেয় descent। তিন মিলে O(m·n)।

ভেতরের যুক্তি

লুকানো logic একটা DAG-এর উপর recurrence: LIP(cell) = 1 + max(LIP(neighbour)) সব valid (strictly larger) neighbour-এর উপর; কোনো বড় neighbour না থাকলে LIP(cell) = 1।

যেহেতু path strictly increasing, কোনো cell দ্বিতীয়বার একই path-এ আসতে পারে না (cycle নেই — DAG)। তাই প্রতিটা cell-এর উত্তর তার বড় neighbour-দের উত্তরের উপর নির্ভর করে — একবার হিসাব করে cache করলেই চলে।

কী দিয়ে তথ্য রাখব

• একটা memo table (m × n, প্রতিটা cell-এর LIP cache) — DP-র heart।
• recursion stack (DFS)।
• ঐচ্ছিক: কোনো visited array লাগে না, কারণ strictly-increasing শর্তই cycle আটকায় — memo-ই যথেষ্ট।

এটি কেন উপযুক্ত

Brute DFS একই cell-এর উত্তর বহুবার গণনা করে (একই cell বহু path-এ আসে) — exponential। memo table (12 DP) প্রতিটা cell-কে একবারই solve করায়।

graph-lens (09) বলে দেয় কেন cycle নেই: strictly-increasing edge মানে DAG, তাই recursion (06) নিরাপদে depth-first নামতে পারে — কোনো infinite loop-এর ভয় ছাড়াই, এবং memo সঙ্গে থাকায় মোট কাজ O(node + edge) = O(m·n)।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

প্রথম সরল চিন্তা: প্রতিটা cell থেকে DFS চালিয়ে দীর্ঘতম increasing path মাপো, কোনো cache ছাড়া — শুধু "বড় neighbour-এ যাও" recursion।

উদাহরণ

def dfs(r, c):
    best = 1
    for each larger neighbour (nr, nc):
        best = max(best, 1 + dfs(nr, nc))
    return best
answer = max(dfs(r, c) over all cells)

কোথায় বেশি কাজ হচ্ছে

cache ছাড়া একই cell বহুবার পুনঃগণনা হয় — একটা cell বহু path-এর অংশ, তাই কাজ exponential (worst case)। কারণ overlapping subproblem-গুলো বারবার solve হচ্ছে — ঠিক যা DP (12) দূর করতে আসে। প্রতিটা cell-এর উত্তর একবার cache করলে মোট কাজ O(m·n)-এ নামে।

যে বিষয়টি খেয়াল করতে হবে

মূল observation: strictly-increasing শর্ত graph-টাকে DAG বানায় (cycle অসম্ভব), তাই প্রতিটা cell-এর "দীর্ঘতম increasing path" একটা সুসংজ্ঞায়িত, fixed মান — যেটা শুধু তার বড় neighbour-দের উত্তরের উপর নির্ভর করে। DAG হওয়ায় memoization নিরাপদ: কোনো cell-এর উত্তর তার নিজের উপর circularly নির্ভর করে না।

আরও কম কাজে সমাধান

প্রতিটা cell থেকে memoized DFS চালাও: LIP(r,c) = 1 + max(LIP(neighbour)) সব strictly-larger neighbour-এর উপর (না থাকলে 1)। উত্তর cache-এ থাকলে সরাসরি ফেরাও, নাহলে হিসাব করে cache-এ রাখো।

সব cell থেকে শুরু করে দেখো (কোনটা সবচেয়ে লম্বা path শুরু করে তা আগে জানা নেই), কিন্তু memo-র কারণে প্রতিটা cell মাত্র একবার সম্পূর্ণ solve হয় — মোট O(m·n)।

ভাবনার পরিবর্তন

মোচড়: "প্রতিটা path আলাদা করে খুঁজব" ভাবার বদলে ভাবো "প্রতিটা cell-এর উত্তর = 1 + তার সেরা বড়-প্রতিবেশীর উত্তর, আর সেটা একবারই হিসাব করব।" exponential path-search একটা O(m·n) DP-তে গুটিয়ে যায়।

ছবিতে বোঝা

[[9,9,4],[6,6,8],[2,1,1]]-এ প্রতিটা cell-এর LIP (এখান থেকে দীর্ঘতম increasing path):

উদাহরণ

matrix          LIP (cache)
 9  9  4         1  1  2
 6  6  8         2  2  1
 2  1  1         3  4  2

cell(2,1)=1 থেকে: 1 -> 2(নিচে নয়, পাশ) -> 6 -> 9
  LIP(9)=1, LIP(6)=2, LIP(2)=3, LIP(1)=4
  cell(2,2)=1 থেকে সরাসরি 8-এ গেলে length=2; ওই cell-এর cache তাই 2।

তীর সবসময় ছোট -> বড় (strictly), তাই কোনো cycle নেই (DAG)।
উত্তর = সব cell-এর LIP-এর max = 4

ছোট input-এ ধাপে ধাপে

[[1,2],[1,3]], cell (0,0)=1 থেকে DFS:

1. LIP(0,0): বড় neighbour — ডানে (0,1)=2, নিচে (1,0)=1 (1 বড় নয়, বাদ)।
2. LIP(0,1)=2: বড় neighbour — নিচে (1,1)=3। LIP(1,1)=3: কোনো বড় neighbour নেই → 1। তাই LIP(0,1) = 1 + 1 = 2।
3. ফিরে LIP(0,0) = 1 + max(LIP(0,1)=2) = 3 (path 1 -> 2 -> 3)।
4. বাকি cell-এর LIP ≤ 3। উত্তর = max = 3। ✓

কোড ও ব্যাখ্যা

Python

Python

import sys


def longest_increasing_path(matrix):
    """memoized DFS on an implicit DAG: grid = graph (09), cache = DP (12),
    DFS = recursion (06)। strictly-increasing edge -> DAG -> cycle নেই -> memo নিরাপদ।
    LIP(cell) = 1 + max(LIP(বড় neighbour)), না থাকলে 1। O(m·n)।"""
    if not matrix or not matrix[0]:
        return 0
    m, n = len(matrix), len(matrix[0])
    memo = [[0] * n for _ in range(m)]        # 0 = এখনো হিসাব হয়নি
    DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))

    def dfs(r, c):
        if memo[r][c]:                        # cache hit -> পুনরায় গণনা নয়
            return memo[r][c]
        best = 1                              # cell নিজেই দৈর্ঘ্য 1
        for dr, dc in DIRS:
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n and matrix[nr][nc] > matrix[r][c]:
                best = max(best, 1 + dfs(nr, nc))   # বড় neighbour-এ নামো
        memo[r][c] = best                     # cache-এ রাখো
        return best

    return max(dfs(r, c) for r in range(m) for c in range(n))


def brute(matrix):
    # obviously-correct reference: cache ছাড়া DFS (ছোট grid-এ ঠিক, ধীর)
    if not matrix or not matrix[0]:
        return 0
    m, n = len(matrix), len(matrix[0])
    DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))

    def dfs(r, c):
        best = 1
        for dr, dc in DIRS:
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n and matrix[nr][nc] > matrix[r][c]:
                best = max(best, 1 + dfs(nr, nc))
        return best

    return max(dfs(r, c) for r in range(m) for c in range(n))


# ---- tests ----
sys.setrecursionlimit(10000)

assert longest_increasing_path([[9, 9, 4], [6, 6, 8], [2, 1, 1]]) == 4
assert longest_increasing_path([[3, 4, 5], [3, 2, 6], [2, 2, 1]]) == 4
assert longest_increasing_path([[1]]) == 1
assert longest_increasing_path([[5, 5], [5, 5]]) == 1        # strictly বাড়ে না
assert longest_increasing_path([]) == 0                      # খালি
assert longest_increasing_path([[1, 2, 3, 4, 5]]) == 5       # এক সারি, সব বাড়ছে
assert longest_increasing_path([[5, 4, 3, 2, 1]]) == 5       # এক সারি, উল্টো দিকে

# random fuzz: memoized vs cache-less brute
import random
random.seed(28)
for _ in range(300):
    m = random.randint(1, 4)
    n = random.randint(1, 4)
    mat = [[random.randint(0, 6) for _ in range(n)] for _ in range(m)]
    assert longest_increasing_path(mat) == brute(mat), mat

print("সব test pass!")

কোডের প্রতিটি অংশ

• memo — m × n cache, 0 মানে "এখনো হিসাব হয়নি" (LIP সবসময় >= 1, তাই 0 sentinel নিরাপদ)।
• dfs(r, c) — cache hit হলে সরাসরি ফেরায়; নাহলে চার দিকের strictly বড় neighbour-এ নামে, 1 + max(...) নেয়, cache করে।
• matrix[nr][nc] > matrix[r][c] — শুধু কঠোরভাবে বড় neighbour-এ যাওয়া (DAG নিশ্চিত করে)।
• max(dfs(r,c) ...) — সব cell থেকে শুরু করে সবচেয়ে লম্বাটা; memo-র কারণে মোট কাজ O(m·n)।
• brute — cache ছাড়া একই DFS, ছোট grid-এ obviously-correct reference।

Output মিলিয়ে দেখা

[[9,9,4],[6,6,8],[2,1,1]]-এ দীর্ঘতম path 1->2->6->9 দৈর্ঘ্য 4; [[3,4,5],[3,2,6],[2,2,1]]-এও 4। একক cell, সব-সমান (1), খালি (0), আর এক-সারি increasing/decreasing (5) সব সঠিক। শেষে 300 random fuzz-এ memoized version cache-less brute-এর সাথে মেলে। শেষে print: সব test pass!।

খরচ ও সাধারণ ভুল

সময়

O(m·n) — memo-র কারণে প্রতিটা cell ঠিক একবার সম্পূর্ণ solve হয়, আর প্রতিটা cell-এ মাত্র 4টা neighbour দেখা; মোট কাজ node + edge = O(m·n)।

অতিরিক্ত জায়গা

O(m·n) — memo table + recursion stack (worst case একটা লম্বা increasing path-এ stack depth O(m·n))।

যে ভুলগুলো এড়াতে হবে

• > এর বদলে >= ব্যবহার করা — সমান cell-এ যাওয়া cycle তৈরি করে, infinite recursion; strictly বড় চাই।
• memo বাদ দিয়ে শুধু DFS — overlapping subproblem-এ exponential blow-up।
• visited array যোগ করা (লাগে না) — strictly-increasing শর্তই cycle আটকায়; visited অপ্রয়োজনীয় জটিলতা।
• শুধু এক cell থেকে শুরু করা — দীর্ঘতম path যেকোনো cell থেকে শুরু হতে পারে, সব cell try করতে হবে (memo সস্তা রাখে)।

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

ভিত্তি: grid-as-graph + DFS (09 graphs, ../../09-graphs/-এর flood-fill/DFS পরিবার, এই tracker-এর #8 Number of Islands-এর আত্মীয়) + memoization (12 DP, ../../12-dynamic-programming/) + recursion (06 recursion)। তিনটা cold-এ জানা থাকলে এই হার্ড সমাধান গড়ে ওঠে।

পরের অনুশীলন

• Number of Islands (grid DFS, ভিন্ন লক্ষ্য) — https://leetcode.com/problems/number-of-islands/ (এই tracker-এর #8)
• Out of Boundary Paths (grid DP + memo) — https://leetcode.com/problems/out-of-boundary-paths/
• Cherry Pickup II (grid DP, দুই agent) — https://leetcode.com/problems/cherry-pickup-ii/

কৌশলটি মনে রাখুন

DP on an implicit DAG (memoized DFS): grid-কে DAG ভেবে প্রতিটা cell থেকে 1 + max(বড় neighbour) recurrence একবার হিসাব করে cache করা। strictly-increasing শর্ত cycle আটকায়, তাই memo নিরাপদ। graphs + DP + recursion-এর canonical মেলবন্ধন।

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে: "grid + দীর্ঘতম increasing/monotonic path" দেখলেই memoized DFS on a DAG মনে করবে। LIP(cell) = 1 + max(strictly-বড় neighbour-দের LIP), না থাকলে 1; cache hit হলে সরাসরি ফেরাও। strictly-increasing মানেই DAG, তাই visited লাগে না — শুধু memo। সব cell থেকে শুরু করে max নাও, মোট O(m·n)।

---

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