How to Solve Longest Increasing Path in a Matrix

Written By
Adam Bhula

Longest Increasing Path in a Matrix Introduction

The Longest Increasing Path in a Matrix problem asks us to as the name would suggest, return the length of the longest increasing path given an m x n matrix. The limitations are that we can only move up, down, left, or right not diagonally, and going outside of bounds (wrap-around) is also not permitted. The challenge in this problem is using memoization to store the results of the subproblems (the lengths) to avoid redundant calculations.

Longest Increasing Path in a Matrix Problem

Given an m x n integers matrix, return the length of the longest increasing path in the matrix.

From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed).

Example Inputs and Outputs

Example 1

Input: Matrix = [ [9, 9, 4], [6, 6, 8], [2, 1, 1] ]
Output: 4

Example 2

Input: Matrix = [ [3, 4, 5], [3, 2, 6], [2, 2, 1] ]
Output: 4

Longest Increasing Path in a Matrix Solutions

To tackle this problem, we can use a dynamic programming approach with memoization. To find the longest increasing path, we start by initializing a table called "memo" to keep track of the lengths of the longest increasing paths starting from each cell in the matrix. We then iterate over each cell in the matrix and perform a depth-first search (DFS).

During the DFS, we explore the neighboring cells and recursively calculate the length of the increasing path if the neighboring cell has a greater value. We store the lengths of these paths in the memo table to avoid redundant calculations. This way, when we encounter a cell that we have visited before, we can simply retrieve the precalculated length from the memo table instead of recomputing it.

After performing the DFS for all cells, we find the maximum length of the increasing path in the memo table. This maximum length represents the longest increasing path in the matrix. By using memoization and avoiding redundant calculations, this DP approach solves the problem more efficiently with a better runtime than a naive approach that explores all possible paths.

def longestIncreasingPath(matrix):
    # Check if input matrix is empty
    if not matrix:
        return 0

    rows, cols = len(matrix), len(matrix[0]) # calculate number of rows and columns
    memo = [[0] * cols for _ in range(rows)] # create memo table
    maxPath = 0

    def dfs(row, col):
        # If the result for this cell has already been calculated, return it
        if memo[row][col] != 0:
            return memo[row][col]

        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]  # Possible directions: right, left, down, up
        maxLen = 1

        for dx, dy in directions:
            newRow, newCol = row + dx, col + dy
            # Check if the new cell is within the matrix boundaries and has a higher value
            if 0 <= newRow < rows and 0 <= newCol < cols and matrix[newRow][newCol] > matrix[row][col]:
                maxLen = max(maxLen, 1 + dfs(newRow, newCol))  # Recursively explore the new cell

        memo[row][col] = maxLen  # Cache the result for this cell
        return maxLen

    for row in range(rows):
        for col in range(cols):
            maxPath = max(maxPath, dfs(row, col))  # Explore each cell and update the maximum path length

    return maxPath

# Driver code
matrix1 = [
    [9, 9, 4],
    [6, 6, 8],
    [2, 1, 1]
print(longestIncreasingPath(matrix1))  # Output: 4

matrix2 = [
    [3, 4, 5],
    [3, 2, 6],
    [2, 2, 1]
print(longestIncreasingPath(matrix2))  # Output: 4

Time/Space Complexity Analysis

  • Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the matrix. This is because we traverse each cell in the matrix exactly once during the DFS process.
  • Space Complexity: O(m * n), this is because we use a memoization table of the same size to store the previously calculated results. Additionally, the recursion stack during the DFS process can go up to the maximum depth of the matrix, which is O(m * n) in the worst case scenario. Therefore, the overall space complexity is dominated by the memoization table and the recursion stack.

About interviewing.io

interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.

We know exactly what to do and say to get the company, title, and salary you want.

Interview prep and job hunting are chaos and pain. We can help. Really.