The Weekly Challenge 266

Method Explanation

The problem asks us to identify words that satisfy two specific conditions:

• The word must appear exactly once in either $line1 or $line2.
• The word must not appear at all in the opposite sentence.

A clean and efficient approach is to build frequency tables (hash tables or counters) for both sentences:

1. Tokenize each sentence into words by splitting on whitespace.
2. Count the occurrences of each word in two separate frequency maps, count1 and count2.
3. Iterate through the words of the first sentence and select those where count1[word] == 1 and word is not in count2.
4. Similarly, iterate through the words of the second sentence and select those where count2[word] == 1 and word is not in count1.
5. If the resulting list is non-empty, return it; otherwise return a singleton with an empty string ('') as specified.

This solution runs in linear time $O(L_1 + L_2)$ where $L_1$ and $L_2$ are the lengths of the sentences, with auxiliary space proportional to the unique words in each sentence.

Perl Solution

use v5.38;
use warnings;
use Type::Params -sigs;
use Types::Standard qw(Str);

signature_for uncommon_words => (
    method     => 0,
    positional => [ Str, Str ],
);

sub uncommon_words ( $line1, $line2 ) {
    my %count1;
    my @words1 = split ' ', $line1;
    $count1{$_}++ for @words1;

    my %count2;
    my @words2 = split ' ', $line2;
    $count2{$_}++ for @words2;

    my @result;
    for my $word ( grep { $count1{$_} == 1 && !exists $count2{$_} } @words1 ) {
        push @result, $word;
    }
    for my $word ( grep { $count2{$_} == 1 && !exists $count1{$_} } @words2 ) {
        push @result, $word;
    }

    return @result ? @result : ('');
}

Python Solution

from collections import Counter


def uncommon_words(line1: str, line2: str) -> tuple[str, ...]:
    """Find all uncommon words in any order in the given two sentences."""
    words1 = line1.split()
    words2 = line2.split()

    counter1 = Counter(words1)
    counter2 = Counter(words2)

    uncommon: list[str] = [
        word for word in counter1 if counter1[word] == 1 and word not in counter2
    ]
    for word in counter2:
        if counter2[word] == 1 and word not in counter1:
            uncommon.append(word)

    return tuple(uncommon) if uncommon else ("",)

Method Explanation

For an $N \times N$ matrix with row index $i$ and column index $j$ (both $0$-indexed):

• An element lies on the main diagonal if $i == j$.
• An element lies on the anti-diagonal if $i + j == N - 1$.

Therefore, cell $(i, j)$ belongs to a diagonal if and only if $i == j$ or $i + j == N - 1$.

We check every entry $(i, j)$:

• If $(i, j)$ is on a diagonal, the element must be non-zero (matrix[i][j] != 0). If it is zero, we immediately return false.
• If $(i, j)$ is off the diagonals, the element must be zero (matrix[i][j] == 0). If it is non-zero, we immediately return false.

If all $N^2$ elements satisfy their respective requirement, the matrix is an X Matrix, and we return true. This requires $O(N^2)$ time in the worst case and $O(1)$ additional space.

Perl Solution

use v5.38;
use warnings;
use Type::Params -sigs;
use Types::Standard qw(ArrayRef Int);

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

sub is_x_matrix ($matrix) {
    my $size = scalar @$matrix;

    for my $i ( 0 .. $size - 1 ) {
        for my $j ( 0 .. $size - 1 ) {
            if ( $i == $j || $i + $j == $size - 1 ) {
                return 0 if $matrix->[$i][$j] == 0;
            }
            else {
                return 0 if $matrix->[$i][$j] != 0;
            }
        }
    }

    return 1;
}

Python Solution

def is_x_matrix(matrix: list[list[int]]) -> bool:
    """Determine whether a given square matrix is an X Matrix."""
    n = len(matrix)
    for i in range(n):
        for j in range(n):
            if i == j or i + j == n - 1:
                if matrix[i][j] == 0:
                    return False
            else:
                if matrix[i][j] != 0:
                    return False
    return True