2023.11.26 Today's Challenge

fabichoi 2023. 11. 26. 23:45

https://leetcode.com/problems/largest-submatrix-with-rearrangements/

Largest Submatrix With Rearrangements - LeetCode

Can you solve this real interview question? Largest Submatrix With Rearrangements - You are given a binary matrix matrix of size m x n, and you are allowed to rearrange the columns of the matrix in any order. Return the area of the largest submatrix within

leetcode.com

TL이 나기 쉬운 문제

class Solution:
    def largestSubmatrix(self, matrix: List[List[int]]) -> int:
        m, n, ans = len(matrix), len(matrix[0]), 0
        prev_row = [0] * n

        for row in range(m):
            curr_row = matrix[row][:]
            for col in range(n):
                if curr_row[col] != 0:
                    curr_row[col] += prev_row[col]
                
            sorted_row = sorted(curr_row, reverse=True)
            for i in range(n):
                ans = max(ans, sorted_row[i] * (i+1))
            
            prev_row = curr_row
            
        return ans