Skip to main content
Talentd

Maximum Strictly Increasing Cells in a Matrix - Solution & Explanation

HardArrayHash TableBinary SearchDynamic Programming14 min read
Practice this problem

Problem Statement

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 <= 105
  • 1 <= m * n <= 105
  • -105 <= mat[i][j] <= 105

Approach Overview

Problem 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 1: Dynamic Programming with Memoization

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.

Code

PythonC++

Python

C++

Complexity

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.

Try this approach in the editor →

Approach 2: Topological Sort Approach

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.

Code

JavaC#

Java

C#

Complexity

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.

Try this approach in the editor →

Approach 3: Sorting + Dynamic Programming

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

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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 dp array.

Sorting + Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force DFS from Each CellExponential (worst case)O(mn)Useful only for understanding the search space; impractical for large matrices
Dynamic Programming with SortingO(mn log(mn))O(mn)General optimal solution; efficient when processing cells ordered by value
Topological Sort on Value DAGO(mn log(mn))O(mn)When modeling the problem as a DAG of increasing values or implementing graph-style DP

Video Solution

Leetcode Weekly contest 347 - Hard - Maximum Strictly Increasing Cells in a Matrix • Prakhar Agrawal • 3,803 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Maximum Strictly Increasing Cells in a Matrix easy or hard?
The problem is classified as Hard on LeetCode because it requires combining multiple concepts: dynamic programming, sorting by value, and row/column state tracking. Many candidates struggle to recognize that the matrix can be processed in value order to avoid expensive graph traversal.
Maximum Strictly Increasing Cells in a Matrix Python/Java solution
Python solutions usually sort all cells and maintain rowMax and colMax arrays for dynamic programming updates. Java implementations often use similar logic with lists or TreeMap-based grouping for values. Both approaches run in O(mn log(mn)) time and O(mn) space.
How to solve Maximum Strictly Increasing Cells in a Matrix in O(mn log(mn))?
Flatten the matrix into a list of cells and sort them by value. Process cells in groups of equal values and compute the longest path ending at each cell using row and column maximums: dp[r][c] = 1 + max(rowMax[r], colMax[c]). After finishing a value group, update rowMax and colMax so equal values don't influence each other.
What is the best approach for Maximum Strictly Increasing Cells in a Matrix?
Dynamic programming with value sorting is the most efficient and commonly accepted solution. Cells are processed in increasing order of value while maintaining the best path length for each row and column. This allows each state to be computed in constant time after sorting, giving an overall complexity of O(mn log(mn)).
Is Maximum Strictly Increasing Cells in a Matrix asked at Google/Amazon/Meta?
This problem reflects patterns commonly used in interviews at companies like Google, Amazon, and Meta, especially matrix dynamic programming and DAG longest-path problems. Variants involving row/column transitions and value ordering appear frequently in senior-level coding interviews.
What data structure is used in Maximum Strictly Increasing Cells in a Matrix?
The solution typically uses arrays or hash maps to track the best path length for each row and column, along with a sorted list of matrix cells. Some implementations also use ordered maps or priority structures to maintain processing order for values.
What is the time complexity of Maximum Strictly Increasing Cells in a Matrix?
The optimal solution runs in O(mn log(mn)) time because all matrix cells are sorted by value before dynamic programming updates are applied. Each cell is processed once, and row/column lookups are constant time. Space complexity is O(mn) for storing DP values and row/column states.

Ready to solve this problem?

Practice Maximum Strictly Increasing Cells in a Matrix with our built-in code editor and test cases.

Practice on FleetCode
Previous

Number of Increasing Paths in a Grid