Maximum Strictly Increasing Cells in a Matrix
HardPrompt
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.lengthn == mat[i].length1 <= m, n <= 1051 <= m * n <= 105-105 <= mat[i][j] <= 105
Approaches
2 approaches with complexity analysis and trade-offs.
This approach models the problem as finding the longest path in a Directed Acyclic Graph (DAG). Each cell is a node, and a directed edge exists from cell A to cell B if they are in the same row or column and value(B) > value(A). We use Depth First Search (DFS) starting from every cell to find the longest path. To avoid recomputing the longest path from the same cell multiple times, we use memoization (a form of dynamic programming).
Algorithm
- We model the problem as finding the longest path in a Directed Acyclic Graph (DAG).
- Each cell
(r, c)is a node. - A directed edge exists from cell A to cell B if they are in the same row or column and
value(B) > value(A). - We use a recursive Depth First Search (DFS) function,
dfs(r, c), to find the length of the longest path starting at cell(r, c). - To avoid recomputing results for the same cell, we use a 2D array
dp[m][n]for memoization. - The main function iterates through all cells, calling
dfsfor each one, and returns the maximum length found.
Walkthrough
We define a function dfs(r, c) that computes the length of the longest increasing path starting from cell (r, c). A 2D array dp[m][n] is used for memoization, where dp[r][c] stores the result for dfs(r, c). It's initialized with a value indicating that the state has not been computed (e.g., 0).
The dfs(r, c) function works as follows:
- If
dp[r][c]is not 0, it means we have already computed the result, so we return it. - Otherwise, we initialize the path length for the current cell to 1 (for the cell itself),
maxLength = 1. - We then explore all valid moves:
- Iterate through all other cells
(r, j)in the same rowr. Ifmat[r][j] > mat[r][c], we can move there. We recursively calldfs(r, j)and update our maximum length:maxLength = max(maxLength, 1 + dfs(r, j)). - Similarly, iterate through all other cells
(i, c)in the same columnc. Ifmat[i][c] > mat[r][c], we updatemaxLength = max(maxLength, 1 + dfs(i, c)).
- Iterate through all other cells
- After checking all possible moves, we store the computed
maxLengthindp[r][c]and return it.
The main part of the algorithm iterates through every cell (i, j) in the matrix, calling dfs(i, j) to ensure we find the longest path starting from any possible cell. The overall maximum found is the answer.
class Solution { int[][] dp; int m, n; int[][] mat; public int maxIncreasingCells(int[][] mat) { this.m = mat.length; this.n = mat[0].length; this.mat = mat; this.dp = new int[m][n]; int maxPath = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { maxPath = Math.max(maxPath, dfs(i, j)); } } return maxPath; } private int dfs(int r, int c) { if (dp[r][c] != 0) { return dp[r][c]; } int currentMax = 1; // Check same row for (int j = 0; j < n; j++) { if (mat[r][j] > mat[r][c]) { currentMax = Math.max(currentMax, 1 + dfs(r, j)); } } // Check same column for (int i = 0; i < m; i++) { if (mat[i][c] > mat[r][c]) { currentMax = Math.max(currentMax, 1 + dfs(i, c)); } } dp[r][c] = currentMax; return currentMax; }}Complexity
Time
O(m * n * (m + n)). For each of the `m*n` states, we iterate through `m` row elements and `n` column elements. This is too slow for the given constraints.
Space
O(m * n) for the memoization table `dp` and the recursion stack depth.
Trade-offs
Pros
Conceptually simple to understand as it directly translates the problem into a graph traversal.
Easy to implement.
Cons
The time complexity is too high for the given constraints, leading to a 'Time Limit Exceeded' error on larger test cases.
This is a more efficient dynamic programming approach. The key idea is to process cells in increasing order of their values. This ensures that when we calculate the longest path for a cell, the values for all potential previous cells (which must have smaller values) have already been computed. By grouping cells with the same value and processing them in batches, we can efficiently update the state.
Algorithm
- Create a
TreeMapto group cell coordinates by their values. TheTreeMapnaturally sorts the cells by value in ascending order. - Initialize a
dp[m][n]table to store the length of the longest path ending at each cell. - Initialize two arrays,
maxLenRow[m]andmaxLenCol[n], to keep track of the maximum path length seen so far in each row and column, respectively. Both are initialized to zeros. - Iterate through the
TreeMapentries (which are sorted by value). - For each value and its list of associated cells, perform a two-pass process:
- First Pass: For each cell
(r, c)with the current value, calculate its path length:dp[r][c] = 1 + max(maxLenRow[r], maxLenCol[c]). This uses the maximums from cells with strictly smaller values. - Second Pass: After computing the
dpvalues for all cells in the group, iterate through them again to update themaxLenRowandmaxLenColarrays with the new maximums.maxLenRow[r] = max(maxLenRow[r], dp[r][c])andmaxLenCol[c] = max(maxLenCol[c], dp[r][c]).
- First Pass: For each cell
- Keep track of the overall maximum
dpvalue found, which will be the final answer.
Walkthrough
- First, we group all cell coordinates by their value using a
TreeMap. ATreeMapis used because it automatically sorts the entries by their keys (the cell values), which is essential for our DP approach. - We use a 2D DP table
dp[m][n], wheredp[i][j]will store the length of the longest increasing path ending at cell(i, j). - We also maintain two auxiliary arrays,
maxLenRow[m]andmaxLenCol[n].maxLenRow[i]stores the maximum path length found so far for any cell in rowi, andmaxLenCol[j]does the same for columnj. These arrays help us quickly find the length of the best path we can extend. - A critical detail is handling cells with the same value. We cannot update
maxLenRowandmaxLenColimmediately after processing a cell, because other cells with the same value in the same row or column should not use this updated value (as paths must be strictly increasing). - To solve this, we process cells with the same value in a batch. We iterate through the
TreeMap, and for each block of cells with an identical value:- First Pass (Calculate DP): For each cell
(val, r, c)in the block, we calculate itsdpvalue:dp[r][c] = 1 + max(maxLenRow[r], maxLenCol[c]). Here,maxLenRowandmaxLenColhold the maximums from cells with values strictly smaller thanval. - Second Pass (Update max lengths): After computing the
dpvalues for all cells in the current block, we iterate through them again to updatemaxLenRow[r]andmaxLenCol[c]with their new, potentially larger, path lengths. These updated values will then be used for the next block of cells with a greater value.
- First Pass (Calculate DP): For each cell
- The overall maximum value computed in the
dptable is the answer.
import java.util.*; class Solution { public int maxIncreasingCells(int[][] mat) { int m = mat.length; int n = mat[0].length; Map<Integer, List<int[]>> valToCells = new TreeMap<>(); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { valToCells.computeIfAbsent(mat[i][j], k -> new ArrayList<>()).add(new int[]{i, j}); } } int[][] dp = new int[m][n]; int[] maxLenRow = new int[m]; int[] maxLenCol = new int[n]; int ans = 0; for (int val : valToCells.keySet()) { List<int[]> cells = valToCells.get(val); // First pass: calculate dp values for all cells with the current value for (int[] cell : cells) { int r = cell[0]; int c = cell[1]; dp[r][c] = 1 + Math.max(maxLenRow[r], maxLenCol[c]); } // Second pass: update the max lengths for rows and columns for (int[] cell : cells) { int r = cell[0]; int c = cell[1]; maxLenRow[r] = Math.max(maxLenRow[r], dp[r][c]); maxLenCol[c] = Math.max(maxLenCol[c], dp[r][c]); ans = Math.max(ans, dp[r][c]); } } return ans; }}Complexity
Time
O(m * n * log(D)), where D is the number of distinct values in the matrix. Populating the `TreeMap` takes `O(m*n*log(D))`. Iterating through the map and all cells takes `O(m*n)`. The overall complexity is dominated by the map creation.
Space
O(m * n). This is for the `dp` table and the `TreeMap` which can store up to `m*n` elements. The `maxLenRow` and `maxLenCol` arrays take `O(m+n)` space.
Trade-offs
Pros
Significantly more efficient than the memoized DFS approach.
Correctly handles cells with duplicate values by processing them in batches.
Passes the time limits for the given constraints.
Cons
Requires more complex logic to handle updates for cells with the same value correctly.
Uses
O(m*n)auxiliary space, which can be large.
Solutions
Solution
class Solution {public int maxIncreasingCells(int[][] mat) { int m = mat.length, n = mat[0].length; TreeMap<Integer, List<int[]>> g = new TreeMap<>(); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { g.computeIfAbsent(mat[i][j], k->new ArrayList<>()).add(new int[]{i, j}); } } int[] rowMax = new int[m]; int[] colMax = new int[n]; int ans = 0; for (var e : g.entrySet()) { var pos = e.getValue(); int[] mx = new int[pos.size()]; int k = 0; for (var p : pos) { int i = p[0], j = p[1]; mx[k] = Math.max(rowMax[i], colMax[j]) + 1; ans = Math.max(ans, mx[k++]); } for (k = 0; k < mx.length; ++k) { int i = pos.get(k)[0], j = pos.get(k)[1]; rowMax[i] = Math.max(rowMax[i], mx[k]); colMax[j] = Math.max(colMax[j], mx[k]); } } return ans; }}class Solution {public: int maxIncreasingCells(vector<vector<int>> &mat) { int m = mat.size(), n = mat[0].size(); map<int, vector<pair<int, int>>> g; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { g[mat[i][j]].emplace_back(i, j); } } vector<int> rowMax(m); vector<int> colMax(n); int ans = 0; for (auto &[_, pos] : g) { vector<int> mx; for (auto &[i, j] : pos) { mx.push_back(max(rowMax[i], colMax[j]) + 1); ans = max(ans, mx.back()); } for (int k = 0; k < mx.size(); ++k) { auto &[i, j] = pos[k]; rowMax[i] = max(rowMax[i], mx[k]); colMax[j] = max(colMax[j], mx[k]); } } return ans; }};class Solution: def maxIncreasingCells(self, mat: List[List[int]]) -> int: m, n = len(mat), len(mat[0]) g = defaultdict(list) for i in range(m): for j in range(n): g[mat[i][j]]. append((i, j)) rowMax = [0] * m colMax = [0] * n ans = 0 for _, pos in sorted(g . items()): mx = [] for i, j in pos: mx . append(1 + max(rowMax[i], colMax[j])) ans = max(ans, mx[- 1]) for k, (i, j) in enumerate(pos): rowMax[i] = max(rowMax[i], mx[k]) colMax[j] = max(colMax[j], mx[k]) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.