Valid Sudoku Challenge
Recently I had to take a code challenge that dealt with matrices and although I felt comfortable with them on paper, I quickly realized how difficult it was for someone of my experience level to go about it.
The Problem:
Given an NxN matrix determine if the matrix is valid. A matrix is valid if every row and column contains exactly the number 1 to N. So in a 4 by 4 matrix, each row and column will only contain the numbers 1 to 4. If the matrix is valid return “VALID and if it isn’t return “INVALID”.
[[1,2,3],
[2,3,1],
[3,1,2]]
The matrix above is valid. A 3 by 3 matrix that only contains the numbers 1 through 3. For each row and column, there are no repeating numbers.
[[3,5,7],
[2,4,8],
[9,1,6]]
The matrix above is invalid. Although each number is unique within the row and column they reside in, some elements exceed the maximum allowable number for the matrix which in this case is 3.
My Solution:
When I see matrix problems I think of nested for loops as matrices are represented as arrays within an array. For this solution I’ll write out my pseudo as to give others the chance to do it on their own. The general idea is to use Hash Tables to check if the elements of the rows and columns are unique.
Create an edge case such that if the elements within the matrix is larger than the length of the matrix, return “INVALID”
Create a hash table with keys “row” and “column”. Both keys have a value of an empty hash. (ie. let store = {rows:{}, cols:{}}
Created a nested for loop for i and j starting at 0 and ending at the length of the matrix to access the elements of the matrix.
Create variable that holds the current element the loop is in.
For our row:
If the key(i) does not exist in our hash, create a key out of the index(i) and a value of an empty array. Push the current element into the array.
(ie. store = {rows:{0:[1]}}
If it does exist and the array does not include the current element, just push it into the array. (ie. store = {rows:{0:[1,2,3]}}.
If the value already exists within the array, then we return “INVALID” because the current number is not unique to the row.
Do the same thing as above with the columns(j). (i.e store = {cols:{0:[1,2,3]}})
If all elements are pushed into the hash table, return “VALID”.
Refactoring:
This solution as you can see is not the best in terms of time complexity with nested for loops. This was my brute force way of solving a problem but I can see how this would not be of best use in the real world. I’d love to see how anyone else would tackle this problem. As always, happy coding!
Weekly Photo:
