The Weekly Challenge 257

Smaller than Current & Reduced Row Echelon

Official Challenge • Solutions on GitHub

Task 1: Smaller than Current

You are given an array of integers, @ints. Write a script to find out how many integers are smaller than current, i.e., for each ints[i], count ints[j] < ints[i] where i != j.

Examples

Example 1: Input: @ints = (5, 2, 1, 6) Output: (2, 1, 0, 3) Example 2: Input: @ints = (1, 2, 0, 3) Output: (1, 2, 0, 3) Example 3: Input: @ints = (0, 1) Output: (0, 1) Example 4: Input: @ints = (9, 4, 9, 2) Output: (2, 1, 2, 0)

Logic

For each element y in the input array, count how many elements x in the same array satisfy x < y. Because strict inequality (<) never matches the element against itself, checking i != j is unnecessary. Time complexity is O(n²) and space complexity is O(n) for the output array.

Perl Solution (ch-1.pl)

#!/usr/bin/env perl
use v5.38;
use warnings;
use Type::Params -sigs;
use Types::Standard qw(ArrayRef Int);
use Test::More;

signature_for smaller_than_current => (
    method     => 0,
    positional => [ ArrayRef [Int] ],
);

sub smaller_than_current ($ints) {
    return [
        map {
            my $x = $_;
            scalar grep { $_ < $x } @$ints
        } @$ints
    ];
}

Python Solution (ch-1.py)

def smaller_than_current(ints: list[int] | tuple[int, ...]) -> list[int]:
    """Return for each element the count of elements strictly smaller than it."""
    return [sum(x < y for x in ints) for y in ints]

Task 2: Reduced Row Echelon

Given a matrix M, check whether the matrix is in reduced row echelon form (RREF). A matrix is in RREF if:

  1. If a row does not consist entirely of zeros, then the first nonzero number in the row is a 1 (the leading 1).
  2. All-zero rows are grouped together at the bottom of the matrix.
  3. In any two successive non-zero rows, the leading 1 in the lower row occurs strictly farther to the right than the leading 1 in the higher row.
  4. Each column containing a leading 1 has zeros everywhere else in that column.

Examples

Example 1: Input: $M = [ [1, 1, 0], [0, 1, 0], [0, 0, 0] ] Output: 0 Example 2: Input: $M = [ [0, 1,-2, 0, 1], [0, 0, 0, 1, 3], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0] ] Output: 1 Example 3: Input: $M = [ [1, 0, 0, 4], [0, 1, 0, 7], [0, 0, 1,-1] ] Output: 1 Example 4: Input: $M = [ [0, 1,-2, 0, 1], [0, 0, 0, 0, 0], [0, 0, 0, 1, 3], [0, 0, 0, 0, 0] ] Output: 0 Example 5: Input: $M = [ [0, 1, 0], [1, 0, 0], [0, 0, 0] ] Output: 0 Example 6: Input: $M = [ [4, 0, 0, 0], [0, 1, 0, 7], [0, 0, 1,-1] ] Output: 0

Logic

We iterate through the matrix row by row while tracking last_leading (initially -1) and a zero_row_encountered flag. If a row is all zeros, we set the flag and continue. If we see a non-zero row after a zero row, we return 0. Otherwise, we locate the first non-zero entry: if it is not 1 or its column index is not strictly greater than last_leading, we return 0. Finally, we verify that all other rows have 0 in that leading column. If all rows pass, we return 1.

Perl Solution (ch-2.pl)

#!/usr/bin/env perl
use v5.38;
use warnings;
use Type::Params -sigs;
use Types::Standard qw(ArrayRef Int);
use Test::More;

signature_for is_reduced_row_echelon => (
    method     => 0,
    positional => [ ArrayRef [ ArrayRef [Int] ] ],
);

sub is_reduced_row_echelon ($matrix) {
    my $last_leading         = -1;
    my $zero_row_encountered = 0;

    for my $row_index ( 0 .. $#{$matrix} ) {
        my $row     = $matrix->[$row_index];
        my $leading = -1;

        for my $i ( 0 .. $#{$row} ) {
            my $element = $row->[$i];
            if ( $element != 0 ) {
                return 0 if $element != 1;
                $leading = $i;
                last;
            }
        }

        if ( $leading == -1 ) {
            $zero_row_encountered = 1;
            next;
        }

        return 0 if $zero_row_encountered;
        return 0 if $leading <= $last_leading;

        for my $r_index ( 0 .. $#{$matrix} ) {
            next if $r_index == $row_index;
            return 0 if $matrix->[$r_index][$leading] != 0;
        }

        $last_leading = $leading;
    }

    return 1;
}

Python Solution (ch-2.py)

def is_reduced_row_echelon(matrix: list[list[int]]) -> int:
    """Return 1 if matrix is in reduced row echelon form, otherwise 0."""
    last_leading = -1
    zero_row_encountered = False

    for row_idx, row in enumerate(matrix):
        if all(x == 0 for x in row):
            zero_row_encountered = True
            continue

        if zero_row_encountered:
            return 0

        leading = next(i for i, x in enumerate(row) if x != 0)
        if row[leading] != 1 or leading <= last_leading:
            return 0

        if any(
            matrix[i][leading] != 0
            for i in range(len(matrix))
            if i != row_idx
        ):
            return 0

        last_leading = leading

    return 1