2713. Maximum Strictly Increasing Cells in a Matrix
Problem Description
In this problem, we are given a 2D integer matrix where each index is 1-indexed, meaning that the top-left corner of the matrix starts at 1,1 instead of the usual 0,0 in programming. The challenge is to start from any cell within this matrix and move to any other cell in the same row or column. However, there is a condition for movement: you can only move to a cell if its value is strictly greater than the value of the current cell. This process continues until there are no more valid moves left.
The objective is to find the longest possible path through the matrix following the movement rule, and to return the number of cells visited during this path. This maximum number should represent the greatest possible number of cells one could visit starting from any cell in the matrix.
Intuition
The intuition behind the solution is to leverage the fact that we can only move to strictly greater cells. This imposes a natural order of movement from smaller to larger values. Therefore, all potential paths will have an increasing trend.
The solution approach involves dynamic programming; specifically, we follow these steps:
- Use a graph model where each node represents a cell (i, j) and its value mat[i][j]. We must identify all potential moves from each cell.
- Sort the nodes based on their values. Since we move from smaller to larger values, processing the nodes in increasing order ensures that by the time we process a cell, all potential moves into this cell have already been considered.
- For all cells with the same value (possible since values may repeat), compute the length of the longest path ending in each cell. We can do this efficiently by keeping track of the maximum path length seen so far in each row and column.
- Update the global maximum path length as the maximum of the result for each cell.
By processing cells in non-decreasing order and updating row and column maximums, we ensure that every possible move is accounted for, and we avoid double-counting. This way, we arrive at the optimal solution which is the maximum number of cells one can visit.
Learn more about Memoization, Binary Search, Dynamic Programming and Sorting patterns.
Solution Approach
The implementation of the solution follows these steps:
-
Graph Representation: The matrix is conceptualized as a graph where each cell is a node that can potentially connect to other nodes in its row and column if they contain larger values.
-
Preprocessing: A dictionary,
g
, is created to group cells by their values, with each value as a key and a list of tuples (coordinates of the cells) as the value.g = defaultdict(list) for i in range(m): for j in range(n): g[mat[i][j]].append((i, j))
-
Higher-Level Dynamic Programming Storage: Two lists,
rowMax
andcolMax
, are initialized to keep track of the maximum path length seen so far for each row and column, respectively.rowMax = [0] * m colMax = [0] * n
-
Iterate Over Cells by Increasing Values: Sort the keys of
g
which represent cell values to process cells in non-decreasing order.for _, pos in sorted(g.items()):
-
Local Dynamic Programming Computation: As each cell is processed, the maximum length of the path ending at that cell is computed using the previously stored values in
rowMax
andcolMax
.mx = [] # Local maximum path lengths for cells with the same value. for i, j in pos: mx.append(1 + max(rowMax[i], colMax[j])) ans = max(ans, mx[-1])
-
Global Maximum Path Update: After processing cells of the same value, update
rowMax
andcolMax
with the new maximum path lengths.for k, (i, j) in enumerate(pos): rowMax[i] = max(rowMax[i], mx[k]) colMax[j] = max(colMax[j], mx[k])
-
Result: Once all cells have been processed,
ans
will contain the maximum number of cells that can be visited starting from any cell in the matrix, which is then returned.
The dynamic programming pattern leveraged in "Local Dynamic Programming Computation" and "Global Maximum Path Update" is crucial as it guarantees the path length is calculated correctly while ensuring that each cell is considered once, and in the right order. This allows for the solution to have a time complexity of O(m * n * log(m * n))
due to the sorting step, where m
and n
are the number of rows and columns of the matrix, respectively.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach.
Suppose our matrix is:
3 4 5 3 2 6 2 2 1
This is a 3x3 matrix with the top-left cell starting at index 1,1. Now, let's apply the solution approach:
-
Graph Representation: Each cell can be thought of as a node. We will move only to nodes with larger values.
-
Preprocessing: We create a dictionary to group cells by their values.
- For the value 1:
g[1] = [(2, 2)]
- For the value 2:
g[2] = [(2, 0), (2, 1)]
- For the value 3:
g[3] = [(0, 0), (1, 0)]
- For the value 4:
g[4] = [(0, 1)]
- For the value 5:
g[5] = [(0, 2)]
- For the value 6:
g[6] = [(1, 2)]
- For the value 1:
-
Higher-Level Dynamic Programming Storage: Initialize the
rowMax
andcolMax
.rowMax = [0, 0, 0]
for three rowscolMax = [0, 0, 0]
for three columns
-
Iterate Over Cells by Increasing Values: We process the list of cell positions in ascending order of their values.
-
Local Dynamic Programming Computation: Calculate the maximum path length for each cell.
- Starting with value 1:
g[1] = [(2, 2)]
, we have no prior larger values, so the length is 1 forrowMax[2]
andcolMax[2]
. - For value 2:
g[2] = [(2, 0), (2, 1)]
, since they follow value 1, the length for both is 1. UpdaterowMax[2]
to 1. - For value 3:
g[3] = [(0, 0), (1, 0)]
, no larger prior values are in the same row or column. The length remains 1 and updatesrowMax[0]
androwMax[1]
. - For value 4:
g[4] = [(0, 1)]
, it can only come from(0, 0)
which has a value 3. The length is1 + rowMax[0]
, so 2. UpdatecolMax[1]
with 2. - For value 5:
g[5] = [(0, 2)]
, could come from(0, 1)
which has value 4. The length becomes1 + colMax[1]
, so 3. UpdatecolMax[2]
with 3. - For value 6:
g[6] = [(1, 2)]
, could have moved from(0, 2)
with value 5. Therefore, length is1 + colMax[2]
, resulting in 4. This is now ourans
.
- Starting with value 1:
-
Global Maximum Path Update: After processing,
rowMax
andcolMax
have been updated with the maximum path lengths as shown during the computation. -
Result: The maximum number of cells visited is 4, starting from cell
(1, 2)
(1-indexed) and moving through cells(0, 2)
,(0, 1)
, and(0, 0)
in that order, following increasing cell values.
The careful consideration of cell values and ensuring we process them from smallest to largest while updating path lengths as we go allows us to determine the maximum visitable path efficiently.
Solution Implementation
1from collections import defaultdict
2
3class Solution:
4 def max_increasing_cells(self, matrix):
5 # Determine the size of the matrix
6 rows, cols = len(matrix), len(matrix[0])
7
8 # Create a dictionary to hold cell values and their positions
9 value_to_positions = defaultdict(list)
10
11 # Populate the dictionary with positions for each value in the matrix
12 for i in range(rows):
13 for j in range(cols):
14 value_to_positions[matrix[i][j]].append((i, j))
15
16 # Initialize arrays to keep track of maximum increasing path length ending at any row or column
17 max_row_length = [0] * rows
18 max_col_length = [0] * cols
19
20 # Variable to keep track of the maximum length of increasing cells found
21 max_length = 0
22
23 # Process cells in ascending order of their values
24 for _, positions in sorted(value_to_positions.items()):
25 current_max = []
26 # Calculate the maximum length for the current set of cells with the same value
27 for i, j in positions:
28 increase_amount = 1 + max(max_row_length[i], max_col_length[j])
29 current_max.append(increase_amount)
30 # Update the overall max_length
31 max_length = max(max_length, increase_amount)
32
33 # Update the max_row_length and max_col_length for the current set of cells
34 for index, (i, j) in enumerate(positions):
35 max_row_length[i] = max(max_row_length[i], current_max[index])
36 max_col_length[j] = max(max_col_length[j], current_max[index])
37
38 # Return the maximum length of the increasing cells path found
39 return max_length
40
1class Solution {
2 public int maxIncreasingCells(int[][] mat) {
3 // Dimensions of the matrix
4 int rows = mat.length;
5 int cols = mat[0].length;
6
7 // TreeMap to organize cells by their values (handles sorting automatically)
8 TreeMap<Integer, List<int[]>> valueToCellsMap = new TreeMap<>();
9
10 // Fill the TreeMap with cells, where each cell is represented by its coordinates [i, j]
11 for (int i = 0; i < rows; ++i) {
12 for (int j = 0; j < cols; ++j) {
13 valueToCellsMap.computeIfAbsent(mat[i][j], k -> new ArrayList<>()).add(new int[]{i, j});
14 }
15 }
16
17 // Arrays to track the maximum increase count per row and column
18 int[] rowMaxIncrements = new int[rows];
19 int[] colMaxIncrements = new int[cols];
20
21 // Variable to store the final answer, which is the maximum length of increasing path
22 int maxLengthOfIncreasingPath = 0;
23
24 // Iterate through the TreeMap, processing cells in ascending order of their values
25 for (var entry : valueToCellsMap.entrySet()) {
26 var cells = entry.getValue();
27 int[] localMaxIncrements = new int[cells.size()];
28 int index = 0; // Used to update localMaxIncrements as we iterate through cells
29
30 // Determine the maximum increasing path ending at each cell based on previous rows/cols
31 for (var cell : cells) {
32 int row = cell[0];
33 int col = cell[1];
34 localMaxIncrements[index] = Math.max(rowMaxIncrements[row], colMaxIncrements[col]) + 1;
35 maxLengthOfIncreasingPath = Math.max(maxLengthOfIncreasingPath, localMaxIncrements[index]);
36 index++;
37 }
38
39 // Update the rowMaxIncrements and colMaxIncrements arrays based on the new localMaxIncrements
40 for (index = 0; index < localMaxIncrements.length; ++index) {
41 int rowToUpdate = cells.get(index)[0];
42 int colToUpdate = cells.get(index)[1];
43 rowMaxIncrements[rowToUpdate] = Math.max(rowMaxIncrements[rowToUpdate], localMaxIncrements[index]);
44 colMaxIncrements[colToUpdate] = Math.max(colMaxIncrements[colToUpdate], localMaxIncrements[index]);
45 }
46 }
47 // Return the maximum length of the increasing path found
48 return maxLengthOfIncreasingPath;
49 }
50}
51
1class Solution {
2public:
3 // Function to find the length of the longest strictly increasing path in the matrix
4 int maxIncreasingCells(vector<vector<int>>& matrix) {
5 int rows = matrix.size(); // Number of rows in the matrix
6 int cols = matrix[0].size(); // Number of columns in the matrix
7
8 // Map to hold the matrix values as keys and their corresponding positions as values
9 map<int, vector<pair<int, int>>> valueToPositions;
10
11 // Populate the map with the matrix values and their positions
12 for (int i = 0; i < rows; ++i) {
13 for (int j = 0; j < cols; ++j) {
14 valueToPositions[matrix[i][j]].emplace_back(i, j);
15 }
16 }
17
18 // Vectors to keep track of the max path length for each row and column
19 vector<int> rowMax(rows, 0);
20 vector<int> colMax(cols, 0);
21
22 int maxLength = 0; // Variable to store the length of the longest path found
23
24 // Process each group of positions belonging to the same value in increasing order
25 for (auto& valueAndPositions : valueToPositions) {
26 vector<int> currentMaxLengths;
27 for (auto& [row, col] : valueAndPositions.second) {
28 // Calculate the max path length at the current position
29 currentMaxLengths.push_back(max(rowMax[row], colMax[col]) + 1);
30 // Update the overall max length found so far
31 maxLength = max(maxLength, currentMaxLengths.back());
32 }
33
34 // Update rowMax and colMax with the new max lengths
35 for (int k = 0; k < currentMaxLengths.size(); ++k) {
36 auto& [row, col] = valueAndPositions.second[k];
37 rowMax[row] = max(rowMax[row], currentMaxLengths[k]);
38 colMax[col] = max(colMax[col], currentMaxLengths[k]);
39 }
40 }
41
42 return maxLength; // Return the length of the longest strictly increasing path
43 }
44};
45
1// Define the type alias for a matrix
2type Matrix = number[][];
3
4// Define the type alias for positions which is an array of tuples with row and column
5type Positions = Array<[number, number]>;
6
7// Function to find the length of the longest strictly increasing path in the matrix
8function maxIncreasingCells(matrix: Matrix): number {
9 const rows = matrix.length; // Number of rows in the matrix
10 const cols = matrix[0].length; // Number of columns in the matrix
11
12 // Map to hold the matrix values as keys and their corresponding positions as values
13 const valueToPositions = new Map<number, Positions>();
14
15 // Populate the map with the matrix values and their positions
16 for (let i = 0; i < rows; ++i) {
17 for (let j = 0; j < cols; ++j) {
18 const value = matrix[i][j];
19 if (!valueToPositions.has(value)) {
20 valueToPositions.set(value, []);
21 }
22 valueToPositions.get(value)!.push([i, j]);
23 }
24 }
25
26 // Arrays to keep track of the max path length for each row and column
27 const rowMax: number[] = new Array(rows).fill(0);
28 const colMax: number[] = new Array(cols).fill(0);
29
30 let maxLength = 0; // Variable to store the length of the longest path found
31
32 // Process each group of positions belonging to the same value in increasing order of values
33 Array.from(valueToPositions.keys())
34 .sort((a, b) => a - b) // Ensure that keys/values are processed in sorted order
35 .forEach(value => {
36 const positions = valueToPositions.get(value)!;
37 const currentMaxLengths: number[] = [];
38
39 positions.forEach(([row, col]) => {
40 // Calculate the max path length at the current position
41 const currentLength = Math.max(rowMax[row], colMax[col]) + 1;
42 currentMaxLengths.push(currentLength);
43 // Update the overall max length found so far
44 maxLength = Math.max(maxLength, currentLength);
45 });
46
47 // Update rowMax and colMax with the new max lengths
48 positions.forEach(([row, col], k) => {
49 rowMax[row] = Math.max(rowMax[row], currentMaxLengths[k]);
50 colMax[col] = Math.max(colMax[col], currentMaxLengths[k]);
51 });
52 });
53
54 return maxLength; // Return the length of the longest strictly increasing path
55}
56
Time and Space Complexity
The time complexity of the given code can be broken down into a few parts:
-
Building the graph
g
: We iterate over all the elements in themat
, which has a size ofm*n
. For each element, we perform a constant-time operation (append
). Thus, this part of the algorithm runs inO(m*n)
time. -
Sorting the keys of the graph
g
: Sinceg
can have at mostm*n
unique keys (in the worst case where all elements are unique), the time complexity of sorting these keys isO(m*n*log(m*n))
. -
Calculating the maximum increasing path: We iterate again over the entries sorted in
g
. For each value, we iterate over all positions with that value and updaterowMax
andcolMax
. The inner loop will run at mostm*n
times in total. For each inner loop, updatingrowMax
andcolMax
is a constant-time operation. Hence, the time complexity for this part isO(m*n)
.
Combining all the steps, the total time complexity of the code is dominated by the sorting step, so it is O(m*n*log(m*n))
.
The space complexity of the given code can be analyzed as follows:
-
The graph
g
, which in the worst case, containsm*n
keys with a single-value list, leading to a space complexity ofO(m*n)
. -
The
rowMax
andcolMax
arrays, which add up to a space complexity ofO(m + n)
. -
The
mx
list, which within a single iteration overg
's keys, in the worst case, might store up tomin(m, n)
elements (in the case of all positions having the same value), so its space complexity isO(min(m, n))
.
Therefore, the total space complexity, considering the space required for input and auxiliary space, is O(m*n + m + n)
, which simplifies to O(m*n)
as it is the dominating term.
Learn more about how to find time and space complexity quickly using problem constraints.
Which data structure is used in a depth first search?
Recommended Readings
Memoization Prereq Backtracking problems backtracking Memoization is a fancy word for a simple concept so is the case for a lot of things we learn in school It means saving the previous function call result in a dictionary and reading from it when we do the exact same call again
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Want a Structured Path to Master System Design Too? Donāt Miss This!