Shared my concise Java code


  • 216
    L
    public boolean isValidSudoku(char[][] board) {
        for(int i = 0; i<9; i++){
            HashSet<Character> rows = new HashSet<Character>();
            HashSet<Character> columns = new HashSet<Character>();
            HashSet<Character> cube = new HashSet<Character>();
            for (int j = 0; j < 9;j++){
                if(board[i][j]!='.' && !rows.add(board[i][j]))
                    return false;
                if(board[j][i]!='.' && !columns.add(board[j][i]))
                    return false;
                int RowIndex = 3*(i/3);
                int ColIndex = 3*(i%3);
                if(board[RowIndex + j/3][ColIndex + j%3]!='.' && !cube.add(board[RowIndex + j/3][ColIndex + j%3]))
                    return false;
            }
        }
        return true;
    }

  • 0
    Z
    This post is deleted!

  • 6
    T

    Nice! I was trying to do something very similar but I was getting stuck on checking cubes. I like the idea of using / and % .


  • 0
    J

    Very neat and easy to understand!


  • 229

    Great solution!. Just trying to explain how to think about % and /. These two operators can be helpful for matrix traversal problems.

    For a block traversal, it goes the following way.

    0,0, 0,1, 0,2; < --- 3 Horizontal Steps followed by 1 Vertical step to next level.

    1,0, 1,1, 1,2; < --- 3 Horizontal Steps followed by 1 Vertical step to next level.

    2,0, 2,1, 2,2; < --- 3 Horizontal Steps.

    And so on...
    But, the j iterates from 0 to 9.

    But we need to stop after 3 horizontal steps, and go down 1 step vertical.

    Use % for horizontal traversal. Because % increments by 1 for each j : 0%3 = 0 , 1%3 = 1, 2%3 = 2, and resets back. So this covers horizontal traversal for each block by 3 steps.

    Use / for vertical traversal. Because / increments by 1 after every 3 j: 0/3 = 0; 1/3 = 0; 2/3 =0; 3/3 = 1.

    So far, for a given block, you can traverse the whole block using just j.

    But because j is just 0 to 9, it will stay only first block. But to increment block, use i. To move horizontally to next block, use % again : ColIndex = 3 * i%3 (Multiply by 3 so that the next block is after 3 columns. Ie 0,0 is start of first block, second block is 0,3 (not 0,1);

    Similarly, to move to next block vertically, use / and multiply by 3 as explained above. Hope this helps.


  • 1
    G

    very precise,very simple solution。,thks


  • 0
    L

    Great explain! Thank you!


  • 0
    J

    the idea is so great


  • 0

    Very concise and nice code!! Much better than mine. Mine has too much redundant codes.... Learn a lot.


  • 0
    K

    @jaqenhgar thank you! it's very helpful!


  • 1
    N

    @jaqenhgar said in Shared my concise Java code:

    Great solution!. Just trying to explain how to think about % and /. These two operators can be helpful for matrix traversal problems.

    For a block traversal, it goes the following way.

    0,0, 0,1, 0,2; < --- 3 Horizontal Steps followed by 1 Vertical step to next level.

    1,0, 1,1, 1,2; < --- 3 Horizontal Steps followed by 1 Vertical step to next level.

    2,0, 2,1, 2,2; < --- 3 Horizontal Steps.

    And so on...
    But, the j iterates from 0 to 9.

    But we need to stop after 3 horizontal steps, and go down 1 step vertical.

    Use % for horizontal traversal. Because % increments by 1 for each j : 0%3 = 0 , 1%3 = 1, 2%3 = 2, and resets back. So this covers horizontal traversal for each block by 3 steps.

    Use / for vertical traversal. Because / increments by 1 after every 3 j: 0/3 = 0; 1/3 = 0; 2/3 =0; 3/3 = 1.

    So far, for a given block, you can traverse the whole block using just j.

    But because j is just 0 to 9, it will stay only first block. But to increment block, use i. To move horizontally to next block, use % again : ColIndex = 3 * i%3 (Multiply by 3 so that the next block is after 3 columns. Ie 0,0 is start of first block, second block is 0,3 (not 0,1);

    Similarly, to move to next block vertically, use / and multiply by 3 as explained above. Hope this helps.


  • 2
    P

    @jaqenhgar Great explanation. However, we can interchangeably use / and % for either vertical or horizontal traversal. Correct me if I am wrong.


  • 0
    C
    when i = 7; 
        then rowIndex = 7 and colIndex = 3; 
        if j = 6; 
           then rowIndex + j / 3 = 9 
    

    The array has overflow.


  • 0

    @ParinSanghavi You're right. Just traverse the matrix and cube in different manner.

    1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 ->9
    VS
    1 -> 4 -> 7 -> 2 -> 5 -> 8 -> 3 -> 6 -> 9


  • 0
    G

    What if the board is not cubic, for this problem the number of the cubes happens to equal 9.
    But what if we had a 9 * 12 board, then i is from 0 to 9, j is from 0 to 12; and what about the RowIndex and ColIndex now?


  • 3
    M

    A little bit more concise.

        for(int i = 0; i<9; i++) {
            HashSet<Character> rows = new HashSet<>();
            HashSet<Character> cols = new HashSet<>();
            HashSet<Character> cube = new HashSet<>();
            for (int j = 0; j < 9;j++) {
                if(board[i][j]!='.' && !rows.add(board[i][j]))
                    return false;
                if(board[j][i]!='.' && !cols.add(board[j][i]))
                    return false;
                int cubeRow = 3*(i/3) + j/3;
                int cubeCol = 3*(i%3) + j%3;
                if(board[cubeRow][cubeCol]!='.' && !cube.add(board[cubeRow][cubeCol]))
                    return false;
            }
        }
        return true;
    

    For the cubeRow or cubeCol, int cubeRow = 3*(i%3) + j%3, cubeCol = 3*(i/3) + j/3 also works. Because it doesn't matter whether we check the cubes vertically or horizontally.


  • 1

    @Lorraine921 why dont we required arrays of sets ?


  • 0

    Here's a mildly refactored version of you solution:

        public boolean isValidSudoku(char[][] board) {
            for(int i = 0; i < 9; i++) {
                Set<Character> rows = new HashSet<>();
                Set<Character> cols = new HashSet<>();
                Set<Character> cubes = new HashSet<>();            
                for (int j = 0; j < 9; j++) {
                    if (board[i][j] != '.' && !rows.add(board[i][j])) return false;
                    if (board[j][i] != '.' && !cols.add(board[j][i])) return false;
                    int colOffset = j % 3, rowOffset = j / 3;
                    int colStart = 3 * (i % 3), rowStart = 3 * (i / 3);
                    int row = rowStart + rowOffset, col = colStart + colOffset;
                    if (board[row][col] != '.' && !cubes.add(board[row][col]) )return false;
                }
            }
            return true;
        }
    

  • 0
    A

    @Chalin-Shi I am wondering the same.


  • 0
    H

    I think time complexity is O(n^2)?


Log in to reply
 

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