| 06 December 2024 | Challenge 298 |
The Right Square
Task 1: Maximal Square
Submitted by: Mohammad Sajid Anwar
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
Solution
From example 3 it follows that one-dimensional input is allowed. While tolerating this, we’ll always operate on a two-dimensional binary \(m \times n\) matrix \(B = (b_{i,k})\) where any of \(m\) or \(n\) may be one.
For \(l \le \min(m, n)\) we may define a binary \((m - l + 1 ) \times (n - l + 1)\) matrix \(B^l = (b_{i,k}^l)\), where \(b_{i,k}^l = 1\) if and only if the square submatrix of \(B\) with length \(l\) having the upper left corner \(b_{i,k}\) consists of 1s only.
Obviously we have \(B^1 = B\).
Analyzing \(B^l\):
- If \(B^l\) is a zero matrix, then \(B\) doesn’t contain a square of length \(l\) consisting of
1s only. - If \(B^l\) is not zero, but has only one row or column, then \(B\)’s maximum square length is \(l\).
- Otherwise we have \(l < \min(m, n)\), i.e. \(B^l\) has at least two rows and columns.
Then we find \(B^{l+1}\) as:
\[b^{l+1}_{i,k} = b^l_{i,k} \wedge b^l_{i+1,k} \wedge b^l_{i,k+1} \wedge b^l_{i+1,k+1}\]We may iterate over \(B^l\) starting from \(B^1 = B\) until either \(B^l\) is a zero matrix or has only one row or column. According to the above rules, we find the maximum square length of \(B\) then.
For the requested size as result we need to square the final length.
Extracting rectangular subarrays from an ndarray is what PDL’s range method is made for.
Here is a demonstration of extracting \(2 \times 2\) submatrices in the PDL shell:
pdl> do_print 1
1
pdl> $m = sequence 3, 3
[
[0 1 2]
[3 4 5]
[6 7 8]
]
pdl> $m->range(ndcoords($m(0:-2,0:-2)), 2)->reorder(2, 3, 0, 1)
[
[
[
[0 1]
[3 4]
]
[
[1 2]
[4 5]
]
]
[
[
[3 4]
[6 7]
]
[
[4 5]
[7 8]
]
]
]
This leads to the following implementation:
use strict;
use warnings;
use PDL;
use PDL::NiceSlice;
sub max_square {
my $m = long @_;
$m = $m->dummy(1) if $m->ndims < 2;
for (my $len = 1;; $len++) {
return ($len - 1)**2 if !any($m);
return $len**2 if min($m->shape) < 2;
$m = $m->range(ndcoords($m(0:-2,0:-2)), 2)
->reorder(2, 3, 0, 1)->andover->andover;
}
}
Here are the matrices \(B^l\) for example 1 leading to \(l_{\max} = 2\):
pdl> $m = long [1, 0, 1, 0, 0], [1, 0, 1, 1, 1], [1, 1, 1, 1, 1], [1, 0, 0, 1, 0]
[
[1 0 1 0 0]
[1 0 1 1 1]
[1 1 1 1 1]
[1 0 0 1 0]
]
pdl> $m = $m->range(ndcoords($m(0:-2,0:-2)),2)->reorder(2, 3, 0, 1)->andover->andover
[
[0 0 0 0]
[0 0 1 1]
[0 0 0 0]
]
pdl> $m = $m->range(ndcoords($m(0:-2,0:-2)),2)->reorder(2, 3, 0, 1)->andover->andover
[
[0 0 0]
[0 0 0]
]
Other examples
The radius \(r\) of the circumcircle of a square with an edge length \(a\) is \(r = \frac{a}{\sqrt{2}}\). Approximating a circle with \(r = 7\) in a binary \(31 \times 31\) matrix. The largest square therein should have an edge length of \(\lfloor 7 \sqrt{2} \rfloor = 9\), leading to an area \(A = 81\). Let’s try it:
pdl> do_print 1
1
pdl> floor 7 * 2**.5
9
pdl> $b = rvals(31, 31, {centre => [15, 15]}) <= 7
[
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
]
pdl> do "./ch-1.pl"
pdl> max_square($b)
81
We may increase the size to \(r = 63\), where we have \(a = \lfloor 63 \sqrt{2} \rfloor = 89\) and \(A = 7921\).
pdl> floor 63 * 2**.5
89
pdl> 89 ** 2
7921
pdl> $b = rvals(255, 255, {centre => [127, 127]}) <= 63
TOO LONG TO PRINT
pdl> max_square($b)
7921
See the full solution to task 1.
Task 2: Right Interval
Submitted by: Mohammad Sajid Anwar
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)
Solution
First we sort the intervals by their start and their end values resulting in a right and a left list.
Then we pick the first interval from the right list and loop over the left list.
If the right interval is not valid for the left interval, i.e. the right start is less than the left end, we proceed in the right list until we find a valid interval and we assign the right intervals’s index to the result at the left intervals index position.
The crucial point is to keep the right interval when proceeding to the next left interval as all the start values in the intervals preceding the right interval are too small for the end values of all following left intervals and therefore only a single pass over the right list is required.
With a little trick we may handle the case of “no right interval” easily: We append an “match all” interval with an infinite start to the list of right intervals that is accessible with the index -1.
The total time complexity of this procedure is dominated by the sorting, which is \(\mathcal{O}(n \log n)\).
use v5.20;
use warnings;
use List::MoreUtils 'nsort_by';
use POSIX 'Inf';
use experimental 'signatures';
sub right_interval (@ints) {
my @left = nsort_by {$ints[$_][1]} 0 .. $#ints;
push @ints, [Inf];
my @right = nsort_by {$ints[$_][0]} -1 .. $#ints - 1;
my @result;
my $r = shift @right;
for my $l (@left) {
$r = shift @right while $ints[$r][0] < $ints[$l][1];
$result[$l] = $r;
}
\@result;
}
See the full solution to task 2.
If you have a question about this post or if you like to comment on it, feel free to open an issue in my github repository.