Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

2818. Maximum Strictly Increasing Cells in a Matrix

My accepted Python solution to LeetCode problem 2818, Maximum Strictly Increasing Cells in a Matrix, running in 723ms.

  • Difficulty: Hard
  • Python
  • Runtime 723ms
  • Memory 71.9MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 723ms, memory 71.9MB, accepted 2026-01-01.

python
class Solution:
    def maxIncreasingCells(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        
        # Group cells by value
        cells = defaultdict(list)
        for i in range(m):
            for j in range(n):
                cells[mat[i][j]].append((i, j))
        
        # row_max[i] = max path length ending at row i
        # col_max[j] = max path length ending at col j
        row_max = [0] * m
        col_max = [0] * n
        
        # dp[i][j] = max path length ending at cell (i,j)
        dp = [[0] * n for _ in range(m)]
        
        # Process cells in sorted order of values
        for val in sorted(cells.keys()):
            # First calculate dp values for all cells with this value
            updates = []
            for i, j in cells[val]:
                dp[i][j] = max(row_max[i], col_max[j]) + 1
                updates.append((i, j, dp[i][j]))
            
            # Then update row_max and col_max
            for i, j, v in updates:
                row_max[i] = max(row_max[i], v)
                col_max[j] = max(col_max[j], v)
        
        return max(max(row) for row in dp)

Source