We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Longest Increasing Path in a Matrix

Difficulty: Hard

Problem Description

Given an m x n integers matrix, return the length of the longest increasing path in 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).

Key Insights

  • The problem can be approached using Depth-First Search (DFS) combined with Memoization to avoid recalculating paths from the same cell.
  • Each cell's value determines the valid moves to neighboring cells.
  • To find the longest increasing path, we need to explore all possibilities recursively while keeping track of the maximum length found.
  • Using a memoization table allows us to store the lengths of increasing paths from previously computed cells, enhancing efficiency.

Space and Time Complexity

Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the matrix. Each cell is processed once. Space Complexity: O(m * n) for the memoization table.

Solution

To solve this problem, we can utilize a combination of Depth-First Search (DFS) and Memoization. The algorithm works by recursively exploring all four possible directions from each cell, checking if the next cell has a greater value (to maintain the increasing path condition). We cache the results of previously computed paths to reduce redundant calculations.

  1. Iterate over each cell in the matrix.
  2. For each cell, initiate a DFS search to find the longest path starting from that cell.
  3. Use a memoization table to store the lengths of paths already computed for each cell.
  4. Return the maximum length found across all cells.

Code Solutions

def longestIncreasingPath(matrix):
    if not matrix or not matrix[0]:
        return 0
    
    m, n = len(matrix), len(matrix[0])
    memo = [[-1] * n for _ in range(m)]

    def dfs(x, y):
        if memo[x][y] != -1:
            return memo[x][y]
        
        max_length = 1  # At least the cell itself
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # right, down, left, up
        
        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]:
                max_length = max(max_length, 1 + dfs(nx, ny))
        
        memo[x][y] = max_length
        return max_length

    longest_path = 0
    for i in range(m):
        for j in range(n):
            longest_path = max(longest_path, dfs(i, j))
    
    return longest_path
← Back to All Questions