36. Valid Sudoku

BF (my solution)

class Solution {
    public boolean isValidSudoku(char[][] board) {
        // check rows
        for (int i = 0; i < 9; i++) {
            boolean[] seen = new boolean[9];
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int idx = board[i][j] - '1';
                    if (seen[idx]) return false;
                    seen[idx] = true;
                }
            }
        }

        // check columns
        for (int i = 0; i < 9; i++) {
            boolean[] seen = new boolean[9];
            for (int j = 0; j < 9; j++) {
                if (board[j][i] != '.') {
                    int idx = board[j][i] - '1';
                    if (seen[idx]) return false;
                    seen[idx] = true;
                }
            }
        }

        // check 3x3 sub-boxes
        for (int boxRow = 0; boxRow < 3; boxRow++) {
            for (int boxCol = 0; boxCol < 3; boxCol++) {
                boolean[] seen = new boolean[9];
                for (int i = 0; i < 3; i++) {
                    for (int j = 0; j < 3; j++) {
                        int row = boxRow * 3 + i;
                        int col = boxCol * 3 + j;
                        if (board[row][col] != '.') {
                            int idx = board[row][col] - '1';
                            if (seen[idx]) return false;
                            seen[idx] = true;
                        }
                    }
                }
            }
        }
        return true;
    }
}

Remarks:

1. TC: $O(81)=O(1)$, SC: $O(1)$
2. Be careful about converting from chat to int: num - '1' (actually should be 0 be we want to use index from 0)

Bit Manipulation

class Solution {
    public boolean isValidSudoku(char[][] board) {
        int[] rows = new int[9];
        int[] cols = new int[9];
        int[] boxes = new int[9];

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                if (c == '.') continue;

                int val = c - '1';
                int mask = 1 << val;
                int boxIdx = (i / 3) * 3 + (j / 3);

                // Check
                if ((rows[i] & mask) != 0 || (cols[j] & mask) != 0 || (boxes[boxIdx] & mask) != 0) {
                    return false;
                }

                // Set
                rows[i] |= mask;
                cols[j] |= mask;
                boxes[boxIdx] |= mask;
            }
        }

        return true;
    }
}

Remarks:

1. Use bit to record and check seen. val = 3 -> mask = 000001000 -> rows[i] & mask = 00000?000

2. rows[i] |= mask means rows[i] = rows[i] || mask. which helps to record seen.

3. more powerful for bigger sudokus (e.g. 16*16): boolean[16] takes 16 bytes, but int (32bit) only takes 4 bytes.

   Data Type	Size (Bytes)	Bits	Value Range (Decimal)	Default Value
   byte	1 byte	8	–128 to 127	0
   short	2 bytes	16	–32,768 to 32,767 ($-2^{15}$ to $2^{15} - 1$)	0
   int	4 bytes	32	–2,147,483,648 to 2,147,483,647 ($-2^{31}$ to $2^{31} - 1$)	0
   long	8 bytes	64	–9,223,372,036,854,775,808 to 9,223,372,036,854,775,807 ($-2^{63}$ to $2^{63} - 1$)	0L
   float	4 bytes	32	Approx. $±3.40282347×10^{38}$ (7 decimal digits precision)	0.0f
   double	8 bytes	64	Approx. $±1.79769313×10^{308}$ (15 decimal digits precision)	0.0d
   char	2 bytes	16	0 to 65,535 (Unicode characters)	'\u0000'
   boolean	JVM-dependent	N/A	true or false (internally often 1 byte or more)	false