Solving Leetcode 36. Valid Sudoku

This past week I stepped into my friend Riley’s shoes to facilitate algo-club, Flatiron School’s unofficial standing meeting of graduates, who come together to well, practice algorithms for 2 hours per day, Monday through Friday. But it’s become more than that. While there’s been a revolving door of members, most parting ways upon beginning their first job in tech, no matter how new or old folks are, there’s always been an easy formation of a core group. This week we sent off two regular members to jobs (and one to a well-deserved vacation), and it was so nice to see newer or quieter folks feeling comfortable enough to step up and share their code and their thought processes.

This week I’m going to walk us all through another Leetcode medium. This one was fun. We were randomly paired and sent off to breakout rooms to solve this in under 45 minutes. My partner Ryan and I got right to the last little bit before our room closed, and then finished up with the club as we walked through what we had so far. Very little in this world is more satisfying than being right on the edge of solving something, and then bam, everything snapping into place in the last minute. So come along with me, let’s determine if a sudoku board is valid.

36. Valid Sudoku — Medium

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

Each row must contain the digits 1-9 without repetition.

Each column must contain the digits 1-9 without repetition.

Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Note:

A Sudoku board (partially filled) could be valid but is not necessarily solvable.

Only the filled cells need to be validated according to the mentioned rules.

Example 1:

Input: board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: true

Example 2:

Input: board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

Constraints:

board.length == 9

board[i].length == 9

board[i][j] is a digit 1-9 or '.'.

Fun, right? Hey, at least we’re just determining its validity and not its solve-ability! For a sudoku to be valid we need unique number in every row, column, and 3x3 miniboard. So, let’s take our overall input board and find our rows, columns, and miniboards!

I decided to create three variables and to use Set to determine if there are any duplicates in each one. I chose sets because they only store unique values, and since we’re looking for unique values it only made sense to start down this path.

I knew that checking rows and columns was going to 1. require a nested loop and 2. be the easier task, so I started there and left miniboard to wait its turn. One of my favorite things to do is check 2-d arrays both horizontally and vertically in the same pass. You do this by inverting your i and j. If this is new to you, when it clicks it’s like some excellent magic. Here’s a walk-through of what that inner loop looks like where we’re checking our first row and first column.

So we know how to check our rows and columns, how do we know when we get a duplicate? And more importantly how do we completely ignore all the empty spots that are denoted by "."?

We can use an if statement where as long as the value of the current index does not equal '.' then we’ll check its uniqueness, otherwise, we’re not going to do anything with our blank spaces. They are irrelevant to determining validity. I included an if statement for miniNum because I know I need it to exist, I just hadn’t figured out the math yet, so it’s not declared yet.

Now, how to check for uniqueness? Set has a .has method that will check if an element is present in the Set object, and return a boolean true or false. This is especially convenient as a boolean is our expected return for the overall problem! So we know that if a row, column, or miniboard set already has the rowNum, colNum, or miniNum then the sudoku is not valid and we can return false. If the set does not yet have the number then we simply use the .add method to add it to the set.

Sweet! Now we’re checking our rows and our columns and we’re good to go there. Now let’s figure out how to determine the parameters of our miniBoard. We’re going to need some math!

To figure out what math would work I started with determing what indices I needed to check for each mini-board. I knew that once I figured out how to get the right indices for my first, or top left board all I would have to do is multiply by three to keep on moving to the next board.

To get the first digit, my row, I knew it needed to stay the same for three loops through j, Math.floor was just what I needed, knowing that if I divided i and j by three I would drop to the same digit for exactly three indices. Figuring out the need for .floor and division it was just logical for me to look at modulo to see if it could be used to check through my columns. Turns out if you modulo your numbers by 3 it increments just perfectly.

So last thing we have to do is add in our miniNum math and return true! Since we’ve set a return to false if we come across any duplicates in each of our sets as we loop we’ve covered all of our false inducing bases, so with a simple return true outside of both of our for loops we can call it a wrap!

Thanks for walking through another algorithm with me! I’ll tackle the hard sudoku solver someday I’m sure. But until then, I’ll keep rocking and rolling, solving medium leetcodes!