TL;DR

Here we are with TASK #1 from The Weekly Challenge #217. Enjoy!

# The challenge

You are given a n x n matrix where n >= 2.

Write a script to find 3rd smallest element in the sorted matrix.

Example 1

Input: @matrix = ([3, 1, 2], [5, 2, 4], [0, 1, 3])
Output: 1

The sorted list of the given matrix: 0, 1, 1, 2, 2, 3, 3, 4, 5.
The 3rd smallest of the sorted list is 1.


Example 2

Input: @matrix = ([2, 1], [4, 5])
Output: 4

The sorted list of the given matrix: 1, 2, 4, 5.
The 3rd smallest of the sorted list is 4.


Example 3

Input: @matrix = ([1, 0, 3], [0, 0, 0], [1, 2, 1])
Output: 0

The sorted list of the given matrix: 0, 0, 0, 0, 1, 1, 1, 2, 3.
The 3rd smallest of the sorted list is 0.


# The questions

Usual stuff: weâ€™re assuming that itâ€™s a matrix of numbers, sorting is the regular sorting for reals, â€¦

# The solution

We will completely disregard that itâ€™s a square matrix, and just go through to find out the third smallest. We will keep a list of the three smallest values found along the way, so we will only need to go through the list in one sweep; each sweep will require us from one up to three comparisons, but itâ€™s still bounded by three. Overall, complexity is linear, yay!

To track the three smallest items we keep them in a sorted array of up to three elements. When a fourth sneakes in, we make sure to remove the biggest element so that we go back to three items maximum. This is the sense of array @three-smallest in the following Raku code:

#!/usr/bin/env raku
use v6;
sub MAIN (*@rows) {
my @matrix = @rows.map({ [ .split(/ \s* \, \s* /)Â».Int ] });
put third-smallest(@matrix);
}

sub third-smallest (@matrix) {
my @three-smallest;
for @matrix -> $row { for @$row -> $item { my$idx = @three-smallest.elems;
--$idx while$idx > 0 && @three-smallest[$idx - 1] >$item;
next if $idx > 2; @three-smallest.splice($idx, 0, $item); @three-smallest.pop while @three-smallest > 3; } } return @three-smallest[*-1]; }  The Perl version is pretty much a straight translation: #!/usr/bin/env perl use v5.24; use warnings; my @matrix = map { [ split m{\s*,\s*}mxs ] } @ARGV; say third_smallest(@matrix); sub third_smallest { my @three_smallest; for my$row (@_) {
for my $item ($row->@*) {
my $idx = scalar(@three_smallest); --$idx while $idx > 0 &&$three_smallest[$idx - 1] >$item;
next if $idx > 2; splice(@three_smallest,$idx, 0, $item); pop(@three_smallest) while @three_smallest > 3; } } return$three_smallest[-1];
}


Stay safe!

Comments? Octodon, , GitHub, Reddit, or drop me a line!