The Weekly Challenge 270

Task 1: Special Positions

Method Explanation

A brute-force check scans row i and column j for every cell that contains a 1, resulting in an $O(m \times n \times (m + n))$ runtime.

Instead, we can observe that since matrix entries are exclusively 0 or 1:

• All other elements in row i are 0 if and only if the sum of row i equals 1.
• All other elements in column j are 0 if and only if the sum of column j equals 1.

We perform an initial pass to compute row sums and column sums in $O(m \times n)$ time. In a second pass, a cell (i, j) is special if and only if:

matrix[i][j] == 1 && row_sums[i] == 1 && col_sums[j] == 1

This optimizes both the time complexity to $O(m \times n)$ and auxiliary space to $O(m + n)$.

Perl Solution

sub num_special_positions ($matrix) {
    my $rows = scalar @$matrix;
    return 0 if $rows == 0;
    my $cols = scalar @{ $matrix->[0] };
    return 0 if $cols == 0;

    my @row_sums = (0) x $rows;
    my @col_sums = (0) x $cols;

    for my $i ( 0 .. $rows - 1 ) {
        for my $j ( 0 .. $cols - 1 ) {
            if ( $matrix->[$i][$j] == 1 ) {
                $row_sums[$i]++;
                $col_sums[$j]++;
            }
        }
    }

    my $special_count = 0;
    for my $i ( 0 .. $rows - 1 ) {
        next if $row_sums[$i] != 1;
        for my $j ( 0 .. $cols - 1 ) {
            if ( $matrix->[$i][$j] == 1 && $col_sums[$j] == 1 ) {
                $special_count++;
            }
        }
    }

    return $special_count;
}

Python Solution

def num_special_positions(matrix: list[list[int]]) -> int:
    """Return the number of special positions in a binary matrix."""
    if not matrix or not matrix[0]:
        return 0

    rows = len(matrix)
    cols = len(matrix[0])

    row_sums = [sum(row) for row in matrix]
    col_sums = [sum(matrix[r][c] for r in range(rows)) for c in range(cols)]

    special_count = 0
    for r in range(rows):
        if row_sums[r] != 1:
            continue
        for c in range(cols):
            if matrix[r][c] == 1 and col_sums[c] == 1:
                special_count += 1

    return special_count

Task 2: Equalize Array

Method Explanation

Let $n$ be the length of the array:

• If $n \le 1$, the array is already equalized at cost 0.
• If $n = 2$, any Level 2 operation increases both elements simultaneously, preserving their difference. Thus, Level 2 cannot reduce the disparity between the two values; only Level 1 operations are effective, costing |ints[0] - ints[1]| * x.
• If $2x \le y$, paired operations are no cheaper than two independent single increments. The optimal strategy is to increment each element to $\max(ints)$ strictly using Level 1.
• When $2x > y$ and $n \ge 3$, pairing increments saves cost. However, the equalized value $T$ is not necessarily restricted to $\max(ints)$—increasing $T$ may allow more Level 2 pairings to eliminate costly singleton increments.

For a given target $T \ge \max(ints)$:

• Total increments needed: $\text{total\_diff} = \sum (T - \text{ints}[i])$.
• Maximum increments needed by a single element: $\text{max\_diff} = T - \min(ints)$.

If $2 \times \text{max\_diff} \le \text{total\_diff}$, no single element dominates, meaning we can pair all operations except at most one leftover: $$\text{pairs} = \lfloor \text{total\_diff} / 2 \rfloor, \quad \text{singles} = \text{total\_diff} \pmod 2$$

Otherwise, the minimum element requires more increments than all other elements combined. The other elements can at most provide $\text{total\_diff} - \text{max\_diff}$ pairings, leaving the rest to be incremented individually: $$\text{pairs} = \text{total\_diff} - \text{max\_diff}, \quad \text{singles} = \text{total\_diff} - 2 \times \text{pairs}$$

The condition $2 \times \text{max\_diff} \le \text{total\_diff}$ is guaranteed to be satisfied once $T$ reaches $\max + (\max - \min)$. Beyond that point, each increment to $T$ adds $n$ increments at cost at least $\lfloor n/2 \rfloor \times y > 0$. Hence, we only need to search $T \in [\max, \max + (\max - \min) + 2]$.

Perl Solution

sub min_cost_to_equal_elements ($ints, $x, $y) {
    my $n = scalar @$ints;
    return 0 if $n <= 1;
    if ( $n == 2 ) {
        return abs( $ints->[0] - $ints->[1] ) * $x;
    }

    my $min_val = $ints->[0];
    my $max_val = $ints->[0];
    for my $val (@$ints) {
        $min_val = $val if $val < $min_val;
        $max_val = $val if $val > $max_val;
    }

    if ( 2 * $x <= $y ) {
        my $cost = 0;
        $cost += ( $max_val - $_ ) * $x for @$ints;
        return $cost;
    }

    my $best  = undef;
    my $limit = $max_val + ( $max_val - $min_val ) + 2;

    for my $target ( $max_val .. $limit ) {
        my $total_diff = 0;
        $total_diff += ( $target - $_ ) for @$ints;
        my $max_diff = $target - $min_val;

        my ( $pairs, $singles );
        if ( 2 * $max_diff <= $total_diff ) {
            $pairs   = int( $total_diff / 2 );
            $singles = $total_diff % 2;
        }
        else {
            $pairs   = $total_diff - $max_diff;
            $singles = $total_diff - 2 * $pairs;
        }

        my $cost = ( $pairs * $y ) + ( $singles * $x );
        if ( !defined $best || $cost < $best ) {
            $best = $cost;
        }
    }

    return $best;
}

Python Solution

def min_cost_to_equal_elements(ints: list[int], x: int, y: int) -> int:
    """Return the minimum cost to make all elements in ints equal."""
    n = len(ints)
    if n <= 1:
        return 0
    if n == 2:
        return abs(ints[0] - ints[1]) * x

    max_val = max(ints)
    min_val = min(ints)

    if 2 * x <= y:
        return sum(max_val - num for num in ints) * x

    best = float("inf")
    limit = max_val + (max_val - min_val) + 2

    for target in range(max_val, limit + 1):
        total_diff = sum(target - num for num in ints)
        max_diff = target - min_val

        if 2 * max_diff <= total_diff:
            pairs = total_diff // 2
            singles = total_diff % 2
        else:
            pairs = total_diff - max_diff
            singles = total_diff - 2 * pairs

        cost = pairs * y + singles * x
        if cost < best:
            best = cost

    return int(best)