The Weekly Challenge #298

Maximal Square • Right Interval
Official Challenge • My Solutions 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 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, then dp[r][c] = 0.
  • If matrix[r][c] == 1:
    • If on the first row or first column (r == 0 or c == 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])
The maximum side length seen across all cells is tracked, and the final answer is $\text{best}^2$.

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.
Sorting takes $O(N \log N)$ and performing $N$ binary searches takes $O(N \log N)$, giving an overall time complexity of $O(N \log N)$ which is vastly superior to the quadratic $O(N^2)$ brute force.

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