Valid Sudoku Cont…

Question: 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 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

You may view the full question here.

Approach 2: Now that we have tried a naive approach in the previous post, let’s now try one where we iterate through and check the element at each position only once. NOTE: we are not essentially reducing the number of checks. Instead of checking the element in three different for loops(one loop for each condition), we checking all three conditions in a single iteration/for loop. This necessarily should preserve the runtime. The space complexity is questionable though. The code looks like —

//Approach 2:
//Runtime: 3ms (Same as last time)
//Memory usage: 45.3MB (Same as last time)
class Solution {
    public boolean isValidSudoku(char[][] board) {
        
        HashMap<Character, Integer>[] rowMaps = new HashMap[9];
        HashMap<Character, Integer>[] colMaps = new HashMap[9];
        HashMap<Character, Integer>[] subMaps = new HashMap[9];
        for(int c = 0; c<9; c++){
            for(int r = 0; r<9; r++){
                char curr = board[r][c];
                if(curr!='.'){
                    int sub = getSubsetIndex(r, c);
                    if(rowMaps[r]==null){
                        rowMaps[r] = new HashMap();
                    }
                    if(colMaps[c]==null){
                        colMaps[c] = new HashMap();
                    }
                    if(subMaps[sub]==null){
                        subMaps[sub] = new HashMap();
                    }
                    if(rowMaps[r].containsKey(curr) || colMaps[c].containsKey(curr) || subMaps[sub].containsKey(curr)){
                        return false;
                    }
                    rowMaps[r].put(curr, 1);
                    colMaps[c].put(curr, 1);
                    subMaps[sub].put(curr, 1);   
                }                
            }
        }
       return true;
    }
    
    private int getSubsetIndex(int row, int col){
        switch(row){
            case 0:
            case 1:
            case 2:
                return 0 + getCol(col);
            case 3:
            case 4:
            case 5:
                return 3 + getCol(col);
            case 6:
            case 7:
            case 8:
            default:
                return 6 + getCol(col);
        }
    }
    
    private int getCol(int col){
        switch(col){
            case 0:
            case 1:
            case 2:
                return 0;
            case 3:
            case 4:
            case 5:
                return 1;
            case 6:
            case 7:
            case 8:
            default:
                return 2;
        }
    }
}

Find more posts here.

Cheers & Chao!