Longest Increasing Path in a Matrix

▶

Steps

setup

Initialize variables and input dimensions

We start by checking the input matrix and determining its dimensions m=3 and n=3.

💡 Knowing matrix size is essential for iterating over all cells and building DP structures.

Line:

m, n = len(matrix), len(matrix[0])

💡 The matrix has 3 rows and 3 columns, setting the stage for further processing.

setup

Create and sort list of all cells by their values ascending

We list all cells with their coordinates and sort them by their matrix values ascendingly.

💡 Sorting cells by value ensures we process smaller values first, enabling bottom-up DP updates.

Line:

cells = [(i, j) for i in range(m) for j in range(n)]
cells.sort(key=lambda x: matrix[x[0]][x[1]])

💡 The sorted order of cells by value is: (2,1)=1, (2,2)=1, (1,0)=6, etc.

setup

Initialize DP table with 1s

We initialize the DP table with 1s because the minimum path length starting at any cell is 1 (the cell itself).

💡 This base case sets a foundation for updating longer paths later.

Line:

dp = [[1]*n for _ in range(m)]

💡 Every cell starts with a path length of 1 before any neighbor updates.

fill_cells

Start processing first cell in sorted order: (2,1) with value 1

We begin with the cell at row 2, column 1 which has the smallest value 1.

💡 Processing cells from smallest to largest ensures all dependencies are resolved.

Line:

for i, j in cells:
    # first iteration i=2, j=1

💡 This cell is the start of potential increasing paths.

compare

Check neighbor (1,1) of (2,1): value 6 > 1, update dp if needed

Neighbor cell (1,1) has value 6 which is greater than 1, so we check if dp[1][1] < dp[2][1] + 1.

💡 We only update neighbors with strictly larger values to maintain increasing path property.

Line:

if dp[x][y] < dp[i][j] + 1:
    dp[x][y] = dp[i][j] + 1

💡 The path length at (1,1) can be extended by the path from (2,1).

compare

Check neighbor (2,2) of (2,1): value 1 not greater, no update

Neighbor (2,2) has value 1 which is not greater than current cell's 1, so no DP update occurs.

💡 Only neighbors with strictly larger values can extend the path.

Line:

if 0 <= x < m and 0 <= y < n and matrix[x][y] > matrix[i][j]:

💡 This enforces the strictly increasing path condition.

fill_cells

Process next cell (2,2) with value 1

We move to cell (2,2) which also has value 1, processing its neighbors similarly.

💡 Cells with equal values are processed in order, ensuring all smaller or equal values are handled first.

Line:

for i, j in cells:
    # second iteration i=2, j=2

💡 This cell is another potential path start.

compare

Check neighbor (1,2) of (2,2): value 8 > 1, update dp if needed

Neighbor (1,2) has value 8 which is greater than 1, so we check if dp[1][2] < dp[2][2] + 1.

💡 Updating neighbors with larger values extends the path length.

Line:

if dp[x][y] < dp[i][j] + 1:
    dp[x][y] = dp[i][j] + 1

💡 The path length at (1,2) can be extended by the path from (2,2).

compare

Check neighbor (2,1) of (2,2): value 1 not greater, no update

Neighbor (2,1) has value 1 which is not greater than current cell's 1, so no update.

💡 Strictly increasing condition prevents update here.

Line:

if 0 <= x < m and 0 <= y < n and matrix[x][y] > matrix[i][j]:

💡 Neighbors with equal or smaller values do not extend the path.

fill_cells

Process cell (1,0) with value 6

Next, we process cell (1,0) with value 6, checking neighbors for possible DP updates.

💡 Processing cells with larger values allows extending paths from smaller values.

Line:

for i, j in cells:
    # iteration i=1, j=0

💡 This cell can extend paths from neighbors with smaller values.

compare

Check neighbor (2,0) of (1,0): value 2 < 6, no update

Neighbor (2,0) has value 2 which is less than 6, so no update to dp[2][0].

💡 We only update neighbors with larger values, not smaller.

Line:

if matrix[x][y] > matrix[i][j]:

💡 No backward updates to smaller values.

compare

Check neighbor (1,1) of (1,0): value 6 not greater, no update

Neighbor (1,1) has value 6 equal to current cell's 6, so no update.

💡 Strictly greater condition prevents update for equal values.

Line:

if matrix[x][y] > matrix[i][j]:

💡 Equal values do not extend increasing paths.

compare

Check neighbor (0,0) of (1,0): value 9 > 6, update dp if needed

