# ETOOBUSY ðŸš€ minimal blogging for the impatient

# PWC217 - Sorted Matrix

**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!*