Maximum Strictly Increasing Cells in a Matrix

Hard
1634.

Maximum Strictly Increasing Cells in a Matrix

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.

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.length
  • n == mat[i].length
  • 1 <= m, n <= 10^5
  • 1 <= m * n <= 10^5
  • -10^5 <= mat[i][j] <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} mat
 * @return {number}
 */
var maxIncreasingCells = function(mat) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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.length
  • n == mat[i].length
  • 1 <= m, n <= 10^5
  • 1 <= m * n <= 10^5
  • -10^5 <= mat[i][j] <= 10^5

Hints for Maximum Strictly Increasing Cells in a Matrix

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

  2. Hint 2

    Keep rowBest[r] = the longest path ending at any processed cell of row r, and colBest[c] likewise. A cell's best is 1 + max(rowBest[r], colBest[c]).

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

  1. Sort all cells by value.
  2. Walk the sorted cells one group of equal values at a time.
  3. For each cell (r, c) in the group, compute best = 1 + max(rowBest[r], colBest[c]) from the arrays as they were before the group.
  4. Then apply the group: rowBest[r] = max(rowBest[r], best) and colBest[c] = max(colBest[c], best); track the overall maximum.
  5. 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/colBest immediately 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 allocate m × n by max(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 ans

Java

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