[Solution]Problem 68: Valid Sudoku [Netflix]

Hashing, Sudoku, Verification

To learn more about the newsletter, check our detailed About Page + FAQs

To help me understand you better, please fill out this anonymous, 2-min survey. If you liked this post, make sure you hit the heart icon in this email.

Recommend this publication to Substack over here

Take the next step by subscribing here

---

How did you do on this question?

This is one my favs to ask those who reach out to me for mock-interview practice.

This problem can be found as problem 36. Valid Sudoku on Leetcode.

Problem

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

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

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

3. 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 '.'.

You can test your solution here

Some of you saw the post about me giving this newsletter away to those struggling and were moved. Y’all wanted to support me but didn’t have the finances to pay for a full subscription. I really appreciate that. If you would like to support the giveaway of this newsletter to people struggling financially, you can use the following links-

Venmo: https://account.venmo.com/u/FNU-Devansh

Paypal: paypal.me/ISeeThings

If there are any other alternatives you’d like to use, let me know. Now let’s get into the solution-

Step 1: Understanding the Scope of this Problem

The first and most important step of this problem is identifying the scope of this problem. This problem is one of my favorites to give out to those who reach out to me for mock interviews. I’ve noticed a tendency that in many of my students to jump into the problem w/o paying attention to the little details. They end up overcomplicating the problem because of this.

They often look at this problem, see the Sudoku (and validation), and immediately jump to backtracking. However, that is not necessary. The first step to solving this problem is to really understand what it’s asking. In essence, this problem is asking you to validate 3 different conditions. We need to ensure there are no repeating elements in-

1. A row

2. A column

3. A grid

That’s all we need to do. So how do we proceed? How can we check if we have a certain element within a group?

Step 2: Checking for Membership

Most of you should be very intimate with Hashing and Dictionaries (HashTables) and HashSets. If you’re not, we covered the basics in a Math Monday, which you can check out below.

Understanding Hashing [Math Mondays]

Both sets and dicts allow you test for membership in O(1) time. They also have O(1) insertion, which makes them ideal for this task. So how do we pick which datastructure will be ideal for our needs? Let’s look at the difference between them-

Dictionaries use hashing to map a key to a value. Great if we want to figure out which value(s) is associated with a particular key. Sets are better if we just need to know if we have seen a particular key before.

So which will be useful here? Let’s figure that out. For doing so, let’s figure out how we will check for duplicates.

My expression when people try backtracking here. This is one of my favorite meme formats.

Step 3: Detecting Duplicates

Let’s build our duplicate detection system up from the basics. To find a duplicate in a row, all we need to do is go through that row and check if we have seen a value before. This utility is served by sets. So far, so good. So we know that for an index, we will go through the corresponding row+column+grid, and store all the elements in a corresponding set. To check for duplicates, we just need to see if that value is in the set.

Is that all? Nope. There is one thing that I haven’t covered about duplicate detection. Try to see if you can spot it.

No cheating.

Rushing ahead will only hurt your interview preparation.

As it is, this method has a lot of repeated work. How? Say, you do this for the first row and move to the 2nd row. In our current solution, you will have to validate every column and the first 3 grids again. Both these were already tested in when you checked your first row. You could do possibly use some clever conditions to work around this, but that will take a lot of time, be ugly, and there are guarantees it will work. You want to keep your work simple.

We want some way to keep track of the values we have seen for any corresponding row+col+grid. A set can’t store this directly, because it won’t know what row/col/grid we’re in. It only tracks the values seen so far, not where we saw them.

So we can use a dict to track values seen in every r/c/g. rows[i] will give us the values seen at the ith row (and the same for others). Since we need to traverse each of the values given by rows[i] (to check for membership), we will still use a set to represent this. Take a second to let this sink in.

For this question, we will use a dict with the key representing a row/column/grid. Our value returned for the key will be a hash set. We are nesting sets inside a dict. Talk about inception. And they say Christopher Nolan has the best plot twists. This will give us the following initialization code.

        cols = collections.defaultdict(set)
        rows = collections.defaultdict(set)
        squares = collections.defaultdict(set)

The more advanced amongst you will be wondering one thing. This approach works for rows and cols pretty easily. But how will be track grids? What will our key for a grid be? How will we check for the value in the appropriate grid? Let’s cover that.

Step 4: Grid Math

Don’t worry, this isn’t too complex.

Think back to every grid in the Sudoku grid. We know that we will have to use the index of our cell (the (row,col) location in the grid) to compute the correct grid. The simplest way to do so would be to use the top left location of every grid as a key. For any given cell, we use the location of that cell to find the correct top left corner.

But how do we do that?

Take a look at how the grids are designed. We know that each grid will be 3x3. This means that every row on the grid will be one of three things-

1. r%3 ==0

2. r%3==1

3. r%3==2

The same holds true for columns. Why is this important?

This means that every (r,c) location in the same grid will be the same integer multiple of 3 as the top left value of the grid. (0,0), (1,2), (2,2), and (0,2) all have the same value in the function (r//3,c//3). This will hold true for every grid.

To those of you that want to sharpen your problem-solving, I would suggest turning this into a more rigorous proof. The idea stays the same, but adding rigor is a great way to sharpen the process. That will help you discover these patterns yourself.

This was the other problem that we had to fix about this question. With it out of the way, we can now get to coding up the solution.

Step 5: Coding it Up

Once we figure out the correct grid checking, the code becomes very simple-

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        cols = collections.defaultdict(set)
        rows = collections.defaultdict(set)
        squares = collections.defaultdict(set)  # key = (r /3, c /3)

        for r in range(9):
            for c in range(9):
                if board[r][c] == ".":
                    continue
                if (
                    board[r][c] in rows[r]
                    or board[r][c] in cols[c]
                    or board[r][c] in squares[(r // 3, c // 3)]
                ):
                    return False
                cols[c].add(board[r][c])
                rows[r].add(board[r][c])
                squares[(r // 3, c // 3)].add(board[r][c])

        return True
 

Time Complexity- O(n^2) technically it’s constant time (since Sudoku is 9x9). We visit every cell of an nxn Sudoku board.

Space Complexity- O(n^2). We store the value seen in every location.

Loved the solution? Hate it? Want to talk to me about your crypto portfolio? Get my predictions on the UCL or MMA PPVs? Want an in-depth analysis of the best chocolate milk brands? Reach out to me by replying to this email, in the comments, or using the links below.

Stay Woke. I’ll see you living the dream.

Go kill all,

Devansh <3

Reach out to me on:

Instagram: https://www.instagram.com/iseethings404/

Message me on Twitter: https://twitter.com/Machine01776819

My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/

My content:

Read my articles: https://rb.gy/zn1aiu

My YouTube: https://rb.gy/88iwdd

Get a free stock on Robinhood. No risk to you, so not using the link is losing free money: https://join.robinhood.com/fnud75