Longest Increasing Path in a Matrix

🎯

Longest Increasing Path in a Matrix

hardDPAmazonGoogleFacebook

Imagine navigating a mountainous terrain represented as a grid, where you want to find the longest path climbing strictly upwards in elevation without backtracking.

💡 This problem is about finding the longest strictly increasing path in a 2D grid. Beginners often struggle because it looks like a graph problem but is presented as a matrix, and naive DFS leads to exponential time due to repeated states. Understanding how to cache results and use DP on a grid modeled as a DAG is key.

📋

Problem Statement

Given an m x n integer matrix, return the length of the longest strictly increasing path in the matrix. From each cell, you can move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary of the matrix.

m == matrix.lengthn == matrix[i].length1 ≤ m, n ≤ 2000 ≤ matrix[i][j] ≤ 2^31 - 1

💡

Example

Input"[[9,9,4],[6,6,8],[2,1,1]]"

Output4

The longest increasing path is [1, 2, 6, 9].

Input"[[3,4,5],[3,2,6],[2,2,1]]"

Output4

The longest increasing path is [3, 4, 5, 6].

• Matrix with all equal elements → output 1
• Matrix with strictly decreasing rows → output 1
• Single cell matrix → output 1
• Matrix with multiple increasing paths of same length → output correct max length

🔁

Why DP?

Why greedy fails:

A greedy approach that always picks the next largest neighbor fails because it might get stuck in a local maximum and miss longer paths starting elsewhere. For example, choosing a neighbor with a slightly larger value might prevent exploring a longer path that requires a smaller immediate step.

DP state:

dp[i][j] represents the length of the longest strictly increasing path starting from cell (i, j).

Recurrence:dp[i][j] = 1 + max(dp[x][y]) for all neighbors (x,y) where matrix[x][y] > matrix[i][j]

The longest path from (i,j) is 1 plus the longest path from any neighbor with a strictly larger value.

⚠️

Common Mistakes

Not memoizing DFS results

Exponential time leading to TLE

✅ Add dp cache to store computed longest paths

Allowing moves to neighbors with equal or smaller values

Incorrect path length, possibly infinite loops

✅ Ensure moves only to strictly larger neighbors

Not checking matrix boundaries before accessing neighbors

Runtime errors or crashes

✅ Add boundary checks before neighbor access

Using global variables without resetting between test cases

Wrong answers on multiple test runs

✅ Initialize dp and variables inside function scope

🧠

Brute Force (Pure DFS without Memoization)

💡 This approach is the foundation to understand the problem. It explores all paths from every cell but is inefficient due to repeated computations.

Intuition

From each cell, recursively explore all four directions to find strictly increasing neighbors and compute the longest path by trying all possibilities.

Algorithm

1. For each cell in the matrix, start a DFS to find the longest increasing path starting there.
2. In DFS, move to neighbors with strictly larger values.
3. Recursively compute the longest path from neighbors and take the maximum.
4. Return the maximum length found among all cells.

💡 The recursion explores all paths but does not remember results, causing repeated work and exponential time.

Recurrence:dp[i][j] = 1 + max(dp[x][y]) for neighbors (x,y) with matrix[x][y] > matrix[i][j]

</>

Code

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])

        def dfs(i, j):
            max_len = 1
            for x, y in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
                if 0 <= x < m and 0 <= y < n and matrix[x][y] > matrix[i][j]:
                    length = 1 + dfs(x, y)
                    if length > max_len:
                        max_len = length
            return max_len

        result = 0
        for i in range(m):
            for j in range(n):
                path_len = dfs(i, j)
                if path_len > result:
                    result = path_len
        return result

# Example usage:
# sol = Solution()
# print(sol.longestIncreasingPath([[9,9,4],[6,6,8],[2,1,1]]))  # Output: 4

Line Notes

def dfs(i, j):Defines recursive DFS to explore paths from cell (i,j)

for x, y in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:Iterate over all four neighbors

if 0 <= x < m and 0 <= y < n and matrix[x][y] > matrix[i][j]:Check bounds and strictly increasing condition

