NeetCode #928LC-1727MediumMath & Geometry
← Back to All Problems#928 · #1727 · Largest Submatrix With Rearrangements(重新排列后的最大子矩阵)
📌 Problem Statement & Constraints
Given an
m x n binary matrix, you may rearrange the elements of each column in any order. Return the area of the largest all-ones submatrix obtainable after rearranging. Constraints: 1 <= m, n <= 10^5, 1 <= m * n <= 10^5, each matrix[i][j] is 0 or 1.💡 Core Algorithmic Approaches
- Process row by row, maintaining
h[j], the number of consecutive ones ending at the current row in columnj. - Rearranging a column is equivalent to freely permuting the heights
h[0..n-1], so sort them in descending order. - After sorting, the
k-th height (1-indexed) meanskcolumns have height at least that value, forming ak * hrectangle. - Take the maximum of
k * hover all rows and allk.
💻 Benchmark Python3 Implementation
class Solution:
def largestSubmatrix(self, matrix: List[List[int]]) -> int:
m, n = len(matrix), len(matrix[0])
h = [0] * n
res = 0
for i in range(m):
for j in range(n):
h[j] = h[j] + 1 if matrix[i][j] else 0 # running height of ones
for width, height in enumerate(sorted(h, reverse=True), 1):
res = max(res, width * height)
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(m * n log n): each of the m rows triggers a sort of n heights.
💾 Space Complexity
O(n): the height array.
⚠️ Interview Pitfalls & Follow-ups
- Actually permuting the matrix columns: it costs O(m * n) moves and complicates the code; sorting the height array is equivalent and simpler.
- Forgetting to reset a height on a zero: a 0 breaks the run of consecutive ones, so
h[j]must return to 0. - Using
width * min(height): after sorting, thek-th element already is the minimum of the firstkheights, so the plain product is correct. - Only considering the full width or a single row: the optimum can use any width, so all
kvalues must be enumerated.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.