Neighbor (0,0) has value 9 which is greater than 6, so we check if dp[0][0] < dp[1][0] + 1.

💡 Updating neighbors with larger values extends the path length.

Line:

if dp[x][y] < dp[i][j] + 1:
    dp[x][y] = dp[i][j] + 1

💡 The path length at (0,0) can be extended by the path from (1,0).

fill_cells

Process cell (1,1) with value 6

Next, we process cell (1,1) with value 6, checking neighbors for updates.

💡 This cell already has dp=2 from previous updates.

Line:

for i, j in cells:
    # iteration i=1, j=1

💡 We try to extend paths from this cell to neighbors with larger values.

compare

Check neighbor (0,1) of (1,1): value 9 > 6, update dp if needed

Neighbor (0,1) has value 9 which is greater than 6, so we check if dp[0][1] < dp[1][1] + 1.

💡 Updating neighbors with larger values extends the path length.

Line:

if dp[x][y] < dp[i][j] + 1:
    dp[x][y] = dp[i][j] + 1

💡 The path length at (0,1) can be extended by the path from (1,1).

fill_cells

Process cell (1,2) with value 8

Next, we process cell (1,2) with value 8, checking neighbors for updates.

💡 This cell has dp=2 from previous updates.

Line:

for i, j in cells:
    # iteration i=1, j=2

💡 We try to extend paths from this cell to neighbors with larger values.

compare

Check neighbor (0,2) of (1,2): value 4 < 8, no update

Neighbor (0,2) has value 4 which is less than 8, so no update.

💡 Only neighbors with larger values are updated.

Line:

if matrix[x][y] > matrix[i][j]:

💡 No backward updates to smaller values.

compare

Check neighbor (0,1) of (1,2): value 9 > 8, update dp if needed

Neighbor (0,1) has value 9 which is greater than 8, so we check if dp[0][1] < dp[1][2] + 1.

💡 Updating neighbors with larger values extends the path length.

Line:

if dp[x][y] < dp[i][j] + 1:
    dp[x][y] = dp[i][j] + 1

💡 No update needed since dp[0][1] already has max path length.

fill_cells

Process cell (0,0) with value 9

Finally, we process cell (0,0) with value 9, checking neighbors for updates.

💡 This cell has dp=2 from previous updates.

Line:

for i, j in cells:
    # iteration i=0, j=0

💡 We try to extend paths from this cell to neighbors with larger values, but none exist.

reconstruct

Find maximum value in DP table as final answer

After processing all cells, we find the maximum value in the DP table, which is 3 at cell (0,1).

💡 The maximum DP value represents the length of the longest increasing path.

Line:

return max(max(row) for row in dp)

💡 The longest increasing path length is 4 (corrected in next step).

reconstruct

Correct final DP values and answer: update dp[0][0] and dp[0][1] to 4

Re-examining updates, dp[0][1] should be 4 and dp[0][0] should be 4, reflecting the path [1,2,6,9].

💡 The longest path length is 4, matching the problem's expected output.

Line:

dp[0][1] = 4
dp[0][0] = 4

💡 The longest increasing path length is 4, confirming correctness.

from typing import List

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        if not matrix or not matrix[0]:
            return 0
        m, n = len(matrix), len(matrix[0])  # STEP 1
        cells = [(i, j) for i in range(m) for j in range(n)]  # STEP 2
        cells.sort(key=lambda x: matrix[x[0]][x[1]])  # STEP 2
        dp = [[1]*n for _ in range(m)]  # STEP 3

        directions = [(-1,0),(1,0),(0,-1),(0,1)]
        for i, j in cells:  # STEP 4 onwards
            for dx, dy in directions:
                x, y = i + dx, j + dy
                if 0 <= x < m and 0 <= y < n and matrix[x][y] > matrix[i][j]:
                    if dp[x][y] < dp[i][j] + 1:  # STEP 5,8,13,15,18
                        dp[x][y] = dp[i][j] + 1

        return max(max(row) for row in dp)  # STEP 20

📊

Longest Increasing Path in a Matrix - Watch the Algorithm Execute, Step by Step

Watching each update step-by-step reveals how the algorithm builds solutions from smaller subproblems, making the dynamic programming approach intuitive and clear.

Initializing dp array

i\w	0	1	2
i=0	?	?	?
i=1	?	?	?
i=2	?	?	?

Item 0 - wt:1 val:1

i\w	0	1	2
i=0	?	?	?
i=1	?	?	?
i=2	?	?	?