length = 1 + dfs(x, y)Recursively compute path length from neighbor

for i in range(m):Outer loop to start DFS from every cell

for j in range(n):Inner loop to cover all columns

path_len = dfs(i, j)Compute longest path starting at (i,j)

if path_len > result:Update global maximum path length

import java.util.*;

public class Solution {
    private int m, n;
    private int[][] matrix;

    public int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        this.matrix = matrix;
        m = matrix.length;
        n = matrix[0].length;
        int result = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int len = dfs(i, j);
                if (len > result) result = len;
            }
        }
        return result;
    }

    private int dfs(int i, int j) {
        int maxLen = 1;
        int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
        for (int[] d : dirs) {
            int x = i + d[0], y = j + d[1];
            if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]) {
                int len = 1 + dfs(x, y);
                if (len > maxLen) maxLen = len;
            }
        }
        return maxLen;
    }

    // Example usage:
    // public static void main(String[] args) {
    //     Solution sol = new Solution();
    //     int[][] matrix = {{9,9,4},{6,6,8},{2,1,1}};
    //     System.out.println(sol.longestIncreasingPath(matrix)); // Output: 4
    // }
}

Line Notes

private int dfs(int i, int j)Recursive DFS to find longest path from (i,j)

for (int[] d : dirs)Iterate over four possible directions

if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j])Check bounds and increasing condition

int len = 1 + dfs(x, y);Compute path length from neighbor

for (int i = 0; i < m; i++)Start DFS from every cell row-wise

for (int j = 0; j < n; j++)Start DFS from every cell column-wise

if (len > result) result = len;Update global max path length

return maxLen;Return longest path from current cell

#include <vector>
#include <iostream>
using namespace std;

class Solution {
    int m, n;
    vector<vector<int>> matrix;
public:
    int longestIncreasingPath(vector<vector<int>>& mat) {
        if (mat.empty() || mat[0].empty()) return 0;
        matrix = mat;
        m = matrix.size();
        n = matrix[0].size();
        int result = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int len = dfs(i, j);
                if (len > result) result = len;
            }
        }
        return result;
    }

private:
    int dfs(int i, int j) {
        int maxLen = 1;
        int dirs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
        for (auto& d : dirs) {
            int x = i + d[0], y = j + d[1];
            if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]) {
                int len = 1 + dfs(x, y);
                if (len > maxLen) maxLen = len;
            }
        }
        return maxLen;
    }
};

// Example usage:
// int main() {
//     Solution sol;
//     vector<vector<int>> matrix = {{9,9,4},{6,6,8},{2,1,1}};
//     cout << sol.longestIncreasingPath(matrix) << endl; // Output: 4
//     return 0;
// }

Line Notes

int dfs(int i, int j)DFS function to compute longest path from (i,j)

for (auto& d : dirs)Loop over four directions

if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j])Check valid move and increasing condition

int len = 1 + dfs(x, y);Calculate path length from neighbor

for (int i = 0; i < m; i++)Start DFS from each row

for (int j = 0; j < n; j++)Start DFS from each column

if (len > result) result = len;Update max path length found

return maxLen;Return longest path length from current cell

var longestIncreasingPath = function(matrix) {
    if (!matrix || matrix.length === 0 || matrix[0].length === 0) return 0;
    const m = matrix.length, n = matrix[0].length;

    function dfs(i, j) {
        let maxLen = 1;
        const directions = [[-1,0],[1,0],[0,-1],[0,1]];
        for (const [dx, dy] of directions) {
            const x = i + dx, y = j + dy;
            if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]) {
                const len = 1 + dfs(x, y);
                if (len > maxLen) maxLen = len;
            }
        }
        return maxLen;
    }

    let result = 0;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            const pathLen = dfs(i, j);
            if (pathLen > result) result = pathLen;
        }
    }
    return result;
};

// Example usage:
// console.log(longestIncreasingPath([[9,9,4],[6,6,8],[2,1,1]])); // Output: 4

Line Notes

function dfs(i, j)Recursive DFS to find longest path from cell (i,j)

for (const [dx, dy] of directions)Iterate over four possible moves

