Maximum Strictly Increasing Cells in a Matrix — Solution
Maximum Strictly Increasing Cells in a Matrix solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Maximum Strictly Increasing Cells in a Matrix is a hard coding problem on arrays, hash table and dynamic programming, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Hash Table, Dynamic Programming, Sorting, Binary Search, Matrix, Ordered Set, Memoization
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an m x n integer matrix mat. Start from any cell. From the current cell you may jump to any other cell in the same row or the same column, as long as its value is strictly greater than the current cell's value. You can keep jumping as long as a move exists.
Return the maximum number of cells you can visit (counting the starting cell).
Example 1
Input: mat = [[3,1],[3,4]]
Output: 2
Explanation: From 1 jump to 3 or 4 (same row/column), then no further strictly larger cell is reachable.
Example 2
Input: mat = [[1,1],[1,1]]
Output: 1
Explanation: No value is strictly larger than another.
Example 3
Input: mat = [[3,1,6],[-9,5,7]]
Output: 4
Explanation: -9 → 3 (same column) → 6 (same row) → 7 (same column) visits 4 cells.
Constraints
m == mat.lengthn == mat[i].length1 <= m, n <= 10^51 <= m * n <= 10^5-10^5 <= mat[i][j] <= 10^5
Hints for Maximum Strictly Increasing Cells in a Matrix
Hint 1
Process the cells in increasing order of value. The best path ending at a cell only depends on smaller cells in its row and column.
Hint 2
Keep
rowBest[r]= the longest path ending at any processed cell of rowr, andcolBest[c]likewise. A cell's best is1 + max(rowBest[r], colBest[c]).Hint 3
Cells with equal values must not chain into each other: compute every cell of one value first, and only then update
rowBest/colBest.
How to solve Maximum Strictly Increasing Cells in a Matrix
A path visits strictly increasing values, so processing cells in increasing value order means every possible predecessor is already finished. The predecessors of a cell are only its row and column, so two arrays of 'best so far' per row and per column replace scanning them.
Approach
- Sort all cells by value.
- Walk the sorted cells one group of equal values at a time.
- For each cell
(r, c)in the group, computebest = 1 + max(rowBest[r], colBest[c])from the arrays as they were before the group. - Then apply the group:
rowBest[r] = max(rowBest[r], best)andcolBest[c] = max(colBest[c], best); track the overall maximum. - Return the maximum.
Why it works
When a cell is processed, rowBest[r] and colBest[c] hold the longest paths ending at strictly smaller cells of its row and column — exactly the cells that may jump into it — so 1 + max is the longest path ending there. Deferring the updates within an equal-value group keeps equal cells from counting each other, which the strict inequality forbids.
Complexity
- Time —
O(m n log(m n)) - Space —
O(m n)
Pitfalls
- Updating
rowBest/colBestimmediately inside a group of equal values lets equal cells chain — wrong for strictly increasing jumps. - A jump can skip any number of cells in the row or column; it is not a move to a neighbour.
- The matrix can be one long row or column (
m * n <= 10^5), so do not allocatem × nbymax(m, n)tables.
Reference solution
Python
from typing import List
def maxIncreasingCells(mat: List[List[int]]) -> int:
m, n = len(mat), len(mat[0])
cells = sorted((mat[r][c], r, c) for r in range(m) for c in range(n))
row_best = [0] * m
col_best = [0] * n
ans = 0
i = 0
total = len(cells)
while i < total:
j = i
while j < total and cells[j][0] == cells[i][0]:
j += 1
results = []
for t in range(i, j):
_, r, c = cells[t]
results.append(1 + max(row_best[r], col_best[c]))
for t in range(i, j):
_, r, c = cells[t]
best = results[t - i]
if best > row_best[r]:
row_best[r] = best
if best > col_best[c]:
col_best[c] = best
if best > ans:
ans = best
i = j
return ansJava
public static int maxIncreasingCells(int[][] mat) {
int m = mat.length, n = mat[0].length, total = m * n;
long[] key = new long[total];
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++)
key[r * n + c] = (long) (mat[r][c] + 100000) * total + (r * n + c);
Arrays.sort(key);
int[] rowBest = new int[m], colBest = new int[n], results = new int[total];
int ans = 0;
for (int i = 0; i < total;) {
long v = key[i] / total;
int j = i;
while (j < total && key[j] / total == v) j++;
for (int t = i; t < j; t++) {
int idx = (int) (key[t] % total), r = idx / n, c = idx % n;
results[t] = 1 + Math.max(rowBest[r], colBest[c]);
}
for (int t = i; t < j; t++) {
int idx = (int) (key[t] % total), r = idx / n, c = idx % n;
rowBest[r] = Math.max(rowBest[r], results[t]);
colBest[c] = Math.max(colBest[c], results[t]);
ans = Math.max(ans, results[t]);
}
i = j;
}
return ans;
}C++
int maxIncreasingCells(vector<vector<int>>& mat) {
int m = mat.size(), n = mat[0].size(), total = m * n;
vector<pair<int, int>> cells;
cells.reserve(total);
for (int r = 0; r < m; r++) for (int c = 0; c < n; c++) cells.push_back({mat[r][c], r * n + c});
sort(cells.begin(), cells.end());
vector<int> rowBest(m, 0), colBest(n, 0), results(total, 0);
int ans = 0;
for (int i = 0; i < total;) {
int j = i;
while (j < total && cells[j].first == cells[i].first) j++;
for (int t = i; t < j; t++) {
int r = cells[t].second / n, c = cells[t].second % n;
results[t] = 1 + max(rowBest[r], colBest[c]);
}
for (int t = i; t < j; t++) {
int r = cells[t].second / n, c = cells[t].second % n;
rowBest[r] = max(rowBest[r], results[t]);
colBest[c] = max(colBest[c], results[t]);
ans = max(ans, results[t]);
}
i = j;
}
return ans;
}JavaScript
var maxIncreasingCells = function(mat) {
var m = mat.length, n = mat[0].length, total = m * n, order = [];
for (var t = 0; t < total; t++) order.push(t);
order.sort(function(a, b) {
return mat[(a / n) | 0][a % n] - mat[(b / n) | 0][b % n];
});
var rowBest = new Array(m).fill(0), colBest = new Array(n).fill(0), ans = 0;
var results = new Array(total);
for (var i = 0; i < total;) {
var v = mat[(order[i] / n) | 0][order[i] % n], j = i;
while (j < total && mat[(order[j] / n) | 0][order[j] % n] === v) j++;
for (var t = i; t < j; t++) {
var r = (order[t] / n) | 0, c = order[t] % n;
results[t] = 1 + Math.max(rowBest[r], colBest[c]);
}
for (var t = i; t < j; t++) {
var r = (order[t] / n) | 0, c = order[t] % n, best = results[t];
if (best > rowBest[r]) rowBest[r] = best;
if (best > colBest[c]) colBest[c] = best;
if (best > ans) ans = best;
}
i = j;
}
return ans;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets