LeetCode Entry

1727. Largest Submatrix With Rearrangements

17.03.2026 medium 2026 kotlin rust

Max area of binary matrix, swap columns

1727. Largest Submatrix With Rearrangements medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1300

Problem TLDR

Max area of binary matrix, swap columns #medium

Intuition

    // columns!
    //         6
    // ***___***___
    // __*****_____ 5
    // ______***___
    // ______*_____
    // ______*_____
    // ______*_____
    // ______*_____
    //       7
    //
    // 001
    // 112 = 1+1+1=3
    // 203 = 2+2=4
    //
    // 22223345  max(2*8,3*4, 4*2, 5)

• subproblem: only the last row with histogram of the previous rows
• sort the histogram, O(n) scan max(h(x)*(width-x))

Approach

• don’t have to build histogram for the first row
• r[x] *= prev + 1 trick

Complexity

• Time complexity: \(O(nmlog(m))\)

• Space complexity: \(O(m)\)

Code

// 110ms
    fun largestSubmatrix(m: Array<IntArray>) =
        m.withIndex().maxOf { (y,r) ->
            if (y>0) for (x in r.indices) r[x] *= m[y-1][x] + 1
            r.sorted().withIndex().maxOf { (x,v) -> (r.size-x)*v }
        }

// 4ms
    pub fn largest_submatrix(mut m: Vec<Vec<i32>>) -> i32 {
        (0..m.len()).map(|y| {
            if y > 0 { for x in 0..m[0].len() { m[y][x] *= m[y-1][x]+1}}
            let mut r = m[y].clone(); r.sort();
            (0..r.len()).map(|x|(r.len()-x)as i32*r[x]).max().unwrap()
        }).max().unwrap()
    }