if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j])Check bounds and increasing condition

const len = 1 + dfs(x, y);Calculate path length from neighbor

for (let i = 0; i < m; i++)Start DFS from each row

for (let j = 0; j < n; j++)Start DFS from each column

if (pathLen > result) result = pathLen;Update global max path length

return maxLen;Return longest path length from current cell

⏱

Complexity

TimeO(m * n * 4^(m*n))

SpaceO(m * n) recursion stack in worst case

Each cell explores up to 4 neighbors recursively without caching, leading to exponential calls.

💡 For a 10x10 matrix, this could mean billions of calls, making it impractical.

Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem's nature and why memoization is needed.

🧠

DFS with Memoization (Top-Down DP)

💡 This approach improves brute force by caching results of subproblems, avoiding repeated computations and reducing time complexity drastically.

Intuition

Use DFS to explore neighbors but store the longest path from each cell once computed, so subsequent calls reuse the cached value.

Algorithm

1. Initialize a dp matrix with zeros to store longest path lengths.
2. For each cell, run DFS if dp value is zero (not computed).
3. In DFS, explore neighbors with strictly larger values and update dp[i][j] as 1 plus max of neighbors' dp.
4. Return the maximum dp value found across all cells.

💡 Memoization ensures each cell's longest path is computed once, turning exponential recursion into polynomial time.

Recurrence:dp[i][j] = 1 + max(dp[x][y]) for neighbors (x,y) with matrix[x][y] > matrix[i][j]

</>

Code

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])
        dp = [[0]*n for _ in range(m)]

        def dfs(i, j):
            if dp[i][j] != 0:
                return dp[i][j]
            max_len = 1
            for x, y in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
                if 0 <= x < m and 0 <= y < n and matrix[x][y] > matrix[i][j]:
                    length = 1 + dfs(x, y)
                    if length > max_len:
                        max_len = length
            dp[i][j] = max_len
            return max_len

        result = 0
        for i in range(m):
            for j in range(n):
                path_len = dfs(i, j)
                if path_len > result:
                    result = path_len
        return result

# Example usage:
# sol = Solution()
# print(sol.longestIncreasingPath([[9,9,4],[6,6,8],[2,1,1]]))  # Output: 4

Line Notes

dp = [[0]*n for _ in range(m)]Initialize memo table with zeros indicating uncomputed states

if dp[i][j] != 0:Return cached result if already computed

for x, y in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:Explore all four neighbors

if 0 <= x < m and 0 <= y < n and matrix[x][y] > matrix[i][j]:Check bounds and strictly increasing condition

dp[i][j] = max_lenCache the computed longest path length for cell (i,j)

for i in range(m):Iterate over all rows to start DFS

for j in range(n):Iterate over all columns to start DFS

return resultReturn the maximum path length found

import java.util.*;

public class Solution {
    private int m, n;
    private int[][] matrix, dp;

    public int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        this.matrix = matrix;
        m = matrix.length;
        n = matrix[0].length;
        dp = new int[m][n];
        int result = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int len = dfs(i, j);
                if (len > result) result = len;
            }
        }
        return result;
    }

    private int dfs(int i, int j) {
        if (dp[i][j] != 0) return dp[i][j];
        int maxLen = 1;
        int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
        for (int[] d : dirs) {
            int x = i + d[0], y = j + d[1];
            if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]) {
                int len = 1 + dfs(x, y);
                if (len > maxLen) maxLen = len;
            }
        }
        dp[i][j] = maxLen;
        return maxLen;
    }

    // Example usage:
    // public static void main(String[] args) {
    //     Solution sol = new Solution();
    //     int[][] matrix = {{9,9,4},{6,6,8},{2,1,1}};
    //     System.out.println(sol.longestIncreasingPath(matrix)); // Output: 4
    // }
}

Line Notes

dp = new int[m][n];Create memo table initialized to zero

if (dp[i][j] != 0) return dp[i][j];Return cached result if available

for (int[] d : dirs)Iterate over four directions

if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j])Check valid move and increasing condition

dp[i][j] = maxLen;Cache computed longest path length

