# Maximum Strictly Increasing Cells in a Matrix
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-strictly-increasing-cells-in-a-matrix)
Canonical: https://scaleengineer.com/dsa/problems/maximum-strictly-increasing-cells-in-a-matrix
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Memoization](https://scaleengineer.com/dsa/patterns/memoization)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table, Matrix, Ordered Set
---
## Problem
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:**

**![](https://assets.glich.co/dsa/maximum-strictly-increasing-cells-in-a-matrix/image0.png)**

**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:**

**![](https://assets.glich.co/dsa/maximum-strictly-increasing-cells-in-a-matrix/image1.png)**

**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:**

**![](https://assets.glich.co/dsa/maximum-strictly-increasing-cells-in-a-matrix/image2.png)**

**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`

# Approaches
## DFS with Memoization
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).
**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.
**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.
### Explanation
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:
1.  If `dp[r][c]` is not 0, it means we have already computed the result, so we return it.
2.  Otherwise, we initialize the path length for the current cell to 1 (for the cell itself), `maxLength = 1`.
3.  We then explore all valid moves:
    *   Iterate through all other cells `(r, j)` in the same row `r`. If `mat[r][j] > mat[r][c]`, we can move there. We recursively call `dfs(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 column `c`. If `mat[i][c] > mat[r][c]`, we update `maxLength = max(maxLength, 1 + dfs(i, c))`.
4.  After checking all possible moves, we store the computed `maxLength` in `dp[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.

```java
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;
    }
}
```
### 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 `dfs` for each one, and returns the maximum length found.

## Dynamic Programming with Sorting
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.
**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.
**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.
### Explanation
1.  First, we group all cell coordinates by their value using a `TreeMap`. A `TreeMap` is used because it automatically sorts the entries by their keys (the cell values), which is essential for our DP approach.
2.  We use a 2D DP table `dp[m][n]`, where `dp[i][j]` will store the length of the longest increasing path *ending* at cell `(i, j)`.
3.  We also maintain two auxiliary arrays, `maxLenRow[m]` and `maxLenCol[n]`. `maxLenRow[i]` stores the maximum path length found so far for any cell in row `i`, and `maxLenCol[j]` does the same for column `j`. These arrays help us quickly find the length of the best path we can extend.
4.  A critical detail is handling cells with the same value. We cannot update `maxLenRow` and `maxLenCol` immediately 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).
5.  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 its `dp` value: `dp[r][c] = 1 + max(maxLenRow[r], maxLenCol[c])`. Here, `maxLenRow` and `maxLenCol` hold the maximums from cells with values *strictly smaller* than `val`.
    *   **Second Pass (Update max lengths):** After computing the `dp` values for all cells in the current block, we iterate through them again to update `maxLenRow[r]` and `maxLenCol[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.
6.  The overall maximum value computed in the `dp` table is the answer.

```java
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;
    }
}
```
### Algorithm
- Create a `TreeMap` to group cell coordinates by their values. The `TreeMap` naturally 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]` and `maxLenCol[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 `TreeMap` entries (which are sorted by value).
- For each value and its list of associated cells, perform a two-pass process:
  1. **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.
  2. **Second Pass:** After computing the `dp` values for all cells in the group, iterate through them again to update the `maxLenRow` and `maxLenCol` arrays with the new maximums. `maxLenRow[r] = max(maxLenRow[r], dp[r][c])` and `maxLenCol[c] = max(maxLenCol[c], dp[r][c])`.
- Keep track of the overall maximum `dp` value found, which will be the final answer.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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 ans

```