Concise Java using Boolean Array to Optimize Hashing


  • 0
    H

    public class Solution {
        public boolean isValidSudoku(char[][] board) {
    	boolean[][] hashR = new boolean[10][10];
    	boolean[][] hashS = new boolean[10][10];
    	for(int j=0; j<9; j++) {
    		boolean[] hashC = new boolean[10];
    		for(int i=0; i<9; i++){
    			if(board[i][j] == '.') {
                                    continue;
                            }
                            int curr = board[i][j]-'0';
                            int sq = (i/3)*3 + (j/3);
    			if(hashC[curr] || hashR[i][curr] || hashS[sq][curr]){
    				return false;
    			} else {
    				hashC[curr] = true;
                                    hashR[i][curr] = true;
                                    hashS[sq][curr] = true;
    			}
    		}
    	}
    	return true;
        }		
    }
    

    Explanation


    i: rows
    j: columns
    s: squares

    row 0: (i/3)*3 = 0 row 1: (i/3)*3 =1 row 2: (i/3)*3 = 2
    col 0: j/3= 0 sq 0 sq 1 sq 2
    col 1: j/3= 1 sq 3 sq 4 sq 5
    col 2: j/3= 2 sq 6 sq 7 sq 8

    as you can see, this gets the following (C1 and C2 are constants we wish to find (remember int division takes off decimal)):

    C1 × (col/3) + C2 × (row/3)*3 = sq

    C1 × 0 + C2 × 0 = 0

    C1 × 0 + C2 × 1 = 1

    C1 × 0 + C2 × 2 = 2

    C1 × 1 + C2 × 0 = 3

    C1 × 1 + C2 × 1 = 4

    C1 × 1 + C2 × 2 = 5

    C1 × 2 + C2 × 0 = 6

    C1 × 2 + C2 × 1 = 7

    C1 × 2 + C2 × 2 = 8

    therefore, C1 = 3 and C2 = 1 giving you all the information you need to make your code concise: 3×i+j = sq

    From here it is simply making binary arrays for each rule (sq, row, col) to check that true never happens twice.
    Optimize for space with doing the row hash in real time and optimize for time here and there with '.' logic and immediate returns.


Log in to reply
 

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