⚡Flashcard Drill➔
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

  1. Process row by row, maintaining h[j], the number of consecutive ones ending at the current row in column j.
  2. Rearranging a column is equivalent to freely permuting the heights h[0..n-1], so sort them in descending order.
  3. After sorting, the k-th height (1-indexed) means k columns have height at least that value, forming a k * h rectangle.
  4. Take the maximum of k * h over all rows and all k.

💻 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, the k-th element already is the minimum of the first k heights, so the plain product is correct.
  • Only considering the full width or a single row: the optimum can use any width, so all k values 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.
🎯 Drill This Card Now➔

🧩 Related Math & Geometry Problems