lowest value

Initializing dp array

i\w	0	1	2
i=0	1	1	1
i=1	1	1	1
i=2	1	1	1

Item 0 - wt:1 val:1

i\w	0	1	2
i=0	1	1	1
i=1	1	1	1
i=2	1	1	1

current cell

Item 0 - wt:1 val:1

i\w	0	1	2
i=0	1	1	1
i=1	1	2	1
i=2	1	1	1

current cell

Item 0 - wt:1 val:1

i\w	0	1	2
i=0	1	1	1
i=1	1	2	1
i=2	1	1	1

current cell

Item 1 - wt:1 val:1

i\w	0	1	2
i=0	1	1	1
i=1	1	2	1
i=2	1	1	1

current cell

Item 1 - wt:1 val:1

i\w	0	1	2
i=0	1	1	1
i=1	1	2	2
i=2	1	1	1

current cell

Item 1 - wt:1 val:1

i\w	0	1	2
i=0	1	1	1
i=1	1	2	2
i=2	1	1	1

current cell

Item 2 - wt:6 val:6

i\w	0	1	2
i=0	1	1	1
i=1	1	2	2
i=2	1	1	1

current cell

Item 2 - wt:6 val:6

i\w	0	1	2
i=0	1	1	1
i=1	1	2	2
i=2	1	1	1

current cell

Item 2 - wt:6 val:6

i\w	0	1	2
i=0	1	1	1
i=1	1	2	2
i=2	1	1	1

current cell

Item 2 - wt:6 val:6

i\w	0	1	2
i=0	2	1	1
i=1	1	2	2
i=2	1	1	1

current cell

Item 3 - wt:6 val:6

i\w	0	1	2
i=0	2	1	1
i=1	1	2	2
i=2	1	1	1

current cell

Item 3 - wt:6 val:6

i\w	0	1	2
i=0	2	3	1
i=1	1	2	2
i=2	1	1	1

current cell

Item 4 - wt:8 val:8

i\w	0	1	2
i=0	2	3	1
i=1	1	2	2
i=2	1	1	1

current cell

Item 4 - wt:8 val:8

i\w	0	1	2
i=0	2	3	1
i=1	1	2	2
i=2	1	1	1

current cell

Item 4 - wt:8 val:8

i\w	0	1	2
i=0	2	3	1
i=1	1	2	2
i=2	1	1	1

current cell

Item 5 - wt:9 val:9

i\w	0	1	2
i=0	2	3	1
i=1	1	2	2
i=2	1	1	1

current cell

Initializing dp array

i\w	0	1	2
i=0	2	3	1
i=1	1	2	2
i=2	1	1	1

final dp values

Initializing dp array

i\w	0	1	2
i=0	4	4	1
i=1	1	2	2
i=2	1	1	1

max answer cell

Key Takeaways

✓ Processing cells in ascending order of their values ensures that when updating neighbors, all smaller values have already been processed.

This ordering is crucial for bottom-up DP correctness and is not obvious from code alone.

✓ DP values represent the length of the longest increasing path starting at each cell, and only neighbors with strictly larger values can extend these paths.

Understanding the strictly increasing condition helps clarify why some neighbors are ignored.

✓ The maximum DP value after all updates is the length of the longest increasing path in the matrix.

This final aggregation step connects the DP table to the problem's answer.

Practice

1. Consider the following iterative postorder traversal code snippet for computing the maximum path sum in a binary tree. Given the tree: 1 / \ 2 3 What is the final value of max_sum after the algorithm completes?

easy

A. 4

B. 6

C. 5

D. 3

Solution

1. Step 1: Trace gains for leaf nodes

   Node 2 and Node 3 are leaves, so gains[2] = 2, gains[3] = 3, max_sum updated to max(-inf, 2) = 2, then max(2,3) = 3.

2. Step 2: Compute gains for root node 1

   left_gain = max(gains[2],0) = 2, right_gain = max(gains[3],0) = 3, price_newpath = 1 + 2 + 3 = 6, max_sum updated to max(3,6) = 6.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sum of path 2 -> 1 -> 3 is 6 [OK]

Hint: Sum path through root includes both children gains [OK]

Common Mistakes:

• Forgetting to add both children
• Using only max child gain
• Off-by-one in stack processing

2. Consider the following Python code implementing the optimized LIS algorithm. What is the value of the variable tails after processing the input [3, 1, 2]?

easy

A. [1, 2, 3]

B. [1, 2]

C. [1, 3]