for (int i = 0; i < m; i++)Start DFS from each row

for (int j = 0; j < n; j++)Start DFS from each column

return maxLen;Return longest path length from current cell

#include <vector>
#include <iostream>
using namespace std;

class Solution {
    int m, n;
    vector<vector<int>> matrix, dp;
public:
    int longestIncreasingPath(vector<vector<int>>& mat) {
        if (mat.empty() || mat[0].empty()) return 0;
        matrix = mat;
        m = matrix.size();
        n = matrix[0].size();
        dp.assign(m, vector<int>(n, 0));
        int result = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int len = dfs(i, j);
                if (len > result) result = len;
            }
        }
        return result;
    }

private:
    int dfs(int i, int j) {
        if (dp[i][j] != 0) return dp[i][j];
        int maxLen = 1;
        int dirs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
        for (auto& d : dirs) {
            int x = i + d[0], y = j + d[1];
            if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]) {
                int len = 1 + dfs(x, y);
                if (len > maxLen) maxLen = len;
            }
        }
        dp[i][j] = maxLen;
        return maxLen;
    }
};

// Example usage:
// int main() {
//     Solution sol;
//     vector<vector<int>> matrix = {{9,9,4},{6,6,8},{2,1,1}};
//     cout << sol.longestIncreasingPath(matrix) << endl; // Output: 4
//     return 0;
// }

Line Notes

dp.assign(m, vector<int>(n, 0));Initialize memo table with zeros

if (dp[i][j] != 0) return dp[i][j];Return cached result if computed

for (auto& d : dirs)Loop over four directions

if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j])Check valid move and increasing condition

dp[i][j] = maxLen;Store computed longest path length

for (int i = 0; i < m; i++)Start DFS from each row

for (int j = 0; j < n; j++)Start DFS from each column

return maxLen;Return longest path length from current cell

var longestIncreasingPath = function(matrix) {
    if (!matrix || matrix.length === 0 || matrix[0].length === 0) return 0;
    const m = matrix.length, n = matrix[0].length;
    const dp = Array.from({length: m}, () => Array(n).fill(0));

    function dfs(i, j) {
        if (dp[i][j] !== 0) return dp[i][j];
        let maxLen = 1;
        const directions = [[-1,0],[1,0],[0,-1],[0,1]];
        for (const [dx, dy] of directions) {
            const x = i + dx, y = j + dy;
            if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]) {
                const len = 1 + dfs(x, y);
                if (len > maxLen) maxLen = len;
            }
        }
        dp[i][j] = maxLen;
        return maxLen;
    }

    let result = 0;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            const pathLen = dfs(i, j);
            if (pathLen > result) result = pathLen;
        }
    }
    return result;
};

// Example usage:
// console.log(longestIncreasingPath([[9,9,4],[6,6,8],[2,1,1]])); // Output: 4

Line Notes

const dp = Array.from({length: m}, () => Array(n).fill(0));Initialize memo table with zeros

if (dp[i][j] !== 0) return dp[i][j];Return cached result if computed

for (const [dx, dy] of directions)Iterate over four directions

if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j])Check bounds and increasing condition

dp[i][j] = maxLen;Cache computed longest path length

for (let i = 0; i < m; i++)Start DFS from each row

for (let j = 0; j < n; j++)Start DFS from each column

return maxLen;Return longest path length from current cell

⏱

Complexity

TimeO(m * n)

SpaceO(m * n) for dp and recursion stack

Each cell is computed once and cached, so total calls are proportional to number of cells.

💡 For a 200x200 matrix, this means at most 40,000 calls, which is efficient.

Interview Verdict: Accepted

This is the standard efficient solution for this problem and is expected in interviews.

🧠

Topological Sort Based DP (Bottom-Up)

💡 This approach treats the matrix as a DAG where edges go from smaller to larger values, then uses topological sorting to compute longest paths iteratively.

Intuition

Sort cells by their values ascendingly, then for each cell, update neighbors with larger values by relaxing their dp values, building longest paths bottom-up.

Algorithm

