Same row column

You are given an n x n matrix containing integers from 1 to n.

Write a script to find if every row and every column contain all the integers from 1 to n.

Examples

Example 1
Input: @matrix = ([1, 2, 3, 4],
                  [2, 3, 4, 1],
                  [3, 4, 1, 2],
                  [4, 1, 2, 3])
Output: true

Example 2
Input: @matrix = ([1])
Output: true

Example 3
Input: @matrix = ([1, 2, 5],
                  [5, 1, 2],
                  [2, 5, 1])
Output: false
Elements are out of range 1..3.

Example 4
Input: @matrix = ([1, 2, 3],
                  [1, 2, 3],
                  [1, 2, 3])
Output: false

Example 5
Input: @matrix = ([1, 2, 3],
                  [3, 1, 2],
                  [3, 2, 1])
Output: false

Analysis

A simple challenge for which someone will probably have a one-line solution.

But is it really so simple? No limit has been placed on the size of the matrix, and it could be - say - 1000 x 1000 with a million elements, so let's look for an efficient solution.

My solution inspects each element of the matrix a maximum of once, and does the following:

• Checks that the value of the element is in the range 1 .. $n: if not, returns false
• Checks that the value has not been seen already in the same row or column: if it has, returns false
• Records that it has been seen in the current row and column

Try it 

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge/381/1

use v5.26;    # The Weekly Challenge - 2026-07-06
use utf8;     # Week 381 - task 1 - Same row column
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;

same_row_column([[1, 2, 3, 4],
                 [2, 3, 4, 1],
                 [3, 4, 1, 2],
                 [4, 1, 2, 3]]);
                 
same_row_column([[1]]);

same_row_column([[1, 2, 5],
                 [5, 1, 2],
                 [2, 5, 1]]);
                 
same_row_column([[1, 2, 3],
                 [1, 2, 3],
                 [1, 2, 3]]);
                 
same_row_column([[1, 2, 3],
                 [3, 1, 2],
                 [1, -1, 77]]);

sub same_row_column {
    
    my ($matrix, @good, $m, $row, $col, $in_row, $in_col, $value, $test);
    
    # initialise
    $matrix = shift;
    $m = scalar @$matrix - 1;  # $m == $n - 1
    print_matrix($matrix, $m, qq[Input: ]);

    # survey matrix
    for $row (0 .. $m) {
        for $col (0 .. $m) {
            $value = $matrix->[$row]->[$col];
            unless ($value >= 1 and $value <= $m + 1) {
                say qq[Output: false - out of range value: $value];
                return;
            }
            if ($in_row->[$row]->[$value] or 
                $in_col->[$col]->[$value]) {
                say qq[Output: false - duplicated value: $value];
                return;
            }   
            $in_row->[$row]->[$value] = $in_col->[$col]->[$value] = 1;
        }
    }
    
    # otherwise ...
    say qq[Output: true];
}

sub print_matrix {
    
    my ($matrix, $cols, $legend, $row, $rows);
    
    # print array as a matrix with $cols columns
    ($matrix, $cols, $legend) = @_;
    $rows = $cols;
    say '';
    for $row (0 .. $rows) {
        say qq{$legend [} . join(', ', @{$matrix->[$row]}) . ']'
                . ($row < $rows ? ',' : '');
        $legend = ' ' x length($legend);
    }
}

26 lines of code

Output from script

Input:  [1, 2, 3, 4],
        [2, 3, 4, 1],
        [3, 4, 1, 2],
        [4, 1, 2, 3]
Output: true

Input:  [1]
Output: true

Input:  [1, 2, 5],
        [5, 1, 2],
        [2, 5, 1]
Output: false - 3 not in all rows and columns

Input:  [1, 2, 3],
        [1, 2, 3],
        [1, 2, 3]
Output: false - 2 not in all rows and columns

Input:  [4, 5, 6],
        [7, 8, 9],
        [0, -1, 77]
Output: false - 1 not in all rows and columns