Solution by Mixacb


  • 0
    M

    Approach #1 Search repeating element [Accepted]

    Intuition

    Check Sudoku in accordance with the rules, that is looking for a number that was repeated in a row or column, or the current block. At least one such coincidence makes the Sudoku is invalid. If there are no such coincidence, Sudoku is valid.

    Algorithm

    1. Create three two-dimensional arrays in order to consider the presence of the element in the row, column, and block. Nine rows for each array will specify block numbers, rows and columns of the board (hereinafter, for simplicity, we call them subarrays). In each row of the subarray is 9 places for each number.

    To know the row number and column number in which there the element is not difficulties. With the numbering of the blocks can be understand as follows. All the indexes of the row and column board we need to represent [0, 1, 2] thus, scaling the coordinates to the block level. For this operation we need to divide the index by 3 and round it down( the coordinates of the blocks - blue and yellow numbers on the picture). Next to the numbering of the specific block by its coordinates multiplied by the new index of "row of the blocks" on the number of units in it (3), as the index of "row" shows how many "rows" already. Thus obtaining the number of blocks added to it a column coordinate, thereby obtaining the index of a particular unit (green numbers on the picture).
    Numbering of blocks

    1. Pass the loop through the board, element by element, skipping empty values.

    2. If you find the number, check whether it is met in the current block, row or column.

    3. If there is not such number, occupied the position in the corresponding row, column, and block.

    4. If the position number is already occupied, return false.

    5. If we complete this cycle, the return value is true.

    JavaScript

    var isValidSudoku = function(board) {
        this.rows=[];
            for(let j=0;j<9;j++){
                this.rows[j]=[];
            }
    
       this.columns=[];
        for(let j=0;j<9;j++){
                this.columns[j]=[];
            }
    
        this.blocks=[];
        for(let j=0;j<9;j++){
                this.blocks[j]=[];
            }
    
        for(let i=0;i<9;i++){
            for(let j=0;j<9;j++){
                if(board[i][j]!=="."){
                var element_index=Number(board[i][j])-1;
                var block_index=3*Math.floor(i/3)+Math.floor(j/3);
    if(!(this.rows[i][element_index])&&!(this.columns[j][element_index])&&!(this.blocks[block_index][element_index]))
                            {
                               this.rows[i][element_index]=1;
                               this.columns[j][element_index]=1;
                               this.blocks[block_index][element_index]=1;
                            }
                        else{
                            return false;
                        }
                    }
            }
        }
        return true;
    };
    
    

    Complexity Analysis

    • Time complexity : $$O(1)$$. The size of the input is fixed, so there is no value of n.
    • Space complexity : $$O(m*n^2)$$. We need space for m=3 massive with n=9 rows and n=9 columns. Since m and n constants, $$O(1)$$.

    Approach #2 Search repeating element using bitwise operations [Accepted]

    Intuition

    The same, only instead of two-dimensional arrays to store element values in a specific row, column and block will use one-dimensional arrays storing for each subarray digit in the binary representation, where a 1 in the corresponding position indicates the presence of the element. For example, 010 000 001 0 indicates the presence of 1 and 8 in the subarray.

    Algorithm

    1. Create a three arrays in order to consider the presence of the element in the subarrays.

    2. Pass the loop through the board, element by element, skipping empty values.

    3. If you find the number, check whether it is employed for the current subarrays. To do this, perform a bitwise shift operation to the right by the amount equal to the found number and compare the bitwise operation “and” with 1. If the number is already in the subarray this operation will return true and in this case, the Sudoku is invalid, the return false.

    4. If the numbers in the subarray are not occupied his position, adding in the appropriate category 1 shifting to the left by the amount equal to the found number using "or" operation .

    5. If we complete this cycle, return true.

    JavaScript

    var isValidSudoku = function(board) {
        this.rows=[];
        this.columns=[];
        this.blocks=[];
    
        for(let i=0;i<9;i++){
            for(let j=0;j<9;j++){
                if(board[i][j]!=="."){
                var element=Number(board[i][j]);
                var block_index=3*Math.floor(i/3)+Math.floor(j/3);
    if(this.rows[i]>>element & 1||this.columns[j]>>element & 1||this.blocks[block_index]>>element & 1){
     return false;
    }
                    else{
                               this.rows[i]|=1<<element;
                               this.columns[j]|=1<<element;
                               this.blocks[block_index]|=1<<element;
                    }
    
                }
            }
        }
        return true;
    };
    
    

    Complexity Analysis

    • Time complexity : The same as previous.
    • Space complexity : $$O(m*n)$$. We need space for m=3 massive with n=9 cells. Since m and n constants, $$O(1)$$.
      [0_1508531065616_Solution by Mixacb](Uploading 100%)

Log in to reply
 

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