Watch 9 video solutions for Maximum Strictly Increasing Cells in a Matrix, a hard level problem involving Array, Hash Table, Binary Search. This walkthrough by Prakhar Agrawal has 3,775 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given a 1-indexed m x n integer matrix mat, you can select any cell in the matrix as your starting cell.
From the starting cell, you can move to any other cell in the same row or column, but only if the value of the destination cell is strictly greater than the value of the current cell. You can repeat this process as many times as possible, moving from cell to cell until you can no longer make any moves.
Your task is to find the maximum number of cells that you can visit in the matrix by starting from some cell.
Return an integer denoting the maximum number of cells that can be visited.
Example 1:
Input: mat = [[3,1],[3,4]] Output: 2 Explanation: The image shows how we can visit 2 cells starting from row 1, column 2. It can be shown that we cannot visit more than 2 cells no matter where we start from, so the answer is 2.
Example 2:
Input: mat = [[1,1],[1,1]] Output: 1 Explanation: Since the cells must be strictly increasing, we can only visit one cell in this example.
Example 3:
Input: mat = [[3,1,6],[-9,5,7]] Output: 4 Explanation: The image above shows how we can visit 4 cells starting from row 2, column 1. It can be shown that we cannot visit more than 4 cells no matter where we start from, so the answer is 4.
Constraints:
m == mat.length n == mat[i].length 1 <= m, n <= 1051 <= m * n <= 105-105 <= mat[i][j] <= 105Problem Overview: You are given an m x n matrix. From any cell, you can move to another cell in the same row or column if the destination value is strictly greater. The goal is to compute the maximum number of cells you can visit in such a strictly increasing sequence.
Approach 1: Dynamic Programming with Memoization and Value Sorting (Time: O(mn log(mn)), Space: O(mn))
The key observation: the next move must go to a strictly larger value in the same row or column. Instead of exploring all paths repeatedly, process cells in increasing order of their values. For each cell (r, c), compute the best path length ending there using previously computed results from the same row and column. Maintain arrays rowMax[r] and colMax[c] representing the longest sequence ending in that row or column with smaller values. Sort all cells by value, process equal values in batches, and update the row/column states afterward to avoid invalid transitions between equal numbers.
This approach combines dynamic programming with ordering logic from sorting. Memoization avoids recomputing subproblems, and the row/column caches reduce the transition lookup to O(1). The final answer is the maximum value stored for any cell.
Approach 2: Topological Sort on Value Graph (Time: O(mn log(mn)), Space: O(mn))
Another way to view the matrix is as a directed graph: each cell points to larger values in the same row or column. Since edges only go from smaller to larger values, the graph is a DAG. Build edges implicitly by grouping cells with the same value and processing them in sorted order. For each cell, compute its longest path using previously processed nodes, similar to a topological DP update.
The topological ordering comes naturally from sorting the matrix values. When processing a node, the longest path ending there equals 1 + max(bestRow[r], bestCol[c]). After finishing a value group, update the row and column best values. This approach mirrors classic matrix dynamic programming but framed as DAG processing. Languages like Java or C# often implement this with ordered maps or sorted lists.
Recommended for interviews: The dynamic programming with value sorting approach is the expected solution. It demonstrates understanding of DP state design and how to exploit row/column structure for constant-time transitions. Explaining the DAG interpretation and topological processing also scores well because it shows you recognize the underlying graph structure.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force DFS from Each Cell | Exponential (worst case) | O(mn) | Useful only for understanding the search space; impractical for large matrices |
| Dynamic Programming with Sorting | O(mn log(mn)) | O(mn) | General optimal solution; efficient when processing cells ordered by value |
| Topological Sort on Value DAG | O(mn log(mn)) | O(mn) | When modeling the problem as a DAG of increasing values or implementing graph-style DP |