2713. Maximum Strictly Increasing Cells in a Matrix LeetCode Solution
In this guide, you will get 2713. Maximum Strictly Increasing Cells in a Matrix LeetCode Solution with the best time and space complexity. The solution to Maximum Strictly Increasing Cells in a Matrix problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Maximum Strictly Increasing Cells in a Matrix solution in C++
- Maximum Strictly Increasing Cells in a Matrix solution in Java
- Maximum Strictly Increasing Cells in a Matrix solution in Python
- Additional Resources
Problem Statement of Maximum Strictly Increasing Cells in a Matrix
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
Complexity Analysis
- Time Complexity: O(mn\log mn)
- Space Complexity: O(mn)
2713. Maximum Strictly Increasing Cells in a Matrix LeetCode Solution in C++
class Solution {
public:
int maxIncreasingCells(vector<vector<int>>& mat) {
const int m = mat.size();
const int n = mat[0].size();
// rows[i] := the maximum path length for the i-th row
vector<int> rows(m);
// cols[j] := the maximum path length for the j-th column
vector<int> cols(n);
unordered_map<int, vector<pair<int, int>>> valToIndices;
// maxPathLength[i][j] := the maximum path length from mat[i][j]
vector<vector<int>> maxPathLength(m, vector<int>(n));
// Sort all the unique values in the matrix in non-increasing order.
set<int, greater<>> decreasingSet;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
valToIndices[mat[i][j]].emplace_back(i, j);
decreasingSet.insert(mat[i][j]);
}
for (const int val : decreasingSet) {
for (const auto& [i, j] : valToIndices[val])
maxPathLength[i][j] = max(rows[i], cols[j]) + 1;
for (const auto& [i, j] : valToIndices[val]) {
rows[i] = max(rows[i], maxPathLength[i][j]);
cols[j] = max(cols[j], maxPathLength[i][j]);
}
}
return max(ranges::max(rows), ranges::max(cols));
}
};
/* code provided by PROGIEZ */2713. Maximum Strictly Increasing Cells in a Matrix LeetCode Solution in Java
class Solution {
public int maxIncreasingCells(int[][] mat) {
final int m = mat.length;
final int n = mat[0].length;
// rows[i] := the maximum path length for the i-th row
int[] rows = new int[m];
// cols[j] := the maximum path length for the j-th column
int[] cols = new int[n];
Map<Integer, ArrayList<Pair<Integer, Integer>>> valToIndices = new HashMap<>();
// maxPathLength[i][j] := the maximum path length from mat[i][j]
int[][] maxPathLength = new int[m][n];
// Sort all the unique values in the matrix in non-increasing order.
TreeSet<Integer> decreasingSet = new TreeSet<>(Comparator.reverseOrder());
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
final int val = mat[i][j];
valToIndices.putIfAbsent(val, new ArrayList<>());
valToIndices.get(val).add(new Pair<>(i, j));
decreasingSet.add(val);
}
for (final int val : decreasingSet) {
for (Pair<Integer, Integer> pair : valToIndices.get(val)) {
final int i = pair.getKey();
final int j = pair.getValue();
maxPathLength[i][j] = Math.max(rows[i], cols[j]) + 1;
}
for (Pair<Integer, Integer> pair : valToIndices.get(val)) {
final int i = pair.getKey();
final int j = pair.getValue();
rows[i] = Math.max(rows[i], maxPathLength[i][j]);
cols[j] = Math.max(cols[j], maxPathLength[i][j]);
}
}
return Math.max(Arrays.stream(rows).max().getAsInt(), //
Arrays.stream(cols).max().getAsInt());
}
}
// code provided by PROGIEZ2713. Maximum Strictly Increasing Cells in a Matrix LeetCode Solution in Python
class Solution:
def maxIncreasingCells(self, mat: list[list[int]]) -> int:
m = len(mat)
n = len(mat[0])
rows = [0] * m # rows[i] := the maximum path length for the i-th row
cols = [0] * n # cols[j] := the maximum path length for the j-th column
valToIndices = collections.defaultdict(list)
# maxPathLength[i][j] := the maximum path length from mat[i][j]
maxPathLength = [[0] * n for _ in range(m)]
# Sort all the unique values in the matrix in non-increasing order.
decreasingSet = set()
for i in range(m):
for j in range(n):
val = mat[i][j]
valToIndices[val].append((i, j))
decreasingSet.add(val)
for val in sorted(decreasingSet, reverse=True):
for i, j in valToIndices[val]:
maxPathLength[i][j] = max(rows[i], cols[j]) + 1
for i, j in valToIndices[val]:
rows[i] = max(rows[i], maxPathLength[i][j])
cols[j] = max(cols[j], maxPathLength[i][j])
return max(max(rows), max(cols))
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.