LeetCode 2713 - Maximum Strictly Increasing Cells in a Matrix

The problem gives us an m x n matrix where each cell contains an integer value. We may start from any cell, and from the current cell we are allowed to move only within the same row or the same column.

leetcodehardarrayhash-tablebinary-searchdynamic-programmingmemoizationsortingmatrixordered-set

LeetCode Problem 2713

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Binary Search, Dynamic Programming, Memoization, Sorting, Matrix, Ordered Set

Solution

Problem Understanding

The problem gives us an m x n matrix where each cell contains an integer value. We may start from any cell, and from the current cell we are allowed to move only within the same row or the same column.

However, there is an important restriction: we may only move to a cell whose value is strictly greater than the current cell's value.

The goal is to compute the maximum number of cells that can be visited in a valid sequence.

The matrix is conceptually 1-indexed in the statement, but that detail is irrelevant for implementation because we only care about relative positions and values.

A move from (r1, c1) to (r2, c2) is valid if:

  • r1 == r2 or c1 == c2
  • mat[r2][c2] > mat[r1][c1]

We want the longest possible strictly increasing path under these movement rules.

The constraints are the key to understanding the required efficiency:

  • 1 <= m * n <= 10^5

This means the total number of cells is at most 100000. A quadratic or cubic algorithm over all cells will be too slow.

A naive graph interpretation would connect each cell to every larger value in its row and column. In the worst case, that produces far too many edges.

Several edge cases are especially important:

  • All values equal, no movement is possible, answer is 1
  • Strictly increasing rows or columns
  • Duplicate values appearing in the same row or column
  • Negative numbers
  • Large sparse matrices where either m or n is very large
  • Multiple cells sharing the same value, which introduces an important ordering issue during dynamic programming

The duplicate value case is the most subtle. Since moves require strictly greater values, cells with the same value must never influence each other during the same update phase.

Approaches

Brute Force Approach

A straightforward approach is to treat every cell as a graph node.

For each cell, we could examine all other cells in the same row and column. If another cell has a larger value, we add a directed edge. Then we run DFS with memoization to compute the longest path starting from each cell.

This produces the correct answer because the graph is acyclic. Every move goes to a strictly larger value, so cycles are impossible.

However, the performance is unacceptable.

Suppose a row contains n cells. Every cell might connect to almost every other cell in that row. Similarly for columns. In the worst case, the number of edges becomes extremely large.

If we explicitly build transitions between cells, complexity can approach:

  • O(m * n * (m + n))

With up to 100000 cells, this is far too slow.

Key Insight

The important observation is that we do not actually need to know every transition.

Suppose we are processing a cell (r, c) with value v.

To determine the best path ending at this cell, we only need:

  • the best path among smaller values in row r
  • the best path among smaller values in column c

If we already know those two quantities, then:

dp[r][c] = 1 + max(bestRow[r], bestCol[c])

The challenge is handling duplicate values correctly.

Cells with the same value cannot transition into each other because moves must be strictly increasing. Therefore, all cells with the same value must be processed together in two phases:

  1. Compute their DP values using only previously processed smaller values
  2. Update row and column bests afterward

This naturally suggests sorting cells by value.

We process values in increasing order, using dynamic programming combined with row and column maximum trackers.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(m * n * (m + n)) O(m * n) Explicitly explores transitions between cells
Optimal O(m * n log(m * n)) O(m * n) Sort cells by value and use row/column DP maxima

Algorithm Walkthrough

  1. Create a list of all cells.

For every position (r, c), store:

(value, row, col)

We need this because the algorithm processes cells in sorted value order. 2. Sort all cells by value.

This guarantees that when processing a cell, every previously processed cell has a smaller or equal value. 3. Maintain two arrays:

  • best_row[r]
  • best_col[c]

These store the maximum DP value seen so far for each row and column using strictly smaller values. 4. Process cells grouped by equal value.

This is the most important step.

Suppose several cells all contain value 5.

We first compute DP values for all of them without updating row or column maxima yet.

This prevents equal-valued cells from incorrectly influencing each other. 5. Compute DP for each cell in the current group.

For cell (r, c):

dp = 1 + max(best_row[r], best_col[c])

This represents extending the best valid path that can move into this cell. 6. Temporarily store these DP values.

We cannot immediately update row and column maxima because another cell with the same value might incorrectly use that update. 7. After finishing the whole group, update row and column maxima.

For every computed cell:

best_row[r] = max(best_row[r], dp)
best_col[c] = max(best_col[c], dp)
  1. Track the global maximum answer.

The answer is the largest DP value among all cells.

Why it works

The algorithm processes values in strictly increasing order. Therefore, when computing a cell's DP value, best_row and best_col contain information only from smaller values.

