Valid Sudoku - LeetCode

// Valid Sudoku - https://leetcode.com/problems/valid-sudoku/


class Solution {

    // Brute Force (Three Grid Passes)
    // Time Complexity: O(n^2)
    // Space Complexity: O(n)
    // public boolean isValidSudoku(char[][] board) {
    //     // Check if rows are valid
    //     for(int row = 0; row < board.length; row++) {
    //         Set<Character> set = new HashSet<>();
    //         for(int col = 0; col < board[0].length; col++) {
    //             if(board[row][col] != '.') {
    //                 if(!set.contains(board[row][col])) {
    //                     set.add(board[row][col]);
    //                 }
    //                 else {
    //                     System.out.println("Invalid Row: " + row);
    //                     return false;
    //                 }


    //             }
    //         }
    //     }


    //     // Check if columns are valid
    //     for(int col = 0; col < board[0].length; col++) {
    //         Set<Character> set = new HashSet<>();
    //         for(int row = 0; row < board.length; row++) {
    //             if(board[row][col] != '.') {
    //                 if(!set.contains(board[row][col])) {
    //                     set.add(board[row][col]);
    //                 }
    //                 else {
    //                     System.out.println("Invalid Column: " + row);

    //                     return false;
    //                 }
    //             }
    //         }
    //     }

    //     // Check if inner 3x3 grids are valid
    //     for(int boxRow = 0; boxRow < 3; boxRow++) {
    //         for(int boxCol = 0; boxCol < 3; boxCol++) {
    //             // inner grid elements
    //             int startRow = boxRow * 3;
    //             int startCol = boxCol * 3;
    //             Set<Character> set = new HashSet<>();
    //             for(int i = 0; i < 3; i++) {
    //                 for(int j = 0; j < 3; j++) {

    //                     int r = startRow + i;
    //                     int c = startCol + j;
    //                     if(board[r][c] != '.') {
    //                         if(!set.contains(board[r][c])) {
    //                             set.add(board[r][c]);
    //                         }
    //                         else {
    //                             return false;
    //                         }
    //                     }
    //                 }
    //             }
    //         }
    //     }

    //     return true;
    // }

    // HashSet (One Pass)
    // Time Complexity: O(n^2)
    // Space Complexity: O(n^2)
    // public boolean isValidSudoku(char[][] board) {
    //     Map<Integer, Set<Character>> rows = new HashMap<>();
    //     Map<Integer, Set<Character>> cols = new HashMap<>();
    //     Map<String, Set<Character>> innerGrids = new HashMap<>();

    //     for(int row = 0; row < board.length; row++) {
    //         for(int col = 0; col < board[0].length; col++) {
    //             if(board[row][col] == '.') {
    //                 continue;
    //             }

    //             char el = board[row][col];

    //             String innerGrid = (row/3) + "," + (col/3);

    //             rows.computeIfAbsent(row, k -> new HashSet<>());
    //             cols.computeIfAbsent(col, k -> new HashSet<>());
    //             innerGrids.computeIfAbsent(innerGrid, k -> new HashSet<>());

    //             if(rows.get(row).contains(el)
    //                 || cols.get(col).contains(el)
    //                 || innerGrids.get(innerGrid).contains(el)) {
    //                     return false;
    //             }

    //             rows.get(row).add(el);
    //             cols.get(col).add(el);
    //             innerGrids.get(innerGrid).add(el);

    //         }
    //     }

    //     return true;
    // }


    // BitMask (One Pass)
    // Time Complexity: O(n^2)
    // Space Complexity: O(n)
    public boolean isValidSudoku(char[][] board) {
        int[] rowMasks = new int[9];
        int[] colMasks = new int[9];
        int[] squareMasks = new int[9];

        for(int r = 0; r < 9; r++) {
            for(int c = 0; c < 9; c++) {
                if(board[r][c] == '.') {
                    continue;
                }

                // 1. Convert char digit to a 0-indexed integer for bit positions.
                // '1' -> 0 (0th bit)
                // '2' -> 1 (1st bit)
                // ...
                // '9' -> 8 (8th bit)
                int digit = board[r][c] - '1';

                // We use the left-shift operator (<<) to create an integer
                // with only the 'digit'-th bit turned on.
                // Example: If digit is '3', digitIndex is 2.
                // 1 << 2  -->  binary ...00000100
                int bitToSet = 1 << digit;

                int boxRow = (r/3);
                int boxCol = (c/3);
                int sqIndex = boxRow * 3 + boxCol;

                // Check if bit has already been set
                // Has this digit been seen in this row before?
                // Has this digit been seen in this col before?
                // Has this digit been seen in this 3x3 square before?
                if((rowMasks[r] & bitToSet) > 0
                    || (colMasks[c] & bitToSet) > 0
                    || (squareMasks[sqIndex] & bitToSet) > 0) {
                        return false;

                }

                rowMasks[r] |= bitToSet;
                colMasks[c] |= bitToSet;
                squareMasks[sqIndex] |= bitToSet;
            }
        }

        return true;
    }
}