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:

  1. 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.
  2. 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.
  3. 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.
  4. 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:

  1. 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.

  2. 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))
  3. Higher-Level Dynamic Programming Storage: Two lists, rowMax and colMax, 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
  4. 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()):
  5. 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 and colMax.

    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])
  6. Global Maximum Path Update: After processing cells of the same value, update rowMax and colMax 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])
  7. 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 Evaluator

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

  1. Graph Representation: Each cell can be thought of as a node. We will move only to nodes with larger values.

  2. 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)]
  3. Higher-Level Dynamic Programming Storage: Initialize the rowMax and colMax.

    • rowMax = [0, 0, 0] for three rows
    • colMax = [0, 0, 0] for three columns
  4. Iterate Over Cells by Increasing Values: We process the list of cell positions in ascending order of their values.

  5. 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 for rowMax[2] and colMax[2].
    • For value 2: g[2] = [(2, 0), (2, 1)], since they follow value 1, the length for both is 1. Update rowMax[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 updates rowMax[0] and rowMax[1].
    • For value 4: g[4] = [(0, 1)], it can only come from (0, 0) which has a value 3. The length is 1 + rowMax[0], so 2. Update colMax[1] with 2.
    • For value 5: g[5] = [(0, 2)], could come from (0, 1) which has value 4. The length becomes 1 + colMax[1], so 3. Update colMax[2] with 3.
    • For value 6: g[6] = [(1, 2)], could have moved from (0, 2) with value 5. Therefore, length is 1 + colMax[2], resulting in 4. This is now our ans.
  6. Global Maximum Path Update: After processing, rowMax and colMax have been updated with the maximum path lengths as shown during the computation.

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

  1. Building the graph g: We iterate over all the elements in the mat, which has a size of m*n. For each element, we perform a constant-time operation (append). Thus, this part of the algorithm runs in O(m*n) time.

  2. Sorting the keys of the graph g: Since g can have at most m*n unique keys (in the worst case where all elements are unique), the time complexity of sorting these keys is O(m*n*log(m*n)).

  3. 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 update rowMax and colMax. The inner loop will run at most m*n times in total. For each inner loop, updating rowMax and colMax is a constant-time operation. Hence, the time complexity for this part is O(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:

  1. The graph g, which in the worst case, contains m*n keys with a single-value list, leading to a space complexity of O(m*n).

  2. The rowMax and colMax arrays, which add up to a space complexity of O(m + n).

  3. The mx list, which within a single iteration over g's keys, in the worst case, might store up to min(m, n) elements (in the case of all positions having the same value), so its space complexity is O(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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which data structure is used in a depth first search?


Recommended Readings

Want a Structured Path to Master System Design Too? Donā€™t Miss This!


Load More