<p>Given a <strong>1-indexed</strong>&nbsp;<code>m x n</code> integer matrix <code>mat</code>, you can select any cell in the matrix as your <strong>starting cell</strong>.</p>

<p>From the starting cell, you can move to any other cell <strong>in the</strong> <strong>same row or column</strong>, but only if the value of the destination cell is <strong>strictly greater</strong> 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.</p>

<p>Your task is to find the <strong>maximum number of cells</strong> that you can visit in the matrix by starting from some cell.</p>

<p>Return <em>an integer denoting the maximum number of cells that can be visited.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<p><strong class="example"><img alt="" src="https://assets.leetcode.com/uploads/2023/04/23/diag1drawio.png" style="width: 200px; height: 176px;" /></strong></p>

<pre>
<strong>Input:</strong> mat = [[3,1],[3,4]]
<strong>Output:</strong> 2
<strong>Explanation:</strong> 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. 
</pre>

<p><strong class="example">Example 2:</strong></p>

<p><strong class="example"><img alt="" src="https://assets.leetcode.com/uploads/2023/04/23/diag3drawio.png" style="width: 200px; height: 176px;" /></strong></p>

<pre>
<strong>Input:</strong> mat = [[1,1],[1,1]]
<strong>Output:</strong> 1
<strong>Explanation:</strong> Since the cells must be strictly increasing, we can only visit one cell in this example. 
</pre>

<p><strong class="example">Example 3:</strong></p>

<p><strong class="example"><img alt="" src="https://assets.leetcode.com/uploads/2023/04/23/diag4drawio.png" style="width: 350px; height: 250px;" /></strong></p>

<pre>
<strong>Input:</strong> mat = [[3,1,6],[-9,5,7]]
<strong>Output:</strong> 4
<strong>Explanation:</strong> 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. 
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == mat.length&nbsp;</code></li>
	<li><code>n == mat[i].length&nbsp;</code></li>
	<li><code>1 &lt;= m, n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= m * n &lt;= 10<sup>5</sup></code></li>
	<li><code>-10<sup>5</sup>&nbsp;&lt;= mat[i][j] &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution:
    def maxIncreasingCells(self, mat: List[List[int]]) -> int:
        """
        My immediate intuition is to use Dynamic Programming.
        It may also be a search problem, but since we have an obviously
        fixed number of cells in the matrix, we can store the maximum
        number of cells we can visit by starting from some cell.

        It seems like we could sort the cells by their value in
        decreasing order.
        Starting with the largest value, we can find the number of cells
        we can visit using ONLY the precomputed values, which is all
        that we need, since we can only go to other cells which are
        strictly greater.

        Thus, given a cell, we can look at all of the other cells in the
        same row and column, and if they have been computed already and
        their value is strictly greater, then the value at this cell is
        the maximum found in either the row or the column plus 1.

        Noting this, we don't really need to go through all of the cells
        in the rows and columns if we are only looking for the maximum.
        We can store the maximums as we go.
        However, we need to be careful that we don't update the maximums
        prematurely, as the values in sequence need to be strictly increasing.
        """
        # Stores (value, i_row, i_col)
        cells_to_visit = []

        for i_row in range(len(mat)):
            for i_col in range(len(mat[i_row])):
                cells_to_visit.append((mat[i_row][i_col], i_row, i_col))

        cells_to_visit.sort(reverse=True)

        row_max = [0] * len(mat)
        col_max = [0] * len(mat[0])
        overall_max = 0

        # Stores (value, i_row_max, i_col_max)
        updates = []

        for i in range(len(cells_to_visit)):
            value, i_row, i_col = cells_to_visit[i]

            if i > 0 and cells_to_visit[i - 1][0] > value:
                # Apply updates
                while updates:
                    max_value, i_row_max, i_col_max = updates.pop()
                    row_max[i_row_max] = max(row_max[i_row_max], max_value)
                    col_max[i_col_max] = max(col_max[i_col_max], max_value)
                    overall_max = max(
                        overall_max, row_max[i_row_max], col_max[i_col_max]
                    )

            # Create an update
            updates.append((max(row_max[i_row], col_max[i_col]) + 1, i_row, i_col))

        # Apply final updates
        while updates:
            max_value, i_row_max, i_col_max = updates.pop()
            row_max[i_row_max] = max(row_max[i_row_max], max_value)
            col_max[i_col_max] = max(col_max[i_col_max], max_value)
            overall_max = max(overall_max, row_max[i_row_max], col_max[i_col_max])

        return overall_max

51000