Skip to content

2713. Maximum Strictly Increasing Cells in a Matrix 👍

  • Time: $O(mn\log mn)$
  • Space: $O(mn)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
 public:
  int maxIncreasingCells(vector<vector<int>>& mat) {
    const int m = mat.size();
    const int n = mat[0].size();
    vector<int> rows(m);  // rows[i] := max path length for i-th row
    vector<int> cols(n);  // cols[j] := max path length for j-th col
    unordered_map<int, vector<pair<int, int>>> valToIndices;
    // maxPathLength[i][j] := max path length from mat[i][j]
    vector<vector<int>> maxPathLength(m, vector<int>(n));
    // all unique values in the matrix in non-increasing order
    set<int, greater<>> decreasingSet;

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j) {
        valToIndices[mat[i][j]].emplace_back(i, j);
        decreasingSet.insert(mat[i][j]);
      }

    for (const int val : decreasingSet) {
      for (const auto& [i, j] : valToIndices[val])
        maxPathLength[i][j] = max(rows[i], cols[j]) + 1;
      for (const auto& [i, j] : valToIndices[val]) {
        rows[i] = max(rows[i], maxPathLength[i][j]);
        cols[j] = max(cols[j], maxPathLength[i][j]);
      }
    }

    return max(*max_element(rows.begin(), rows.end()),
               *max_element(cols.begin(), cols.end()));
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
  public int maxIncreasingCells(int[][] mat) {
    final int m = mat.length;
    final int n = mat[0].length;
    int[] rows = new int[m]; // rows[i] := max path length for i-th row
    int[] cols = new int[n]; // cols[j] := max path length for j-th col
    Map<Integer, ArrayList<Pair<Integer, Integer>>> valToIndices = new HashMap<>();
    // maxPathLength[i][j] := max path length from mat[i][j]
    int[][] maxPathLength = new int[m][n];
    // all unique values in the matrix in non-increasing order
    TreeSet<Integer> decreasingSet = new TreeSet<>(Comparator.reverseOrder());

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j) {
        final int val = mat[i][j];
        valToIndices.putIfAbsent(val, new ArrayList<>());
        valToIndices.get(val).add(new Pair<>(i, j));
        decreasingSet.add(val);
      }

    for (final int val : decreasingSet) {
      for (Pair<Integer, Integer> pair : valToIndices.get(val)) {
        final int i = pair.getKey();
        final int j = pair.getValue();
        maxPathLength[i][j] = Math.max(rows[i], cols[j]) + 1;
      }
      for (Pair<Integer, Integer> pair : valToIndices.get(val)) {
        final int i = pair.getKey();
        final int j = pair.getValue();
        rows[i] = Math.max(rows[i], maxPathLength[i][j]);
        cols[j] = Math.max(cols[j], maxPathLength[i][j]);
      }
    }

    return Math.max(Arrays.stream(rows).max().getAsInt(), //
                    Arrays.stream(cols).max().getAsInt());
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
  def maxIncreasingCells(self, mat: List[List[int]]) -> int:
    m = len(mat)
    n = len(mat[0])
    rows = [0] * m  # rows[i] := max path length for i-th row
    cols = [0] * n  # cols[j] := max path length for j-th col
    valToIndices = collections.defaultdict(list)
    # maxPathLength[i][j] := max path length from mat[i][j]
    maxPathLength = [[0] * n for _ in range(m)]
    # all unique values in the matrix in non-increasing order
    decreasingSet = set()

    for i in range(m):
      for j in range(n):
        val = mat[i][j]
        valToIndices[val].append((i, j))
        decreasingSet.add(val)

    for val in sorted(decreasingSet, reverse=True):
      for i, j in valToIndices[val]:
        maxPathLength[i][j] = max(rows[i], cols[j]) + 1
      for i, j in valToIndices[val]:
        rows[i] = max(rows[i], maxPathLength[i][j])
        cols[j] = max(cols[j], maxPathLength[i][j])

    return max(max(rows), max(cols))