1. Create a list of all cells and sort them by their values ascendingly.
2. Initialize a dp matrix with 1s since minimum path length is 1.
3. Iterate over cells in sorted order, for each cell update dp of neighbors with larger values.
4. Return the maximum dp value found.

💡 This approach uses the DAG property of the matrix values to compute dp iteratively without recursion.

Recurrence:dp[i][j] = max(dp[i][j], 1 + dp[x][y]) for neighbors (x,y) with matrix[x][y] < matrix[i][j]

</>

Code

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])
        cells = [(i, j) for i in range(m) for j in range(n)]
        cells.sort(key=lambda x: matrix[x[0]][x[1]])
        dp = [[1]*n for _ in range(m)]

        directions = [(-1,0),(1,0),(0,-1),(0,1)]
        for i, j in cells:
            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:
                        dp[x][y] = dp[i][j] + 1

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

# Example usage:
# sol = Solution()
# print(sol.longestIncreasingPath([[9,9,4],[6,6,8],[2,1,1]]))  # Output: 4

Line Notes

cells = [(i, j) for i in range(m) for j in range(n)]Create list of all cell coordinates

cells.sort(key=lambda x: matrix[x[0]][x[1]])Sort cells by their values ascendingly

dp = [[1]*n for _ in range(m)]Initialize dp with 1 since each cell is a path of length 1

for i, j in cells:Process cells in ascending order of values

if dp[x][y] < dp[i][j] + 1:Relax dp value for neighbor with larger value

return max(max(row) for row in dp)Return maximum path length found

import java.util.*;

public class Solution {
    private int m, n;
    private int[][] matrix, dp;

    public int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        this.matrix = matrix;
        m = matrix.length;
        n = matrix[0].length;
        dp = new int[m][n];
        List<int[]> cells = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                cells.add(new int[]{i, j});
                dp[i][j] = 1;
            }
        }
        cells.sort(Comparator.comparingInt(a -> matrix[a[0]][a[1]]));

        int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
        for (int[] cell : cells) {
            int i = cell[0], j = cell[1];
            for (int[] d : dirs) {
                int x = i + d[0], y = j + d[1];
                if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]) {
                    if (dp[x][y] < dp[i][j] + 1) {
                        dp[x][y] = dp[i][j] + 1;
                    }
                }
            }
        }

        int result = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dp[i][j] > result) result = dp[i][j];
            }
        }
        return result;
    }

    // Example usage:
    // public static void main(String[] args) {
    //     Solution sol = new Solution();
    //     int[][] matrix = {{9,9,4},{6,6,8},{2,1,1}};
    //     System.out.println(sol.longestIncreasingPath(matrix)); // Output: 4
    // }
}

Line Notes

List<int[]> cells = new ArrayList<>();Store all cell coordinates

cells.sort(Comparator.comparingInt(a -> matrix[a[0]][a[1]]));Sort cells by their values ascendingly

dp[i][j] = 1;Initialize dp with 1 for each cell

for (int[] cell : cells)Process cells in ascending order

if (dp[x][y] < dp[i][j] + 1)Relax dp value for neighbor with larger value

return result;Return maximum path length found

for (int i = 0; i < m; i++)Iterate rows to find max dp

for (int j = 0; j < n; j++)Iterate columns to find max dp

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

class Solution {
    int m, n;
    vector<vector<int>> matrix, dp;
public:
    int longestIncreasingPath(vector<vector<int>>& mat) {
        if (mat.empty() || mat[0].empty()) return 0;
        matrix = mat;
        m = matrix.size();
        n = matrix[0].size();
        dp.assign(m, vector<int>(n, 1));
        vector<pair<int,int>> cells;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                cells.emplace_back(i, j);
            }
        }
        sort(cells.begin(), cells.end(), [&](auto &a, auto &b) {
            return matrix[a.first][a.second] < matrix[b.first][b.second];
        });

        int dirs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
        for (auto& cell : cells) {
            int i = cell.first, j = cell.second;
            for (auto& d : dirs) {
                int x = i + d[0], y = j + d[1];
                if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]) {
                    if (dp[x][y] < dp[i][j] + 1) {
                        dp[x][y] = dp[i][j] + 1;
                    }
                }
            }
        }

        int result = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dp[i][j] > result) result = dp[i][j];
            }
        }
        return result;
    }
};

