O(n^2) Java solution with bitmasks


  • 0
    B

    I thought i'd share my new solution in Java. There are other solutions using bitmasks but mine is different in the way I handle the 3x3 squares. Basically, I refer to each square by its bottom-right limit that I update on each pass with simple additions.

    Comments welcome.

    public class Solution {
    
        private static final int SIZE = 9;
        private static final int SQR_SIZE = 3;
    
        public boolean isValidSudoku(char[][] board) {
            
            int sqrRow = SQR_SIZE;
            int sqrCol = SQR_SIZE;
            
            // Checks for duplicate values in each row, column and square.
            for (int i = 0; i < SIZE; ++i) {
                
                // Check row
                int bitmask = 0;
                for (int j = 0; j < SIZE; ++j) {
                    char cell = board[i][j];
                    if (cell == '.')
                        continue;
                    int cellBitmask = 1 << (cell - '1');
                    if ((cellBitmask & bitmask) != 0)
                        return false;
                    bitmask |= cellBitmask;
                }
                
                // Check column
                bitmask = 0;
                for (int j = 0; j < SIZE; ++j) {
                    char cell = board[j][i];
                    if (cell == '.')
                        continue;
                    int cellBitmask = 1 << (cell - '1');
                    if ((cellBitmask & bitmask) != 0)
                        return false;
                    bitmask |= cellBitmask;
                }
                
                // Check square
                bitmask = 0;
                for (int row = sqrRow - SQR_SIZE; row < sqrRow; ++row)
                    for (int col = sqrCol - SQR_SIZE; col < sqrCol; ++col) {
                        char cell = board[row][col];
                        if (cell == '.')
                            continue;
                        int cellBitmask = 1 << (cell - '1');
                        if ((cellBitmask & bitmask) != 0)
                            return false;
                        bitmask |= cellBitmask;
                    }
                
                // Select next square (faster than division or modulo)
                if (sqrCol == SIZE) {
                    sqrRow += SQR_SIZE;
                    sqrCol  = SQR_SIZE;
                } else
                    sqrCol += SQR_SIZE;
                
            }
            return true;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.