Longest Increasing Path in a Matrix

To solve the problem of finding the longest increasing path in a given matrix, you can use a Depth First Search (DFS) algorithm. The DFS will be utilized to explore all possible increasing paths from each cell in the matrix.

Here’s how you can approach the problem:

  1. Initialize a Cache: Use a 2D array (same size as the input matrix) to store the length of the longest increasing path starting from each cell. This helps to avoid redundant computations.

  2. Depth First Search: For each cell, perform a DFS to find the length of the longest increasing path starting from that cell.

  3. Directional Movements: You can define the directions (left, right, up, down) using an array of deltas.

  4. Boundary and Increasing Check: While performing the DFS, check if the next cell is within the boundary of the matrix and if the value in the next cell is greater than the current cell.

  5. Update the Cache: Use the cache to store the result of the DFS, so that if the same cell is visited again, the result can be retrieved from the cache.

Here’s the code implementing the above approach:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        if not matrix:
            return 0

        m, n = len(matrix), len(matrix[0])
        cache = [[-1] * n for _ in range(m)]
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

        def dfs(x, y):
            if cache[x][y] != -1:
                return cache[x][y]

            length = 1
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and matrix[nx][ny] > matrix[x][y]:
                    length = max(length, 1 + dfs(nx, ny))

            cache[x][y] = length
            return length

        return max(dfs(x, y) for x in range(m) for y in range(n))

Key Takeaways

  • The cache helps in reducing the time complexity by avoiding redundant computations.
  • The time complexity of the solution is (O(m \times n)), where (m) and (n) are the dimensions of the matrix.
  • The space complexity is also (O(m \times n)) due to the cache and the recursion stack.
  • The DFS explores all possible increasing paths from each cell, respecting the given movement constraints.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

from typing import List

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        if not matrix:
            return 0

        rows, cols = len(matrix), len(matrix[0])
        # memoization to store the longest path starting from (i, j)
        cache = [[-1 for _ in range(cols)] for _ in range(rows)]

        def dfs(i, j):
            # If the result for this cell is already computed, return it
            if cache[i][j] != -1:
                return cache[i][j]

            # Directions: up, down, left, right
            directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
            max_length = 1
            for di, dj in directions:
                ni, nj = i + di, j + dj
                # Check if the next cell is within bounds and has a greater value
                if 0 <= ni < rows and 0 <= nj < cols and matrix[ni][nj] > matrix[i][j]:
                    length = 1 + dfs(ni, nj)
                    max_length = max(max_length, length)

            # Store the result in cache
            cache[i][j] = max_length
            return max_length

        # Perform DFS from each cell to find the maximum path length
        result = 0
        for i in range(rows):
            for j in range(cols):
                result = max(result, dfs(i, j))

        return result

Identifying Problem Isomorphism

“Longest Increasing Path in a Matrix” can be approximately mapped to “Increasing Triplet Subsequence”.

In “Longest Increasing Path in a Matrix”, you are asked to find the length of the longest increasing path in a 2D matrix, where each move must go to a cell adjacent to the current cell (including diagonally) and the values in the cells must be strictly increasing.

In “Increasing Triplet Subsequence”, you are tasked to find if there exists a triplet of indices (i, j, k) in a 1D array such that i < j < k and array[i] < array[j] < array[k].

Although the problems are not exactly the same, they share a fundamental trait: both require you to find an increasing sequence in a set of numbers. The difference lies in the dimensions of the input - the former is a 2D problem, while the latter is a 1D problem. The requirement of the increasing sequence in the 2D matrix is more complex as it requires traversal through more possibilities (up, down, left, right, and diagonally). In contrast, the “Increasing Triplet Subsequence” problem is simpler as it only involves linear traversal of an array.

“Longest Increasing Path in a Matrix” is more complex as it involves dynamic programming and careful handling of boundary conditions, while “Increasing Triplet Subsequence” is simpler, requiring only one pass through the array to solve.

10 Prerequisite LeetCode Problems

