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.
This approach utilizes dynamic programming with memoization to find the maximum number of strictly increasing cells starting from each cell. The idea is to explore the matrix and remember results for subproblems to avoid recomputation.
We can start from any cell and either move right or down, ensuring each move is to a greater value cell. This approach uses a recursive function that checks each possible move and calculates the maximum number of steps possible. The results are stored in a cache for efficiency.
This solution defines a recursive function dp which returns the length of the longest path starting from a given cell. It checks all possible cells in the same row and column that can be visited (strictly greater value) and chooses the maximum path length.
Calculated results are stored in a matrix cache to prevent redundant calculations.
Time Complexity: O(m * n), as each cell is computed only once and stored in cache.
Space Complexity: O(m * n), due to the recursion stack and cache.
In this approach, we consider each cell as a graph node, where an edge exists from cell A to cell B if moving from A to B is a valid step. The problem then becomes finding the longest path in this Directed Acyclic Graph (DAG), which can be efficiently found using a topological sort approach.
This Java solution employs a topological sort based on sorting the cells by their values, ensuring that we are processing cells in a valid topological order. For each cell, the solution updates paths considering the paths from all previously processed cells in the same row and column.
Time Complexity: O(m * n log(m * n)), due to sorting all cells initially based on their values.
Space Complexity: O(m * n) for storing the path lengths in the dp array.
Based on the problem description, the value of the cells we move through in sequence must strictly increase. Therefore, we can use a hash table g to record the positions of all cells corresponding to each value, and then traverse from the smallest to the largest value.
During this process, we can maintain two arrays rowMax and colMax, which record the maximum increasing length of each row and column, respectively. Initially, all elements of these two arrays are 0.
For all cell positions corresponding to each value, we traverse them in order of position. For each position (i, j), we can calculate the maximum increasing length ending at that position as 1 + max(rowMax[i], colMax[j]), update the answer, and then update rowMax[i] and colMax[j].
Finally, return the answer.
The time complexity is O(m times n times log(m times n)), and the space complexity is O(m times n).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Dynamic Programming with Memoization | Time Complexity: O(m * n), as each cell is computed only once and stored in cache. Space Complexity: O(m * n), due to the recursion stack and cache. |
| Topological Sort Approach | Time Complexity: O(m * n log(m * n)), due to sorting all cells initially based on their values. Space Complexity: O(m * n) for storing the path lengths in the |
| Sorting + Dynamic Programming | — |
| 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 |
Leetcode Weekly contest 347 - Hard - Maximum Strictly Increasing Cells in a Matrix • Prakhar Agrawal • 3,775 views views
Watch 8 more video solutions →Practice Maximum Strictly Increasing Cells in a Matrix with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor