Longest Increasing Path in a Matrix - Practice Coding Problems

Longest Increasing Path in a Matrix - Problem

Array Dynamic Programming Depth-First Search Breadth-First Search Graph Topological Sort Memoization Matrix Hard

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

From each cell, you can move in four directions: left, right, up, or down. You cannot move diagonally or outside the boundary.

Input & Output

Example 1 — Basic 3x3 Matrix

$ Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]

› Output: 4

💡 Note: The longest increasing path is 1→6→8→9 with length 4. We can start from (2,1) with value 1, move to (1,0) with value 6, then to (1,2) with value 8, then to (0,0) or (0,1) with value 9.

Example 2 — Simple 2x2 Matrix

$ Input: matrix = [[3,4],[5,2]]

› Output: 3

💡 Note: The longest increasing path is 2→3→4 with length 3. Start from (1,1) with value 2, move to (0,0) with value 3, then to (0,1) with value 4.

Example 3 — Single Cell

$ Input: matrix = [[1]]

› Output: 1

💡 Note: Only one cell exists, so the longest path has length 1.

Constraints

m == matrix.length
n == matrix[i].length
1 ≤ m, n ≤ 200
0 ≤ matrix[i][j] ≤ 2³¹ - 1

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

2D matrix with integer values

Explore Paths

From each cell, move in 4 directions to find increasing paths

Return Maximum

Length of the longest increasing path found

Key Takeaway

🎯 Key Insight: Use memoization to cache DFS results and avoid recalculating the same subproblems

Asked in

G Google 45 f Facebook 38 a Amazon 32 M Microsoft 28

The key insight is to use memoization to avoid recalculating the longest path from the same cell multiple times. The optimal approach uses DFS with memoization, achieving O(m×n) time and O(m×n) space complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force DFS	O(2^(m×n))	O(m×n)	Try all possible paths from every cell using recursive DFS
DFS with Memoization	O(m×n)	O(m×n)	Cache DFS results to avoid recalculating the same subproblems

Brute Force DFS — Algorithm Steps

Start DFS from every cell in the matrix
For each cell, explore all 4 directions recursively
Return the maximum path length found

Visualization

Tap to expand

Step-by-Step Walkthrough

Start from each cell

Try DFS from every position

Explore 4 directions

Recursively check all valid increasing moves

Track maximum

Keep the longest path found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int directions[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

int dfs(int** matrix, int i, int j, int m, int n) {
    int maxLength = 1;
    for (int k = 0; k < 4; k++) {
        int ni = i + directions[k][0];
        int nj = j + directions[k][1];
        if (ni >= 0 && ni < m && nj >= 0 && nj < n && matrix[ni][nj] > matrix[i][j]) {
            int length = 1 + dfs(matrix, ni, nj, m, n);
            if (length > maxLength) maxLength = length;
        }
    }
    return maxLength;
}

int solution(int** matrix, int m, int n) {
    if (m == 0 || n == 0) return 0;
    
    int result = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int length = dfs(matrix, i, j, m, n);
            if (length > result) result = length;
        }
    }
    
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for small test cases
    int** matrix = (int**)malloc(10 * sizeof(int*));
    for (int i = 0; i < 10; i++) {
        matrix[i] = (int*)malloc(10 * sizeof(int));
    }
    
    // For demonstration, handle simple case [[9,9,4],[6,6,8],[2,1,1]]
    int m = 3, n = 3;
    int testMatrix[3][3] = {{9,9,4},{6,6,8},{2,1,1}};
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            matrix[i][j] = testMatrix[i][j];
        }
    }
    
    printf("%d\n", solution(matrix, m, n));
    
    for (int i = 0; i < 10; i++) {
        free(matrix[i]);
    }
    free(matrix);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^(m×n))

Each cell can explore 4 directions recursively, leading to exponential branching

✓ Linear Growth

Space Complexity

O(m×n)

Recursion stack can go as deep as m×n in worst case

⚡ Linearithmic Space

78.4K Views

Medium Frequency

~25 min Avg. Time

2.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force DFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler