Problem Name: 1727. Largest Submatrix with Rearrangement
Problem Link: https://leetcode.com/problems/largest-submatrix-with-rearrangements/description/?envType=daily-question&envId=2023-11-26
Difficulty: Medium
Tag: Array | Matrix | Greedy | Sorting
Language: C# | C++
OJ: LeetCode
Algorithm:
Initialization:
Get the number of rows (rowSize) and columns (columnSize) in the matrix.
Initialize result to 0.
Iterate through Rows:
For each row i:
If i > 0, accumulate the height of the submatrix by adding the value of the corresponding element from the previous row to each 1 in the current row.
Calculate Heights and Update Result:
Create an array store with the heights of the submatrices for the current row.
Sort store in descending order.
For each height in store, calculate the size of the submatrix and update result with the maximum size encountered.
Return Result:
Return the final value of result, representing the size of the largest submatrix consisting entirely of 1s.
Code(C#)
class Solution {
public:
vector<int> getSumAbsoluteDifferences(vector<int>& nums) {
int n = nums.size();
vector<int> result(n);
vector<int> previous(n);
vector<int> next(n);
previous[0] = 0;
for (int i = 1; i < n; ++i)
previous[i] = previous[i - 1] + i * (nums[i] - nums[i - 1]);
next[n - 1] = 0;
for (int i = n - 2, j = 1; i >= 0; --i, ++j)
next[i] = next[i + 1] + j * (nums[i + 1] - nums[i]);
for (int i = 0; i < n; ++i)
result[i] = previous[i] + next[i];
return result;
}
};
Code(C++)
class Solution {
public:
int largestSubmatrix(vector<vector<int>>& matrix) {
int rowSize = matrix.size();
int columnSize = matrix[0].size();
int result = 0;
for (int i = 0; i < rowSize; i++) {
if (i > 0)
for (int j = 0; j < columnSize; j++) {
if (matrix[i][j] == 1)
matrix[i][j] += matrix[i - 1][j];
}
vector<int> store(matrix[i].begin(), matrix[i].end());
sort(store.begin(), store.end(), greater<int>());
for (int j = 0; j < columnSize; j++) {
int value = store[j] * (j + 1);
result = max(result, value);
}
}
return result;
}
};