Task — Maximal square

You are given an m x n binary matrix with 0 and 1 only. Write a script to find the largest square containing only 1s and return its area.

Examples

Example 1
Input: @matrix = ([1, 0, 1, 0, 0],
                  [1, 0, 1, 1, 1],
                  [1, 1, 1, 1, 1],
                  [1, 0, 0, 1, 0])
Output: 4
Two maximal square found with same size marked as 'x':
[1, 0, 1, 0, 0]
[1, 0, x, x, 1]
[1, 1, x, x, 1]
[1, 0, 0, 1, 0]
[1, 0, 1, 0, 0]
[1, 0, 1, x, x]
[1, 1, 1, x, x]
[1, 0, 0, 1, 0]

Example 2
Input: @matrix = ([0, 1],
                  [1, 0])
Output: 1
Two maximal square found with same size marked as 'x':
[0, x]
[1, 0]
[0, 1]
[x, 0]

Example 3
Input: @matrix = ([0])
Output: 0

Analysis

This is a good example of something which the human eye can spot in a second or two, but isn't so easy to do in procedural software.

In general, when we are looking for the largest something we need to generate all the possible somethings and keep track of the largest one we've found so far. That is a possible approach here, but I've found a (somewhat) better one.

First, let's note that the side length $s of the largest square can't be more than the smaller of the height $h or the width $w of the matrix.

Also, the top-left corner of a square of side length $q must have an $x coordinate no more than $w - $q and a $y coordinate no more than $h - $q, because otherwise the bottom-right element would be outside the matrix.

Armed with those insights I have an outer loop looking for squares with side lengths $q ranging from $s down to 1. Searching for the largest possible square first means we can stop as soon as we find a square: ther's no need to keep looking because we've already eliminated the possibility of a larger one.

Within this outer loop I then have two nested loops checking all the possible top-left corners for a $q x $q square, bearing in mind the limits on top-left corners described above.

And lastly, for each of these top-left corner and size combinations I check the sqare for 0s, and if there are none, we have the solution.

An algorithm with 4 nested loops is not something I would use lightly, but with the limits imposed by this approach it handles a 100 x 100 matrix of random 1s and 0s in under a second. The randomness means that in such a matrix there is typically only a 2 x 2 square to be found, so I think I can claim that this is a sufficiently economical solution.

Try it 

Try running the script with any input:

Your $m =

example: [0, 1, 1], [1, 1, 1], [1, 1, 0]

⤡

#!/usr/bin/perl

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

use v5.26;    # The Weekly Challenge - 2024-12-02
use utf8;     # Week 298 - task 1 - Maximal square
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';

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

maximal_square([[1, 0, 1, 1],
                [0, 1, 0, 1],
                [1, 0, 1, 0],
                [1, 0, 1, 1]]);
                
maximal_square([[0, 0],
                [0, 0]]);
                
sub maximal_square {
    
    my ($m, $w, $h, $s, $q, $x, $y, $xx, $yy, $top_left);
    $m = shift;
    
    $h = @$m;               # height
    $w = @{$m->[0]};        # width
    $s = $w > $h ? $h : $w; # max possible square side
    $top_left = '';
    
    # loop over possible sizes, largest to smallest
    SIZES: for ($q = $s; $q > 0; $q --) {
    
        # loop over all possible top-left x and y
        for $x (0 .. $w - $q) {
            TOPLEFT: for $y (0 .. $h - $q) {
                
                # now check if this is the top left of 
                # a $q-sided square
                for $xx ($x .. $x + $q - 1) {
                    for $yy ($y .. $y + $q - 1) {
                        next TOPLEFT unless $m->[$yy]->[$xx] == 1;
                    }
                }
                
                # found a square!
                $top_left = qq[$x, $y];
                last SIZES;
            }
        }
    }
    print_matrix('Input: ', $m);
    say qq[Output: ] . ($top_left ? (($q * $q) . 
       qq[ (top left at $top_left)]) : '0');
}

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, 1, 0, 0]
        [1, 0, 1, 1, 1]
        [1, 1, 1, 1, 1]
        [1, 0, 0, 1, 0]
Output: 4 (top left at 2, 1)

Input:  [1, 0, 1, 0, 0]
        [1, 0, 1, 1, 1]
        [1, 1, 1, 1, 1]
        [1, 0, 1, 1, 1]
        [0, 1, 0, 1, 0]
Output: 9 (top left at 2, 1)

Input:  [1, 0, 1, 1]
        [0, 1, 0, 1]
        [1, 0, 1, 0]
        [1, 0, 1, 1]
Output: 1 (top left at 0, 0)

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