2713. Maximum Strictly Increasing Cells in a Matrix

Description

Given a 1-indexed m x n integer matrix mat, you can select any cell in the matrix as your starting cell.

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

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

Return an integer denoting the maximum number of cells that can be visited.

 

Example 1:

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

Example 2:

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

Example 3:

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

 

Constraints:

• m == mat.length 
• n == mat[i].length 
• 1 <= m, n <= 105
• 1 <= m * n <= 105
• -105 <= mat[i][j] <= 105

Solutions

Solution 1: Sorting + Dynamic Programming

Based on the problem description, the value of the cells we move through in sequence must strictly increase. Therefore, we can use a hash table $g$ to record the positions of all cells corresponding to each value, and then traverse from the smallest to the largest value.

During this process, we can maintain two arrays rowMax and colMax, which record the maximum increasing length of each row and column, respectively. Initially, all elements of these two arrays are $0$.

For all cell positions corresponding to each value, we traverse them in order of position. For each position $(i, j)$, we can calculate the maximum increasing length ending at that position as $1 + \max(\textit{rowMax}[i], \textit{colMax}[j])$, update the answer, and then update rowMax[i] and colMax[j].

Finally, return the answer.

The time complexity is $O(m \times n \times \log(m \times n))$, and the space complexity is $O(m \times n)$.

Python3JavaC++GoTypeScript

class Solution:
    def maxIncreasingCells(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        g = defaultdict(list)
        for i in range(m):
            for j in range(n):
                g[mat[i][j]].append((i, j))
        rowMax = [0] * m
        colMax = [0] * n
        ans = 0
        for _, pos in sorted(g.items()):
            mx = []
            for i, j in pos:
                mx.append(1 + max(rowMax[i], colMax[j]))
                ans = max(ans, mx[-1])
            for k, (i, j) in enumerate(pos):
                rowMax[i] = max(rowMax[i], mx[k])
                colMax[j] = max(colMax[j], mx[k])
        return ans

class Solution {
    public int maxIncreasingCells(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        TreeMap<Integer, List<int[]>> g = new TreeMap<>();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                g.computeIfAbsent(mat[i][j], k -> new ArrayList<>()).add(new int[] {i, j});
            }
        }
        int[] rowMax = new int[m];
        int[] colMax = new int[n];
        int ans = 0;
        for (var e : g.entrySet()) {
            var pos = e.getValue();
            int[] mx = new int[pos.size()];
            int k = 0;
            for (var p : pos) {
                int i = p[0], j = p[1];
                mx[k] = Math.max(rowMax[i], colMax[j]) + 1;
                ans = Math.max(ans, mx[k++]);
            }
            for (k = 0; k < mx.length; ++k) {
                int i = pos.get(k)[0], j = pos.get(k)[1];
                rowMax[i] = Math.max(rowMax[i], mx[k]);
                colMax[j] = Math.max(colMax[j], mx[k]);
            }
        }
        return ans;
    }
}

class Solution {
public:
    int maxIncreasingCells(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        map<int, vector<pair<int, int>>> g;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                g[mat[i][j]].emplace_back(i, j);
            }
        }
        vector<int> rowMax(m);
        vector<int> colMax(n);
        int ans = 0;
        for (auto& [_, pos] : g) {
            vector<int> mx;
            for (auto& [i, j] : pos) {
                mx.push_back(max(rowMax[i], colMax[j]) + 1);
                ans = max(ans, mx.back());
            }
            for (int k = 0; k < mx.size(); ++k) {
                auto& [i, j] = pos[k];
                rowMax[i] = max(rowMax[i], mx[k]);
                colMax[j] = max(colMax[j], mx[k]);
            }
        }
        return ans;
    }
};

func maxIncreasingCells(mat [][]int) (ans int) {
    m, n := len(mat), len(mat[0])
    g := map[int][][2]int{}
    for i, row := range mat {
        for j, v := range row {
            g[v] = append(g[v], [2]int{i, j})
        }
    }
    nums := make([]int, 0, len(g))
    for k := range g {
        nums = append(nums, k)
    }
    sort.Ints(nums)
    rowMax := make([]int, m)
    colMax := make([]int, n)
    for _, k := range nums {
        pos := g[k]
        mx := make([]int, len(pos))
        for i, p := range pos {
            mx[i] = max(rowMax[p[0]], colMax[p[1]]) + 1
            ans = max(ans, mx[i])
        }
        for i, p := range pos {
            rowMax[p[0]] = max(rowMax[p[0]], mx[i])
            colMax[p[1]] = max(colMax[p[1]], mx[i])
        }
    }
    return
}

function maxIncreasingCells(mat: number[][]): number {
    const m = mat.length;
    const n = mat[0].length;
    const g: { [key: number]: [number, number][] } = {};

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (!g[mat[i][j]]) {
                g[mat[i][j]] = [];
            }
            g[mat[i][j]].push([i, j]);
        }
    }

    const rowMax = Array(m).fill(0);
    const colMax = Array(n).fill(0);
    let ans = 0;

    const sortedKeys = Object.keys(g)
        .map(Number)
        .sort((a, b) => a - b);

    for (const key of sortedKeys) {
        const pos = g[key];
        const mx: number[] = [];

        for (const [i, j] of pos) {
            mx.push(1 + Math.max(rowMax[i], colMax[j]));
            ans = Math.max(ans, mx[mx.length - 1]);
        }

        for (let k = 0; k < pos.length; k++) {
            const [i, j] = pos[k];
            rowMax[i] = Math.max(rowMax[i], mx[k]);
            colMax[j] = Math.max(colMax[j], mx[k]);
        }
    }

    return ans;
}

Comments