# 26.11.2023 [1727. Largest Submatrix With Rearrangements]
Max area of `1` submatrix after sorting columns optimally
26.11.2023
1727. Largest Submatrix With Rearrangements medium
blog post
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/417
Problem TLDR
Max area of 1
submatrix after sorting columns optimally
Intuition
Use hint :(
Ok, if we store the heights of the columns we can analyze each row independently, by choosing the largest heights first. The area will be height * width
, where width will be the current position:
Approach
We can reuse the matrix, but don’t do this in a production code without a warning.
Complexity
Time complexity:
O(nmlog(m))Space complexity:
O(1)
Code
fun largestSubmatrix(matrix: Array<IntArray>): Int {
for (y in 1..<matrix.size)
for (x in 0..<matrix[y].size)
if (matrix[y][x] > 0)
matrix[y][x] += matrix[y - 1][x]
var max = 0
for (row in matrix) {
row.sort()
for (x in row.lastIndex downTo 0)
max = max(max, row[x] * (row.size - x))
}
return max
}