We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Largest Submatrix With Rearrangements

Number: 1845

Difficulty: Medium

Paid? No

Companies: Amazon, Google, Directi

Problem Description

Given an m x n binary matrix, you can rearrange the columns in any order. Determine the area of the largest submatrix (formed by contiguous rows and columns) such that every element is 1 after an optimal rearrangement of the columns.

Key Insights

  • For each cell in the matrix, compute the number of consecutive 1s vertically up to that cell. This effectively gives a histogram representation for that row.
  • Since columns can be rearranged arbitrarily, sorting the histogram for the current row in descending order groups the taller bars together.
  • After sorting, the potential area for a submatrix with height equal to the j-th entry in the sorted array is: (height) * (j+1), because you can use the first (j+1) columns.
  • Maintain a global maximum area by evaluating all rows.

Space and Time Complexity

Time Complexity: O(m * n * log n) Space Complexity: O(m * n) if using a separate DP table; can be optimized to O(n) by modifying the matrix or using one auxiliary array.

Solution

We first iterate through the matrix row by row. For each row, update the height of consecutive 1s for every column. Then, copy the current row’s heights and sort them in descending order which simulates the optimal rearrangement of columns. For every index in the sorted list, calculate the area as (sorted_height * (current_index + 1)) and update the maximum area found. This solution leverages dynamic programming, greedy sorting, and histogram area calculation.

Code Solutions

def largestSubmatrix(matrix):
    # Get dimensions
    num_rows = len(matrix)
    num_cols = len(matrix[0])
    
    # Create a height matrix to store the consecutive 1's count for each column
    max_area = 0
    # Update the matrix in-place to store heights
    for i in range(num_rows):
        for j in range(num_cols):
            # If we are not at the first row and the current cell is a 1 update with previous row count
            if matrix[i][j] == 1 and i > 0:
                matrix[i][j] += matrix[i - 1][j]
        # Copy current row of heights and sort in descending order to simulate optimal column rearrangement
        sorted_heights = sorted(matrix[i], reverse=True)
        # Compute the area using each height as the minimum height for a submatrix of width (j+1)
        for j in range(num_cols):
            current_area = sorted_heights[j] * (j + 1)
            max_area = max(max_area, current_area)
    return max_area

# Example usage:
# matrix = [[0,0,1],[1,1,1],[1,0,1]]
# print(largestSubmatrix(matrix))
← Back to All Questions