Task — Maximum sub-matrix

You are given m x n binary matrix having 0 or 1 as elements. Write a script to find out maximum sub-matrix having only 0 elements.

Examples

Example 1:
Input : [ 1 0 0 0 1 0 ]
        [ 1 1 0 0 0 1 ]
        [ 1 0 0 0 0 0 ]
Output: [ 0 0 0 ]
        [ 0 0 0 ]

Example 2:
Input : [ 0 0 1 1 ]
        [ 0 0 0 1 ]
        [ 0 0 1 0 ]
Output: [ 0 0 ]
        [ 0 0 ]
        [ 0 0 ]

Analysis

I did not submit a solution at the time, but have written this later

My solution to this is as follows:

• Loop over every cell in the matrix that contains 0
• Consider each cell in turn to be at the top left of a rectangular block of 0 elements, and look to the right and below to see how far the block extends (there may be more than one)
• If it is the largest block found so far, record this as the possible answer

There is one special case, which is when the matrix comprises only 1s, in which case there is obviously no block of zeroes.

Try it 

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2021-08-30
use utf8;     # Week 128 - task 1 - Maximum Sub-Matrix
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';

my $m;

maximum_submatrix([[ 1, 0, 0, 0, 1, 0 ],
                   [ 1, 1, 0, 0, 0, 1 ],
                   [ 1, 0, 0, 0, 0, 0 ]]);
maximum_submatrix([[ 0, 0, 1, 1 ],
                   [ 0, 0, 0, 1 ],
                   [ 0, 0, 1, 0 ]]);
maximum_submatrix([[ 0, 1, 1, 1, 1 ],
                   [ 0, 1, 1, 1, 1 ],
                   [ 0, 1, 1, 1, 1 ],
                   [ 0, 0, 0, 0, 0 ]]);
maximum_submatrix([[ 1, 0, 0, 0, 1, 0 ],
                   [ 1, 1, 0, 0, 0, 1 ],
                   [ 1, 0, 0, 0, 0, 0 ]]);
maximum_submatrix([[ 1, 1, 1, 1, 1, 1 ],
                   [ 1, 1, 1, 1, 0, 0 ],
                   [ 1, 1, 1, 0, 0, 0 ]]);             
maximum_submatrix([[ 0 ]]);
maximum_submatrix([[ 1 ]]);
maximum_submatrix([[1, 0, 0], [1, 0, 0], [0, 1, 0]]);

sub maximum_submatrix {
    
    my ($last_x, $last_y, @already, $x, $y, $xx, $yy, $size, $biggest, $shape, $output);
    
    $m = shift;
    $last_y = @$m - 1;
    $last_x = @{$m->[0]} - 1;
    
    # loop over all possible top lefts
    $biggest = 0;
    for $x (0 .. $last_x) {
        for $y (0 .. $last_y) {
            
            # check all bottom rights
            for $xx ($x .. $last_x) {
                for $yy ($y .. $last_y) {
                    next unless valid_submatrix($x, $y, $xx, $yy);
                    $size = ($xx - $x + 1) * ($yy - $y + 1);
                    if ($size > $biggest) {
                        $shape = [$xx - $x + 1, $yy - $y + 1];
                        $biggest = $size;
                    }
                }
            }
        }
    }

    print_matrix('Input: ', $m);
    unless (defined $shape) {
        say qq[Output: none];
        return;
    }
    for $y (0 .. $shape->[0] - 1) {
        for $x (0 .. $shape->[1] - 1) {
            $output->[$x][$y] = 0;
        }
    }
    print_matrix('Output:', $output);
}

sub valid_submatrix {

    my ($x1, $y1, $x2, $y2) = @_;
    my ($x, $y);

    for $x ($x1 .. $x2) {
        for $y ($y1 .. $y2) {
            return 0 if $m->[$y]->[$x];
        }
    }
    return 1;
}
        
sub print_matrix {
    
    my ($legend, $matrix, $j);

    # format matrix
    ($legend, $matrix) = @_;
    say '';
    for $j (0 .. @$matrix - 1) {
        say qq{$legend [} . join(', ', @{$matrix->[$j]}) . qq(]);
        $legend = ' ' x length($legend);
    }
}

Output

Input:  [1, 0, 0, 0, 1, 0]
        [1, 1, 0, 0, 0, 1]
        [1, 0, 0, 0, 0, 0]

Output: [0, 0]
        [0, 0]
        [0, 0]

Input:  [0, 0, 1, 1]
        [0, 0, 0, 1]
        [0, 0, 1, 0]

Output: [0, 0]
        [0, 0]
        [0, 0]

Input:  [0, 1, 1, 1, 1]
        [0, 1, 1, 1, 1]
        [0, 1, 1, 1, 1]
        [0, 0, 0, 0, 0]

Output: [0, 0, 0, 0, 0]

Input:  [1, 0, 0, 0, 1, 0]
        [1, 1, 0, 0, 0, 1]
        [1, 0, 0, 0, 0, 0]

Output: [0, 0]
        [0, 0]
        [0, 0]

Input:  [1, 1, 1, 1, 1, 1]
        [1, 1, 1, 1, 0, 0]
        [1, 1, 1, 0, 0, 0]

Output: [0, 0]
        [0, 0]

Input:  [0]

Output: [0]

Input:  [1]
Output: none

Input:  [1, 0, 0]
        [1, 0, 0]
        [0, 1, 0]

Output: [0, 0]
        [0, 0]