How do you solve Valid Sudoku on LeetCode?

Valid Sudoku (LeetCode #36) can be solved using Brute Force or Optimal Solution (Hash Map). The optimal approach is Optimal Solution (Hash Map) with O(n) time complexity and O(n) space complexity. Key insight: Recognizing that Sudoku validation can be broken down into three distinct checks (rows, columns, boxes) allows for a systematic approach.

What is the brute force solution for Valid Sudoku?

The brute force approach for Valid Sudoku is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves checking each row, column, and 3x3 sub-box for duplicate numbers. We can iterate through the board and validate each section one by one. This is straightforward but can be inefficient. The optimal Optimal Solution (Hash Map) approach improves this to O(n).

What algorithm or data structure is used to solve Valid Sudoku?

Valid Sudoku uses the following concepts: Array, Hash Table, Matrix. The recommended patterns to study are: Hash Map, Array, Two Pointers.

What are the interview tips for Valid Sudoku?

When you first see this problem, clarify the rules of Sudoku and ensure you understand what makes a board valid. Communicate your approach clearly, emphasizing the three checks and how you will implement them. Mention edge cases, such as completely empty boards or boards with only one filled cell, to show your thorough understanding.

What are common mistakes when solving Valid Sudoku?

Students often forget to check all three conditions (rows, columns, boxes) and may only check rows or columns. Another common mistake is not handling the empty cells ('.') correctly, leading to false positives.

#36

Valid Sudoku

Medium

ArrayHash TableMatrixHash MapArrayTwo Pointers

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution (Hash Map)★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

Using hash maps (or sets) allows us to efficiently track seen numbers for rows, columns, and boxes simultaneously. This reduces the need for multiple passes and makes the solution cleaner and faster.

⚙️

Algorithm

5 steps

1Step 1: Create three sets to keep track of seen numbers for rows, columns, and boxes.
2Step 2: Iterate through each cell in the board.
3Step 3: For each filled cell, check if the number has already been seen in the respective row, column, or box.
4Step 4: If a duplicate is found, return false. If not, add the number to the respective sets.
5Step 5: If no duplicates are found after checking all cells, return true.

solution.py31 lines

1# Full working Python code with comments
2
3def isValidSudoku(board):
4    rows = [set() for _ in range(9)]
5    cols = [set() for _ in range(9)]
6    boxes = [set() for _ in range(9)]
7
8    for r in range(9):
9        for c in range(9):
10            num = board[r][c]
11            if num != '.':
12                box_index = (r // 3) * 3 + (c // 3)
13                if (num in rows[r]) or (num in cols[c]) or (num in boxes[box_index]):
14                    return False
15                rows[r].add(num)
16                cols[c].add(num)
17                boxes[box_index].add(num)
18
19    return True
20
21# Example usage:
22board = [["5","3",".",".","7",".",".",".","."],
23         ["6",".",".","1","9","5",".",".","."],
24         [".","9","8",".",".",".",".","6","."],
25         ["8",".",".",".","6",".",".",".","3"],
26         ["4",".",".","8",".","3",".",".","1"],
27         ["7",".",".",".","2",".",".",".","6"],
28         [".","6",".",".",".",".","2","8","."],
29         [".",".",".","4","1","9",".",".","5"],
30         [".",".",".",".","8",".",".","7","9"]]
31print(isValidSudoku(board))  # Output: True

ℹ

Complexity note: The time complexity is O(n) because we are iterating through each of the 81 cells once. The space complexity is O(n) due to the sets used to track seen numbers, which can grow up to 27 (9 rows + 9 columns + 9 boxes).

1Recognizing that Sudoku validation can be broken down into three distinct checks (rows, columns, boxes) allows for a systematic approach.
2Using sets to track seen numbers is efficient and helps avoid unnecessary complexity in checking for duplicates.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.