// Example usage:
// int main() {
//     Solution sol;
//     vector<vector<int>> matrix = {{9,9,4},{6,6,8},{2,1,1}};
//     cout << sol.longestIncreasingPath(matrix) << endl; // Output: 4
//     return 0;
// }

Line Notes

dp.assign(m, vector<int>(n, 1));Initialize dp with 1 for each cell

cells.emplace_back(i, j);Store all cell coordinates

sort(cells.begin(), cells.end(), ...Sort cells by their values ascendingly

if (dp[x][y] < dp[i][j] + 1)Relax dp value for neighbor with larger value

for (auto& cell : cells)Process cells in ascending order

return result;Return maximum path length found

for (int i = 0; i < m; i++)Iterate rows to find max dp

for (int j = 0; j < n; j++)Iterate columns to find max dp

var longestIncreasingPath = function(matrix) {
    if (!matrix || matrix.length === 0 || matrix[0].length === 0) return 0;
    const m = matrix.length, n = matrix[0].length;
    const dp = Array.from({length: m}, () => Array(n).fill(1));
    const cells = [];
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            cells.push([i, j]);
        }
    }
    cells.sort((a, b) => matrix[a[0]][a[1]] - matrix[b[0]][b[1]]);

    const directions = [[-1,0],[1,0],[0,-1],[0,1]];
    for (const [i, j] of cells) {
        for (const [dx, dy] of directions) {
            const x = i + dx, y = j + dy;
            if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]) {
                if (dp[x][y] < dp[i][j] + 1) {
                    dp[x][y] = dp[i][j] + 1;
                }
            }
        }
    }

    let result = 0;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (dp[i][j] > result) result = dp[i][j];
        }
    }
    return result;
};

// Example usage:
// console.log(longestIncreasingPath([[9,9,4],[6,6,8],[2,1,1]])); // Output: 4

Line Notes

const dp = Array.from({length: m}, () => Array(n).fill(1));Initialize dp with 1 for each cell

cells.push([i, j]);Store all cell coordinates

cells.sort((a, b) => matrix[a[0]][a[1]] - matrix[b[0]][b[1]]);Sort cells by their values ascendingly

if (dp[x][y] < dp[i][j] + 1)Relax dp value for neighbor with larger value

for (const [i, j] of cells)Process cells in ascending order

return result;Return maximum path length found

for (let i = 0; i < m; i++)Iterate rows to find max dp

for (let j = 0; j < n; j++)Iterate columns to find max dp

⏱

Complexity

TimeO(m * n * log(m * n))

SpaceO(m * n)

Sorting all cells takes O(m*n*log(m*n)) and each cell updates up to 4 neighbors.

💡 For a 200x200 matrix, sorting 40,000 cells is efficient and the DP updates are linear.

Interview Verdict: Accepted

This approach is an elegant bottom-up alternative to memoized DFS and is acceptable in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 Memoized DFS (Approach 2) is the best balance of simplicity and efficiency and should be coded in most interviews.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(m * n * 4^(m*n))	O(m * n) recursion stack	Yes (deep recursion)	Yes	Mention only - never code
2. DFS with Memoization	O(m * n)	O(m * n)	Possible but unlikely for constraints	Yes	Code this approach
3. Topological Sort Based DP	O(m * n * log(m * n))	O(m * n)	No	Yes	Mention as alternative

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain brute force to show understanding, optimize with memoization, and optionally mention topological DP. Practice coding and testing edge cases.

How to Present

Clarify input size and constraints.Explain brute force DFS and why it's inefficient.Introduce memoization to optimize repeated work.Optionally discuss bottom-up topological DP.Write clean code and test with examples and edge cases.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

Interviewer tests your understanding of DFS, memoization, DP on grids as DAGs, and ability to optimize naive solutions.

Common Follow-ups

• What if diagonal moves are allowed? → Adjust neighbor directions.
• Can you reconstruct the path? → Store parent pointers during DFS.

