You are given 5x5 matrix filled with integers such that each row is sorted from left to right and the first integer of each row is greater than the last integer of the previous row.
Write a script to find a given integer in the matrix using an efficient search algorithm.
Matrix: [ 1, 2, 3, 5, 7 ] [ 9, 11, 15, 19, 20 ] [ 23, 24, 25, 29, 31 ] [ 32, 33, 39, 40, 42 ] [ 45, 47, 48, 49, 50 ] Input: 35 Output: 0 since it is missing in the matrix Input: 39 Output: 1 as it exists in the matrix
This challenge confuses me. We're basically asked to find a number in a sorted list. Which in languages without hashes one would solve with binary search (yielding an \(\mathcal{O} (\log N)\) solution), and in languages with hashes you'd use a hash (yielding an \(\mathcal{O} (1)\) (expected) time solution). Sure, the hash takes linear preprocessing time, but since we're asked to write a script, we're spending linear time reading in the data anyway.
Perhaps the intend was a subroutine which takes a matrix and a target number, but that was not what is being asked. The challenge explicitly asks for a script, which means we have to spend a linear amount of time reading data anyway. So, that's what you get.
The only part where we use the fact we are given a matrix is for the input: the first five lines are assumed to contain the matrix. The rest of the input is taken as numbers to search for.
Only for language lacking hashes/maps/dictionaries/tables, we will make use of the fact the input is sorted. For the majority of languages, the fact input is sorted does not offer additional benefits.
All the solutions first read the matrix (five rows with five integers, separated by white space) from standard input. The rest of the input is taken as numbers to search for — one integer per line.
For our Perl solution, we offer two ways to solve this.
First is a simple hash based solution:
my $MATRIX_SIZE = 5;
my %matrix;
@matrix {<> =~ /-?[0-9]+/g} = () for 1 .. $MATRIX_SIZE;
chomp, say exists $matrix {$_} || 0 while <>;
Here, we read in five lines of data, which we store in a hash.
Then for the rest of the input, we print 1 or 0 depending
on whether the number is in the matrix or not.
Our second solution has a subroutine which takes two arguments: a 5 x 5 matrix (a reference to a two dimensional array), and a number to search for. We're using a bog standard binary search to find the number. Binary search uses a one dimensional structure to search, but we can trivially map a one dimensional coordinate to a two dimensional one by using integer division, and the modulus operation.
my sub bsearch ($matrix, $target) {
my ($min, $max) = (0, $MATRIX_SIZE * $MATRIX_SIZE);
while ($min < $max) {
use integer;
my $mid = ($min + $max) / 2;
#
# To map a 1-d coordinate c to a 2-d pair x, y, we use
# x = floor (c / size), y = c % size.
#
my $cmp = $$matrix [$mid / $MATRIX_SIZE]
[$mid % $MATRIX_SIZE] <=> $target;
if ($cmp < 0) {$min = $mid + 1}
elsif ($cmp > 0) {$max = $mid}
else {return 1}
}
return (0)
}
Find the full program on GitHub.
In AWK, arrays are associative, taking both integers and strings as indices. As such, we can do \(\mathcal{O} (1)\) (expected) time lookups.
By default, AWK splits input lines on white space, which makes
reading in the data easy. First five ($MATRIX_SIZE) lines are
the matrix to search in:
NR <= MATRIX_SIZE {
for (i = 1; i <= NF; i ++) {
matrix [$i] = 1
}
}
The rest of the input are numbers to search for:
NR > MATRIX_SIZE {
print (matrix [$0] ? 1 : 0)
}
Find the full program on GitHub.
Bash also has associative arrays, which we can declare by using the
-A option to declare.
We can then read in five ($MATRIX_SIZE) lines of data. Using
read with the -a option reads a line from
standard input, splits it on white space, and places the fields
in an array (called line in our case). We then add place each
field in the associative array matrix:
declare -A matrix
MATRIX_SIZE=5
for ((i = 1; i <= $MATRIX_SIZE; i ++))
do read -a line
for n in ${line[@]}
do matrix[$n]=1
done
done
We can now read the rest of the input, and print whether or not the read element is in the matrix:
while read number
do echo $((matrix[$number] ? 1 : 0))
done
Find the full program on GitHub.
C does not have native support for hashes or associative arrays. So, for our C solution, we will make use of binary search — which is supported by the standard library.
First order of business is to read 25 integers into an array named
matrix:
# define MATRIX_SIZE 5
# define NR_OF_ELEMENTS (MATRIX_SIZE * MATRIX_SIZE)
int * matrix;
if ((matrix = (int *) malloc (NR_OF_ELEMENTS * sizeof (int))) == NULL) {
perror ("Malloc failed");
exit (1);
}
/*
* Read in the matrix
*/
for (int i = 0; i < NR_OF_ELEMENTS; i ++) {
if (scanf ("%d", &matrix [i]) != 1) {
perror ("Scanf failed");
exit (1);
}
}
We will do the binary search by making use of the bsearch
library call. It does need a comparison function, which takes
two arguments and which returns a negative value if the first
argument is less than the second, zero if the arguments are equal,
and positive if the first argument is larger than the second.
This is the function we will be using:
static int compare (const void * a, const void * b) {
return * (int *) a - * (int *) b;
}
We're now ready to search for the values:
int target;
while (scanf ("%d", &target) == 1) {
printf ("%d\n", bsearch (&target, matrix, NR_OF_ELEMENTS,
sizeof (int), compare) == NULL ? 0 : 1);
}
Find the full program on GitHub.
Lua has tables, which work like associative arrays. It has also a
feature to read a number from standard input: read ("*number"),
which is quite handy for this challenge:
local MATRIX_SIZE = 5
local matrix = {}
--
-- Read in the matrix
--
for i = 1, MATRIX_SIZE * MATRIX_SIZE do
matrix [io . read ("*number")] = 1
end
--
-- Read in the rest, printing 1/0 depending on
-- whether the number is present in the matrix or not.
--
while true do
local target = io . read ("*number")
if target == nil then break end
if matrix [target]
then print (1)
else print (0)
end
end
Find the full program on GitHub.
In Node.js, we first slurp in the entire input, and extract the numbers:
let MATRIX_SIZE = 5
let numbers =
require ("fs")
. readFileSync (0) // Read all.
. toString () // Turn it into a string.
. match (/-?[0-9]+/g)
Then we create the matrix structure:
let matrix = {}
for (let i = 0; i < MATRIX_SIZE * MATRIX_SIZE; i ++) {
matrix [numbers [i]] = 1
}
Now we can check the rest of the numbers if they are present:
for (let j = MATRIX_SIZE * MATRIX_SIZE; j < numbers . length; j ++) {
console . log (matrix [numbers [j]] ? 1 : 0)
}
Find the full program on GitHub.
For our Pascal solution, we make use of Binary Search. We start off
with defining a bsearch method, which takes a matrix (an array of
integers), and a number to search with as arguments, and which returns
1 or 0 depending on whether the number is present or not.
const
matrix_size = 5;
type
matrix_type = Array [1 .. matrix_size * matrix_size] of Longint;
function bsearch (matrix: matrix_type; target: Longint) : Integer;
var
min, mid, max: Integer;
begin
bsearch := 0;
min := 1;
max := matrix_size * matrix_size + 1;
while min < max do
begin
mid := (min + max) div 2;
if matrix [mid] = target then
begin
bsearch := 1;
min := max;
end;
if matrix [mid] < target then
begin
min := mid + 1;
end
else begin
max := mid;
end
end
end;
Reading in the data, and calling the bsearch function:
begin
(* Read in the matrix *)
for i := 1 to matrix_size * matrix_size do
begin
read (matrix [i]);
end;
(* The rest of the input are numbers we want to search *)
while not eof () do
begin
readln (target);
writeln (bsearch (matrix, target));
end;
end.
Find the full program on GitHub.
MATRIX_SIZE = 5
import fileinput
import re
matrix = {}
for i in range (MATRIX_SIZE):
for n in re . findall (r'-?[0-9]+', input ()):
matrix [n] = 1
for line in fileinput . input ():
if line . strip () in matrix:
print ("1")
else:
print ("0")
Find the full program on GitHub.
matrix_size = 5
matrix = {}
(1 .. matrix_size) . each do
ARGF . readline . scan(/-?[0-9]+/) do
|number|
matrix [number] = 1
end
end
ARGF . each_line do
|number|
puts (matrix [number . strip] ? 1 : 0)
end
Find the full program on GitHub.