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 its area.
Method Explanation
A standard brute-force approach testing all possible square submatrices would be $O((m \cdot n) \cdot \min(m, n)^2)$, which is inefficient. Instead, we can use Dynamic Programming in $O(m \cdot n)$ time and space.
Let dp[r][c] represent the side length of the largest all-1s square whose bottom-right corner is at (r, c).
- If
matrix[r][c] == 0, thendp[r][c] = 0. - If
matrix[r][c] == 1:- If on the first row or first column (
r == 0orc == 0),dp[r][c] = 1. - Otherwise, a square of side $k$ can only be formed if the cells above (
r-1, c), to the left (r, c-1), and diagonally top-left (r-1, c-1) can each support a square of side $k - 1$. Therefore:dp[r][c] = 1 + min(dp[r - 1][c], dp[r][c - 1], dp[r - 1][c - 1])
- If on the first row or first column (
Perl Implementation
sub maximal_square_area ($matrix) {
($matrix) = $MATRIX_CHECK->($matrix);
return 0 if !@$matrix;
my $rows = scalar @$matrix;
my $cols = scalar @{ $matrix->[0] };
die 'Non-rectangular matrix' if grep { @$_ != $cols } @$matrix;
my @dp = map { [ (0) x $cols ] } 1 .. $rows;
my $best = 0;
for my $r ( 0 .. $rows - 1 ) {
for my $c ( 0 .. $cols - 1 ) {
my $val = $matrix->[$r][$c];
die 'Matrix must contain only 0 and 1' if $val != 0 && $val != 1;
next if $val == 0;
my $size;
if ( $r == 0 || $c == 0 ) {
$size = 1;
}
else {
$size = 1 + min( $dp[ $r - 1 ][$c], $dp[$r][ $c - 1 ], $dp[ $r - 1 ][ $c - 1 ] );
}
$dp[$r][$c] = $size;
$best = $size if $size > $best;
}
}
return $best * $best;
}
Python Implementation
def maximal_square_area(matrix: Sequence[Sequence[int]]) -> int:
"""Return the area of the largest all-1s square in the 0/1 matrix."""
if not matrix:
return 0
rows = len(matrix)
cols = len(matrix[0])
if any(len(row) != cols for row in matrix):
raise ValueError("Non-rectangular matrix")
dp = [[0] * cols for _ in range(rows)]
best = 0
for r in range(rows):
for c in range(cols):
value = matrix[r][c]
if value not in (0, 1):
raise ValueError("Matrix must contain only 0 and 1")
if value == 0:
continue
if r == 0 or c == 0:
dp[r][c] = 1
else:
dp[r][c] = 1 + min(dp[r - 1][c], dp[r][c - 1], dp[r - 1][c - 1])
best = max(best, dp[r][c])
return best * best
Task 2: Right Interval
You are given an array of intervals, where intervals[i] = [start_i, end_i] and each start_i is unique. The right interval for an interval i is an interval j such that start_j >= end_i and start_j is minimized. Return an array of right interval indices for each interval. If no right interval exists for an interval i, then put -1 at index i.
Method Explanation
Since each interval's start value is unique, we can pair each interval's start value with its original index (start_i, i) and sort these pairs by start value in ascending order.
Then, for each original interval [start_i, end_i]:
- We perform a binary search (lower bound /
bisect_left) on the sorted start values to find the first start value that is $\ge \text{end}_i$. - If such an index is found within bounds, the original index of that interval is our answer for interval $i$.
- If all start values are smaller than $\text{end}_i$, the answer is
-1.
Perl Implementation
sub _lower_bound ($starts, $value) {
my ( $lo, $hi ) = ( 0, scalar(@$starts) );
while ( $lo < $hi ) {
my $mid = int( ( $lo + $hi ) / 2 );
if ( $starts->[$mid] < $value ) {
$lo = $mid + 1;
}
else {
$hi = $mid;
}
}
return $lo;
}
sub right_interval_indices ($intervals) {
($intervals) = $INTERVALS_CHECK->($intervals);
return [] if !@$intervals;
my @starts;
for my $i ( 0 .. $#$intervals ) {
my $start = $intervals->[$i][0];
push @starts, [ $start, $i ];
}
@starts = sort { $a->[0] <=> $b->[0] } @starts;
my @sorted_starts = map { $_->[0] } @starts;
my @out;
for my $i ( 0 .. $#$intervals ) {
my $end = $intervals->[$i][1];
my $pos = _lower_bound( \@sorted_starts, $end );
push @out, $pos == @sorted_starts ? -1 : $starts[$pos][1];
}
return \@out;
}
Python Implementation
def right_interval_indices(intervals: Sequence[Interval]) -> list[int]:
"""Return index of the right interval for each interval, or -1."""
if not intervals:
return []
starts = sorted((start, idx) for idx, (start, _end) in enumerate(intervals))
sorted_starts = [start for start, _idx in starts]
result: list[int] = []
for _start, end in intervals:
pos = bisect_left(sorted_starts, end)
result.append(starts[pos][1] if pos < len(starts) else -1)
return result