Maximally Indexed Indices (PWC 298)

Challenge 298 solutions in Perl by Matthias Muth

Thank you, Mohammad Sajid Anwar for two more great challenges this week!

These are my Challenge 298 Task 1 and 2 solutions in Perl
for The Weekly Challenge.

Summary

Task 1: Maximal Square
Quite classical: nested loops for rows and columns, and then for the width of the possible square.
The trick here is to extend the square by stripes to the right and below until it doesn't match the criteria anymore.
Finding the maximum of all size on the fly is easy.

Task 2: Right Interval
Sorting the indices of the given intervals by their start_i values, resulting in indices of indices. Then go through the sorted array to more easily find the 'right' interval. Don't get mixed up by the level of indexation!

Code:
Find the complete source code for both tasks, including tests, on Github.

Task 1: 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 1's and return it’s area.

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

I chose a classical approach, using two nested loops for rows and columns.

At any given position, if the field is 1, we already have a matrix, of size 1.
Now we can try to extend our matrix by one column to the right and one row below. If all fields at the right edge of that extended matrix are 1, as well as all fields at its bottom edge, the extended matrix is a valid square. We repeat that until the test fails, or the extended matrix hits the border of the original grid.

For checking the right and bottom border for 'all ones', the all function from the List::Util core module comes in handy.

We update the maximum square width in each iteration, and return the squared maximum width (the size of the largest square) at the end.

Three nested loops, but quite straightforward:

use v5.36;
use List::Util qw( all max );

sub maximal_square( $matrix ) {
    my ( $last_r, $last_c ) = ( $matrix->$#*, $matrix->[0]->$#* );
    my $max = 0;
    for my $r ( 0..$last_r ) {
        for my $c ( 0..$last_c ) {
            next
                if $matrix->[$r][$c] != 1;
            my $w = 1;
            while ( $r + $w <= $last_r
                && $c + $w <= $last_c
                && ( all { $matrix->[ $r + $_ ][ $c + $w ] } 0 .. $w )
                && ( all { $matrix->[ $r + $w ][ $c + $_ ] } 0 .. $w - 1 ) )
            {
                ++$w;
            }
            $max = $w
                if $w > $max;
        }
    }
    return $max * $max;
}

Task 2: Right Interval

You are given an array of @intervals, where \$intervals[i] = [starti, endi] and each starti is unique.
The right interval for an interval i is an interval j such that startj >= endi and startj is minimized. Please note that i may equal j.
Write a script to return an array of right interval indices for each interval i. If no right interval exists for interval i, then put -1 at index i.

Example 1

Input: @intervals = ([3,4], [2,3], [1,2])
Output: (-1, 0, 1)
There is no right interval for [3,4].
The right interval for [2,3] is [3,4] since start0 = 3 is the smallest start that is >= end1 = 3.
The right interval for [1,2] is [2,3] since start1 = 2 is the smallest start that is >= end2 = 2.

 
Example 2

Input: @intervals = ([1,4], [2,3], [3,4])
Output: (-1, 2, -1)
There is no right interval for [1,4] and [3,4].
The right interval for [2,3] is [3,4] since start2 = 3 is the smallest start that is >= end1 = 3.

 
Example 3

Input: @intervals = ([1,2])
Output: (-1)
There is only one interval in the collection, so it outputs -1.

 
Example 4

Input: @intervals = ([1,4], [2, 2], [3, 4])
Output: (-1, 1, -1)

I want to find the interval to the right of each interval that meets a given criteria, but the intervals in the input data are ordered randomly. So best is to sort the intervals first, using their start_i values.

In the sorted array, we only store the indices into the original array, because we will need the original index for building up the results to return:

    my @sorted_indices =
    sort { $intervals->[$a][0] <=> $intervals->[$b][0] }
        keys $intervals->@*;

I use the keys ARRAY standard Perl function instead of 0..$#ARRAY for getting the list of all indices of ARRAY. This is shorter, easier to type, and less prone to typing errors. It has been available since Perl 5.12 (so since the year 2010!).

The indices of the sorted array point to the indices of the original array. We have indexed the indices! (Hence the title of this blog.)

We can then find the 'right' interval for each original interval by getting the first entry in the sorted array that points to an interval that meets the criteria of having a start_i value equal to or greater that the end_i value of the current interval:

    return map {
        my $end_i = $_->[1];
        ( first { $intervals->[$_][0] >= $end_i } @sorted_indices ) // -1;
    } $intervals->@*;

That works, and is a good enough solution for the test data.

But as usual, I try to not repeat doing things that aren't necessary. You may call it 'runtime optimization', but I think that if it is algorithmically unnecessary, it's a waste of resources, and not a good solution.

What bothers me is this:
Each time we want a 'right' interval for an original interval, we go through the sorted array from the beginning again.

Looking for a way to avoid this, we could walk through the sorted array instead of the original array. Then we can start searching at the current interval instead of the beginning of the array. And typically the search will return one of the first few intervals that are to the right of the current interval (skipping only those that start inside our current interval, and thus are not 'right' intervals).

The downside is that we get the results in a seemingly random order. But we have the original index, so we can put each result into a @result array at the correct place, and just return that array in the end.

That solution then looks like this:

sub right_interval( $intervals ) {
    my @sorted_indices =
        sort { $intervals->[$a][0] <=> $intervals->[$b][0] }
            keys $intervals->@*;

    my @results;
    for my $si_i ( 0..$#sorted_indices ) {
        my $i = $sorted_indices[$si_i];
        my $end_i = $intervals->[$i][1];
        $results[$i] =
            ( first { $intervals->[$_][0] >= $end_i }
                @sorted_indices[ $si_i .. $#sorted_indices ] )
                // -1;
    }
    return @results;
}

Feeling good about not heating the CPU too much, by indexing indices!

Thank you for the challenge!