“Longest Increasing Path in a Matrix” involves the application of depth-first search and dynamic programming. Here are 10 problems to prepare:

  1. “Flood Fill” (LeetCode Problem #733): This problem is a simpler version of depth-first search on a grid, which is a fundamental concept in “Longest Increasing Path in a Matrix”.

  2. “Number of Islands” (LeetCode Problem #200): This problem requires a similar depth-first search on a grid, but with a different goal.

  3. “Path Sum” (LeetCode Problem #112): This problem introduces the concept of searching for paths in a structure.

  4. “Climbing Stairs” (LeetCode Problem #70): This problem introduces a simple dynamic programming concept, which is essential for the problem.

  5. “Best Time to Buy and Sell Stock” (LeetCode Problem #121): This problem also involves dynamic programming, but in a different context.

  6. “House Robber” (LeetCode Problem #198): Another simple dynamic programming problem that deals with maximizing a quantity.

  7. “Unique Paths” (LeetCode Problem #62): This problem introduces the concept of finding paths in a grid, a simpler version of the problem.

  8. “Longest Continuous Increasing Subsequence” (LeetCode Problem #674): This problem will help you understand how to find increasing sequences, which is crucial for the main problem.

  9. “Max Area of Island” (LeetCode Problem #695): This problem also requires depth-first search on a grid, and can provide practice in working with 2D arrays.

  10. “Longest Increasing Subsequence” (LeetCode Problem #300): This problem involves finding an increasing subsequence, but in a 1D array instead of a 2D one.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        if not matrix or not matrix[0]:
            return 0
        rows, cols = len(matrix), len(matrix[0])
        dp =[[0] * cols for i in range(rows)]
        def dfs(i, j):
            if not dp[i][j]:
                val = matrix[i][j]
                dp[i][j] = 1 + max(
                    dfs(i - 1, j) if i and val > matrix[i - 1][j] else 0,
                    dfs(i + 1, j) if i < rows - 1 and val > matrix[i + 1][j] else 0,
                    dfs(i, j - 1) if j and val > matrix[i][j - 1] else 0,
                    dfs(i, j + 1) if j < cols - 1 and val > matrix[i][j + 1] else 0)
            return dp[i][j]
        
        for r in range(rows):
            for c in range(cols):
                dfs(r,c)
        return max(max(x) for x in dp)

Problem Classification

Longest Increasing Path in a Matrix - The problem asks to find the longest increasing path in a matrix. This is a Path Finding Problem.

Language Agnostic Coding Drills

The code is solving the problem of finding the longest increasing path in a matrix. Here are the drills in an increasing level of difficulty:

  1. Arrays and Matrices: Understanding how to define, access, and manipulate arrays and matrices is fundamental. Practice initializing a 2D array (matrix), accessing elements, and updating them.

  2. Depth-First Search (DFS): This is a classic algorithm that is extensively used in problems involving graphs and matrices. DFS starts from a root node (or a selected start node) and explores as far as possible along each branch before backtracking. Practice implementing a DFS that traverses a simple graph or tree.

  3. Understanding and using dynamic programming (DP): The core idea behind dynamic programming is to break down a complex problem into simpler sub-problems, and store the result of these sub-problems so that when their solutions are needed again, they can be looked up instead of being re-computed (hence, saving computational time). Practice dynamic programming problems to get comfortable with this concept.

  4. Implementing memoization: This is a specific technique used in dynamic programming where the results of expensive function calls are cached and reused when the same inputs occur again. Implement a simple function that uses memoization.

  5. Conditional Execution and Ternary Operations: Understand how to use if-else conditions to control the flow of your program. Also, get familiar with ternary operations in Python, which allow you to quickly test a condition instead of a full multi-line if-else statement.

  6. Working with a DFS in a Matrix and Edge Conditions: Apply your knowledge of DFS to traverse a matrix instead of a graph or a tree. Be aware of edge conditions, and how to handle them (like ensuring your DFS doesn’t go outside of the matrix boundaries).

  7. Applying DFS and DP Together: Practice problems that require both DFS and DP.

The problem-solving approach here involves applying DFS on each cell in the input matrix. For each cell, we calculate the length of the longest path that can be achieved starting from this cell by using DFS, and we store this value in our DP table (the same size as the input matrix). The value at any cell in the DP table is calculated as one plus the maximum of the values for all valid neighboring cells. We only calculate this value if it hasn’t been calculated before, which is checked by looking up the DP table. This is where memoization comes into play. After filling up our DP table, the answer to the problem is the maximum value in this table.

Targeted Drills in Python

  1. Arrays and Matrices

    1
2
3
4
5

    rows, cols = 5, 4  # define number of rows and columns
matrix = [[0 for _ in range(cols)] for _ in range(rows)]  # initializing a 2D array
print(matrix)  # print the 2D array
matrix[0][0] = 1  # set an element
print(matrix[0][0])  # access an element

  2. Depth-First Search (DFS)

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

    def dfs(graph, start):
    visited = []
    stack = [start]

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.append(node)
            stack.extend(graph[node] - set(visited))
    return visited

graph = {1: set([2, 3]), 2: set([1, 4, 5]), 3: set([1]), 4: set([2]), 5: set([2])}
print(dfs(graph, 1))  # prints [1, 3, 2, 5, 4]

  3. Understanding and using dynamic programming (DP)

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

    # This simple example calculates fibonacci numbers using DP
def fibonacci(n, dp):
    if n <= 1:
        return n
    if dp[n] != 0:
        return dp[n]
    dp[n] = fibonacci(n-1, dp) + fibonacci(n-2, dp)
    return dp[n]

n = 10
dp = [0] * (n+1)
print(fibonacci(n, dp))  # prints 55

  4. Implementing memoization

    1
2
3
4
5
6
7
8
9

    # The Fibonacci function can be modified to include memoization as follows:
def fibonacci(n, memo = {}):
    if n <= 1:
        return n
    elif n not in memo:
        memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
    return memo[n]

print(fibonacci(10))  # prints 55

  5. Conditional Execution and Ternary Operations

    1
2
3

    a = 5
b = 10
print("a is less than b") if a < b else print("a is greater than or equal to b")  # prints "a is less than b"

  6. Working with a DFS in a Matrix and Edge Conditions

    1
2
3
4
5
6
7
8
9

    # A DFS in a matrix is very similar to a DFS in a graph. For simplicity, let's define a function that returns the neighbors of a cell in a matrix
def get_neighbors(matrix, row, col):
    neighbors = []
    rows, cols = len(matrix), len(matrix[0])
    for r in range(max(0, row - 1), min(rows, row + 2)):
        for c in range(max(0, col - 1), min(cols, col + 2)):
            if (r, c) != (row, col):
                neighbors.append((r, c))
    return neighbors

  7. Applying DFS and DP Together

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

    # Here is a simple example of applying DFS and DP together to find the longest increasing path in a matrix
def longest_increasing_path(matrix):
    if not matrix: return 0
    rows, cols = len(matrix),len(matrix[0])
    cache = [[-1]*cols for _ in range(rows)]

    def dfs(row, col):
        if cache[row][col] != -1:
            return cache[row][col]
        val = matrix[row][col]
        cache[row][col] = 1 + max(
            dfs(r, c) for r, c in [(row-1, col), (row+1, col), (row, col-1), (row, col+1)]
            if 0 <= r < rows and 0 <= c < cols and val > matrix[r][c]
        )
        return cache[row][col]

    return max(dfs(row, col) for row in range(rows) for col in range(cols))