8. Valid Sudoku

Valid Sudoku – LeetCode Solutions: Brute Force to Optimal

Problem:
Determine if a given 9×9 Sudoku board is valid. A board is valid if:

1. Each row contains the numbers 1-9 with no duplicates.
2. Each column contains the numbers 1-9 with no duplicates.
3. Each of the 9 sub-boxes (3×3 grids) contains the numbers 1-9 with no duplicates.

Note:

• Empty cells are represented by the character '.' and can be ignored during validation.
• Only the filled cells need to be validated according to the above conditions.

---

Approach 1: Brute Force (Triple Nested Loops)

In the brute-force approach, we:

1. Check each row for duplicates.
2. Check each column for duplicates.
3. Check each 3×3 subgrid for duplicates.

This involves iterating through each cell of the board, keeping track of visited numbers in each row, column, and subgrid using a Set.

---

Code (Java – Brute Force):

import java.util.HashSet;

public class ValidSudokuBruteForce {
    public boolean isValidSudoku(char[][] board) {
        // Validate rows
        for (int i = 0; i < 9; i++) {
            HashSet<Character> rowSet = new HashSet<>();
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.' && !rowSet.add(board[i][j])) {
                    return false;
                }
            }
        }

        // Validate columns
        for (int i = 0; i < 9; i++) {
            HashSet<Character> colSet = new HashSet<>();
            for (int j = 0; j < 9; j++) {
                if (board[j][i] != '.' && !colSet.add(board[j][i])) {
                    return false;
                }
            }
        }

        // Validate sub-boxes (3x3 grids)
        for (int boxRow = 0; boxRow < 9; boxRow += 3) {
            for (int boxCol = 0; boxCol < 9; boxCol += 3) {
                HashSet<Character> boxSet = new HashSet<>();
                for (int i = 0; i < 3; i++) {
                    for (int j = 0; j < 3; j++) {
                        char num = board[boxRow + i][boxCol + j];
                        if (num != '.' && !boxSet.add(num)) {
                            return false;
                        }
                    }
                }
            }
        }

        return true;  // Board is valid if no duplicates are found
    }
}

---

Time and Space Complexity:

• Time Complexity: O(9² + 9² + 9²) ≈ O(243) ≈ O(1)
  Since the board size is fixed at 9×9, it can be considered constant.
• Space Complexity: O(9) ≈ O(1) for each set used to track duplicates.

---

Approach 2: Optimized Solution Using Arrays (Optimal)

Instead of using HashSet, we can further optimize the space by using arrays to track the occurrence of digits.

• Use 2D arrays row, col, and box to keep track of numbers.
• Map each number to an index and increment the index when you encounter that number.

Code (Java – Optimal Solution):

public class ValidSudokuOptimal {
    public boolean isValidSudoku(char[][] board) {
        int[][] row = new int[9][9];  // To track numbers in each row
        int[][] col = new int[9][9];  // To track numbers in each column
        int[][] box = new int[9][9];  // To track numbers in each 3x3 box

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int num = board[i][j] - '1';  // Convert char '1'-'9' to index 0-8
                    int boxIndex = (i / 3) * 3 + (j / 3);  // Calculate box index

                    // Check and update the tracking arrays
                    if (row[i][num] == 1 || col[j][num] == 1 || box[boxIndex][num] == 1) {
                        return false;  // If number is already seen in row, col, or box
                    }

                    row[i][num] = 1;
                    col[j][num] = 1;
                    box[boxIndex][num] = 1;
                }
            }
        }

        return true;  // Board is valid
    }
}

---

Time and Space Complexity:

• Time Complexity: O(81) ≈ O(1)
  We still iterate through every cell, which is constant time due to the fixed board size.
• Space Complexity: O(9 * 9) = O(81) ≈ O(1) for the row, col, and box arrays.

---

Comparison of Approaches:

Approach	Time Complexity	Space Complexity	Description
Brute Force (HashSet)	O(1)	O(9 + 9 + 9)	Uses sets for row, col, and box tracking
Optimal (Arrays)	O(1)	O(81) ≈ O(1)	Uses arrays instead of sets for tracking

---

Conclusion:

• Both approaches solve the problem efficiently due to the fixed grid size.
• The Optimal Array Approach is more space-efficient in terms of low-level operations and is the best choice for interviews.