Grouping equal values prevents illegal transitions between equal cells.

Thus every computed transition is valid, and every valid increasing path is considered through row and column maxima propagation.

This guarantees correctness.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def maxIncreasingCells(self, mat: List[List[int]]) -> int:
        rows = len(mat)
        cols = len(mat[0])

        value_to_cells = defaultdict(list)

        for r in range(rows):
            for c in range(cols):
                value_to_cells[mat[r][c]].append((r, c))

        best_row = [0] * rows
        best_col = [0] * cols

        answer = 0

        for value in sorted(value_to_cells.keys()):
            cells = value_to_cells[value]

            current_results = []

            # Compute DP values first
            for r, c in cells:
                dp = 1 + max(best_row[r], best_col[c])
                current_results.append((r, c, dp))
                answer = max(answer, dp)

            # Update row/column bests afterward
            for r, c, dp in current_results:
                best_row[r] = max(best_row[r], dp)
                best_col[c] = max(best_col[c], dp)

        return answer

The implementation begins by grouping all cells according to their values. A defaultdict(list) is ideal because many cells may share the same value.

Next, two arrays are initialized:

  • best_row
  • best_col

Each entry stores the maximum path length achieved so far for that row or column.

The algorithm then iterates through values in sorted order. This sorting step is what enforces increasing transitions.

For every group of equal-valued cells, the code first computes all DP values and stores them temporarily in current_results.

This temporary storage is essential. If we updated best_row or best_col immediately, then another cell with the same value could incorrectly use that information, violating the strictly increasing condition.

After all cells in the group have been evaluated, the updates are applied together.

Finally, the maximum DP value encountered is returned.

Go Solution

package main

import (
	"sort"
)

func maxIncreasingCells(mat [][]int) int {
	rows := len(mat)
	cols := len(mat[0])

	valueToCells := make(map[int][][]int)

	for r := 0; r < rows; r++ {
		for c := 0; c < cols; c++ {
			val := mat[r][c]
			valueToCells[val] = append(valueToCells[val], []int{r, c})
		}
	}

	values := make([]int, 0, len(valueToCells))
	for val := range valueToCells {
		values = append(values, val)
	}

	sort.Ints(values)

	bestRow := make([]int, rows)
	bestCol := make([]int, cols)

	answer := 0

	for _, val := range values {
		cells := valueToCells[val]

		type State struct {
			r  int
			c  int
			dp int
		}

		current := make([]State, 0, len(cells))

		// Compute DP values first
		for _, cell := range cells {
			r := cell[0]
			c := cell[1]

			dp := 1
			if bestRow[r] > bestCol[c] {
				dp += bestRow[r]
			} else {
				dp += bestCol[c]
			}

			current = append(current, State{r, c, dp})

			if dp > answer {
				answer = dp
			}
		}

		// Apply updates afterward
		for _, state := range current {
			if state.dp > bestRow[state.r] {
				bestRow[state.r] = state.dp
			}

			if state.dp > bestCol[state.c] {
				bestCol[state.c] = state.dp
			}
		}
	}

	return answer
}

The Go implementation follows the same logic as the Python version.

A map from value to cell coordinates replaces Python's defaultdict.

Because Go does not have tuples, small slices or structs are used to store coordinates and DP states.

The temporary State struct is important for preserving the two-phase update process.

Go integer arithmetic is safe here because the maximum path length is at most 100000, well within 32-bit integer limits.

Worked Examples

Example 1

mat = [
    [3, 1],
    [3, 4]
]

Step 1: Group by Value

Value Cells
1 (0,1)
3 (0,0), (1,0)
4 (1,1)

Initial state:

Structure Value
best_row [0, 0]
best_col [0, 0]

Process Value 1

Cell (0,1):

dp = 1 + max(best_row[0], best_col[1])
   = 1 + max(0, 0)
   = 1

Update afterward:

Structure Value
best_row [1, 0]
best_col [0, 1]

Answer = 1

Process Value 3

Cell (0,0):

dp = 1 + max(1, 0) = 2

Cell (1,0):

dp = 1 + max(0, 0) = 1

Apply updates:

Structure Value
best_row [2, 1]
best_col [2, 1]

Answer = 2

Process Value 4

Cell (1,1):

dp = 1 + max(1, 1) = 2

Final answer = 2

Example 2

mat = [
    [1,1],
    [1,1]
]

All cells belong to the same value group.

Every cell computes:

dp = 1 + max(0, 0) = 1

Since equal values cannot chain into each other, the answer remains:

1

Example 3

mat = [
    [3,1,6],
    [-9,5,7]
]

Sorted Values

-9, 1, 3, 5, 6, 7

Process -9 at (1,0)