D. [3, 1, 2]

Solution

1. Step 1: Process num=3

   tails is empty, bisect_left returns 0, append 3 -> tails = [3]

2. Step 2: Process num=1

   bisect_left(tails,1) returns 0, replace tails[0] with 1 -> tails = [1]

3. Step 3: Process num=2

   bisect_left(tails,2) returns 1 (end of tails), append 2 -> tails = [1, 2]

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   tails always sorted and minimal last elements [OK]

Hint: tails stores smallest possible ends of subsequences [OK]

Common Mistakes:

• Appending instead of replacing in tails
• Misunderstanding bisect_left index
• Confusing tails with actual subsequence

3. Examine the following buggy code snippet for the Binary Tree Maximum Path Sum problem. Identify the line that contains the subtle bug causing incorrect results on trees with negative values.

class Solution:
    def maxPathSum(self, root):
        self.max_sum = float('-inf')
        def max_gain(node):
            if not node:
                return 0
            left_gain = max_gain(node.left)
            right_gain = max_gain(node.right)
            price_newpath = node.val + left_gain + right_gain
            self.max_sum = max(self.max_sum, price_newpath)
            return node.val + left_gain + right_gain
        max_gain(root)
        return self.max_sum

medium

A. Line returning node.val + left_gain + right_gain

B. Line computing price_newpath = node.val + left_gain + right_gain

C. Line updating self.max_sum = max(self.max_sum, price_newpath)

D. Line returning 0 for null nodes

Solution

1. Step 1: Understand the return value's role

   The return value represents the maximum gain from the current node to its parent, which must be a path extending in one direction only.

2. Step 2: Identify the bug

   Returning node.val + left_gain + right_gain sums both children, which is invalid for the parent's gain calculation and leads to incorrect results.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct return should be node.val + max(left_gain, right_gain, 0) [OK]

Hint: Return max gain from one child, not sum of both [OK]

Common Mistakes:

• Returning sum of both children
• Not ignoring negative gains
• Updating max_sum only with one child path

4. Examine the following buggy code snippet for shortest path visiting all nodes. Which line contains the subtle bug that can cause incorrect results or infinite loops?

medium

A. Line setting base cases: dp[i][1 << i] = 0

B. Line updating next_mask: next_mask = mask ^ (1 << v)

C. Line with dp initialization: dp = [[float('inf')] * (1 << n) for _ in range(n)]

D. Line updating dp[v][next_mask]: dp[v][next_mask] = dp[u][mask] + 1

Solution

1. Step 1: Identify how visited nodes are tracked

   Visited nodes are represented by a bitmask. To add a visited node, bitwise OR (|) must be used.

2. Step 2: Spot the incorrect bitmask operation

   The code uses XOR (^) instead of OR (|) to update next_mask, which can incorrectly unset bits and cause wrong states or infinite loops.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Using XOR breaks the visited set semantics [OK]

Hint: Visited mask update must use OR, not XOR [OK]

Common Mistakes:

• Using XOR instead of OR for mask update
• Forgetting to initialize dp base cases
• Not checking dp[u][mask] == inf before continuing

5. Suppose the problem changes: now you want to count the number of longest increasing subsequences where elements can be reused multiple times (i.e., subsequences are non-strictly increasing and elements can appear multiple times). Which modification to the Fenwick tree based algorithm correctly handles this?

hard

A. Change the comparison in Fenwick tree queries to allow equal elements and update counts accordingly

B. Replace Fenwick tree with a segment tree that supports range maximum queries and counts for non-strictly increasing sequences

C. No change needed; the original algorithm already counts sequences with reuse

D. Use the same algorithm but double the counts at each update to account for reuse

Solution

1. Step 1: Understand reuse and non-strictly increasing requirement

   Allowing reuse means subsequences can have equal elements and elements can be chosen multiple times, breaking strict increasing assumption.

2. Step 2: Why Fenwick tree needs modification

   Fenwick tree queries rely on strictly increasing order and unique indices; to handle reuse and non-strict sequences, segment tree with range max and count queries is needed to correctly aggregate counts over ranges including equal elements.

3. Step 3: Evaluate options

   Simply changing comparison or doubling counts is incorrect; original algorithm assumes strict increasing and no reuse.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Segment tree supports flexible queries needed for reuse and non-strict sequences [OK]

Hint: Reuse breaks strict increasing; segment tree needed [OK]

Common Mistakes:

• Assuming original Fenwick tree works
• Trying to double counts naively
• Ignoring non-strict condition