algoadvance

Leetcode 36. Valid Sudoku

Problem Statement

Determine if a 9x9 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 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

The Sudoku board could be partially filled, where empty cells are represented by the character ‘.’.

Example:

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

Clarifying Questions

1. Input Constraints: Is it guaranteed that the input will always be a 9x9 grid?
2. Edge Cases: Can there be invalid inputs such as characters other than ‘.’ or digits?
3. Performance: Is there any specific time constraint or performance expectation for large inputs?

Strategy

To determine if a Sudoku board is valid, we need to check three main conditions:

1. No duplicate digits in any row.
2. No duplicate digits in any column.
3. No duplicate digits in any of the nine 3x3 sub-boxes.

We’ll use a hash set to keep track of digits we’ve seen so far for each row, column, and sub-box.

Steps to Implement:

1. Iterate through each cell in the board.
2. For each cell, if it is not empty, check if this number has already been seen in the current row, column, or the corresponding 3x3 sub-box.
3. If any duplicate is found, the board is not valid.
4. If no duplicates are found during the iteration, the board is valid.

Code

public class Solution {
    public boolean isValidSudoku(char[][] board) {
        // HashSet to keep track of the digits we have seen so far in rows, columns, and sub-boxes
        HashSet<String> seen = new HashSet<>();

        // We iterate through every cell in the 9x9 grid board
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char current = board[i][j];
                
                // If the current cell contains a digit (1-9)
                if (current != '.') {
                    // Create unique strings for row, column, and sub-box conditions
                    String rowCheck = current + " in row " + i;
                    String colCheck = current + " in column " + j;
                    String boxCheck = current + " in box " + (i / 3) + "-" + (j / 3);
                    
                    // If any of the strings already exist in the set, it means there is a duplicate
                    if (!seen.add(rowCheck) || !seen.add(colCheck) || !seen.add(boxCheck)) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

Time Complexity Analysis

• Time Complexity: O(1)
  • Since the size of the board is fixed at 9x9, the number of operations we perform is constant.
• Space Complexity: O(1)
  • Similarly, the space used by our hash set is for a maximum of 27 checks (each digit can appear in 3 categories: row, column, and sub-box).

Thus, the solution is highly efficient for the given problem, maintaining constant time and space complexities.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?