dp = 1

Update:

best_row = [0,1]
best_col = [1,0,0]

Process 1 at (0,1)

dp = 1

Update:

best_row = [1,1]
best_col = [1,1,0]

Process 3 at (0,0)

dp = 1 + max(1,1) = 2

Update:

best_row = [2,1]
best_col = [2,1,0]

Process 5 at (1,1)

dp = 1 + max(1,1) = 2

Update:

best_row = [2,2]
best_col = [2,2,0]

Process 6 at (0,2)

dp = 1 + max(2,0) = 3

Update:

best_row = [3,2]
best_col = [2,2,3]

Process 7 at (1,2)

dp = 1 + max(2,3) = 4

Final answer:

4

Complexity Analysis

Measure Complexity Explanation
Time O(m * n log(m * n)) Sorting all cells dominates
Space O(m * n) Storage for grouped cells

The matrix contains at most 100000 cells.

Every cell is processed exactly once after sorting.

The dominant operation is sorting the distinct values or equivalently sorting all cells, which costs:

O(m * n log(m * n))

The auxiliary space consists primarily of the grouped cell storage and row/column DP arrays.

Test Cases

from typing import List

class Solution:
    def maxIncreasingCells(self, mat: List[List[int]]) -> int:
        from collections import defaultdict

        rows = len(mat)
        cols = len(mat[0])

        value_to_cells = defaultdict(list)

        for r in range(rows):
            for c in range(cols):
                value_to_cells[mat[r][c]].append((r, c))

        best_row = [0] * rows
        best_col = [0] * cols

        answer = 0

        for value in sorted(value_to_cells.keys()):
            current = []

            for r, c in value_to_cells[value]:
                dp = 1 + max(best_row[r], best_col[c])
                current.append((r, c, dp))
                answer = max(answer, dp)

            for r, c, dp in current:
                best_row[r] = max(best_row[r], dp)
                best_col[c] = max(best_col[c], dp)

        return answer

sol = Solution()

assert sol.maxIncreasingCells([[3,1],[3,4]]) == 2  # example 1
assert sol.maxIncreasingCells([[1,1],[1,1]]) == 1  # all equal
assert sol.maxIncreasingCells([[3,1,6],[-9,5,7]]) == 4  # example 3

assert sol.maxIncreasingCells([[1]]) == 1  # single cell

assert sol.maxIncreasingCells([[1,2,3,4]]) == 4  # increasing row
assert sol.maxIncreasingCells([[4,3,2,1]]) == 4  # can move backward by value

assert sol.maxIncreasingCells([
    [1],
    [2],
    [3],
    [4]
]) == 4  # increasing column

assert sol.maxIncreasingCells([
    [7,7,7],
    [7,7,7]
]) == 1  # duplicates everywhere

assert sol.maxIncreasingCells([
    [-5,-4,-3],
    [-2,-1,0]
]) == 6  # negative values

assert sol.maxIncreasingCells([
    [1,100],
    [2,3]
]) == 3  # mixed transitions

assert sol.maxIncreasingCells([
    [1,2],
    [2,3]
]) == 3  # equal values should not chain

Test Summary

Test Why
[[3,1],[3,4]] Validates basic transitions
[[1,1],[1,1]] Ensures equal values cannot chain
[[3,1,6],[-9,5,7]] Validates longer mixed path
[[1]] Smallest possible matrix
Single increasing row Ensures row traversal works
Single decreasing row Confirms movement depends on value, not direction
Single increasing column Ensures column traversal works
All duplicates Tests strict inequality handling
Negative values Confirms negatives work correctly
Mixed transitions Tests row and column interaction
Equal neighboring values Verifies group-update correctness

Edge Cases

One important edge case is when all matrix values are identical. In this situation, no move is possible because every move requires a strictly greater destination value. A buggy implementation might accidentally allow transitions between equal-valued cells if updates are applied immediately. The grouped processing strategy prevents this by ensuring equal values never influence one another during the same phase.

Another important edge case involves long monotonic rows or columns. For example, a single row like [1,2,3,4,5] should produce a path length of 5. The implementation handles this efficiently because best_row accumulates the best chain length incrementally without explicitly constructing graph edges.

Negative values are also important. Since comparisons are purely relational, the algorithm must not assume values are positive. Sorting works naturally for negative numbers, so paths like -9 -> -5 -> 0 -> 7 are handled correctly without any special logic.

A particularly subtle case occurs when multiple equal values appear in the same row or column. Suppose two cells both contain value 5. If one updates best_row before the other is processed, the second cell might incorrectly extend from the first, even though equal values are not allowed to connect. The temporary storage phase completely avoids this bug by postponing updates until the entire equal-value group has been evaluated.