💡 These follow-ups test your flexibility and ability to extend solutions beyond the base problem.

🔍

Pattern Recognition

When to Use

1) Problem asks for longest increasing/decreasing path in grid or matrix. 2) Moves allowed in 4 directions. 3) Overlapping subproblems due to multiple paths. 4) No cycles due to strictly increasing condition.

Signature Phrases

longest strictly increasing pathmove up/down/left/rightmatrix grid traversal

NOT This Pattern When

Problems allowing cycles or arbitrary moves, or those requiring shortest paths, are different patterns.

Similar Problems

Longest Path in a Directed Acyclic Graph - same DAG conceptNumber of Increasing Paths in a Grid - counting instead of longestMaximum Path Sum in a Matrix - similar DP on grid

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. The following code attempts to solve the Russian Doll Envelopes problem. Identify the line that contains a subtle bug that causes incorrect results on some inputs.

medium

A. Line 4: Sorting envelopes by width ascending and height ascending

B. Line 6: Extracting heights from envelopes

C. Line 8: Using bisect_left to find insertion index

D. Line 11: Replacing element in lis at found index

Solution

1. Step 1: Examine sorting order

   Sorting by width ascending and height ascending causes envelopes with same width but increasing height to be counted incorrectly in LIS.

2. Step 2: Understand LIS requirement

   Heights must be sorted descending for equal widths to avoid counting invalid envelopes.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting order bug leads to wrong LIS and incorrect nesting count [OK]

Hint: Sort height descending for equal widths to avoid LIS errors [OK]

Common Mistakes:

• Sorting both dimensions ascending instead of height descending
• Misusing bisect functions
• Incorrectly extracting heights

4. Suppose the problem changes: now you can reuse elements multiple times to form the longest strictly increasing subsequence. Which modification to the optimized LIS algorithm is correct?

hard

A. The optimized binary search approach cannot be directly adapted; use a DP with memoization considering reuse

B. Modify the DP to consider repeated elements by changing comparison from '>' to '>=' in recursion

C. Use the same binary search approach but allow replacing tails with equal or greater elements (use bisect_right)

D. Sort the array and count the longest consecutive increasing sequence allowing duplicates

Solution

1. Step 1: Understand reuse impact

   Allowing reuse breaks the strictly increasing subsequence definition and the binary search tails logic.

2. Step 2: Evaluate algorithm suitability

   The optimized binary search approach relies on unique progression; reuse requires state tracking, best handled by DP with memoization.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Reuse requires more complex DP, not simple binary search [OK]

Hint: Reuse breaks tails logic; DP with memo needed [OK]

Common Mistakes:

• Trying to fix with bisect_right only
• Changing comparison operators without DP
• Assuming sorting solves reuse problem

5. Suppose the problem is modified so that envelopes can be reused multiple times to form the longest nesting sequence (i.e., you can use the same envelope multiple times). Which modification to the algorithm is correct to handle this variant?

hard

A. No change needed; the original LIS approach already handles reuse

B. Keep the same sorting and LIS approach but use bisect_right instead of bisect_left to allow equal heights

C. Sort envelopes by width ascending and height descending, then find the Longest Non-Decreasing Subsequence (LNDS) on heights using binary search

D. Use dynamic programming with nested loops allowing repeated envelopes by removing strict inequality checks

Solution

1. Step 1: Understand reuse impact

   Allowing reuse means envelopes can be repeated, so strict increasing conditions must be relaxed.

2. Step 2: Recognize LIS approach limitation

   Binary search LIS assumes unique usage; it cannot handle repeated envelopes correctly.

3. Step 3: Use DP with nested loops

   Dynamic programming with nested loops and relaxed inequalities can count repeated envelopes, though with higher time complexity.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Naive LIS fails on reuse; DP with relaxed checks handles it correctly [OK]

Hint: Reuse breaks LIS; DP with relaxed checks needed [OK]

Common Mistakes:

• Assuming bisect_right fixes reuse problem
• Thinking original LIS handles reuse
• Trying LNDS without changing DP logic