Leetcode: Valid Sudoku

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

A partially filled sudoku which is valid.

Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

Understand the problem:
The problem asks for determining if a Sudoku is valid. Note that only the filled cells need to be validated. The rule of Sudoku is each row should only contains 1 - 9 of each number occurring only once, each column contains 1-9, and each 3 by 3 sub-matrix should contain 1 - 9.

Solution:
A straight-forward solution will be check each row, and then each column, and each block, respectively. Use hash set to store the visited numbers. In this method, we need to scan the matrix three times. Here we show a neat program which requires scanning the matrix only once. 

Code (Java):

public class Solution {
    public boolean isValidSudoku(char[][] board) {
        if (board == null || board.length != 9 || board[0].length != 9) {
            return false;
        }
        
        boolean[][] rows = new boolean[9][9];
        boolean[][] cols = new boolean[9][9];
        boolean[][] blocks = new boolean[9][9];
        
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    continue;
                }
                
                int c = board[i][j] - '1';
                
                if (rows[i][c] == true || cols[j][c] == true || blocks[(i / 3) * 3 + j / 3][c] == true) {
                    return false;
                }
                
                rows[i][c] = true;
                cols[j][c] = true;
                blocks[(i / 3) * 3 + j / 3][c] = true;
            }
        }
        return true;
    }
}

Summary:
It is a relatively easy question, the solution above is very tricky. Try to fully understand what does the rows, cols, and blocks mean. 


Update on 9/29/15:

public class Solution {
    public boolean isValidSudoku(char[][] board) {
        boolean[][] rows = new boolean[9][9];
        boolean[][] cols = new boolean[9][9];
        boolean[][] grid = new boolean[9][9];
        
        
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    continue;
                }
                
                int num = board[i][j] - '1';
                int x = 3 * (i / 3) + num / 3;
                int y = 3 * (j / 3) + num % 3;
                if (rows[i][num] || cols[num][j] || grid[x][y]) {
                    return false;
                }
                
                rows[i][num] = true;
                cols[num][j] = true;
                grid[x][y] = true;
            }
        }
        
        return true;
    }
}

Leetcode: Rotate Image

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up:
Could you do this in-place?

Understand the question:

The question asks for rotating an image by 90 degrees. The question has two requirements:

a. Rotate by 90 degrees in clockwise.

b. Transform in-place.

To understand the problem correctly, we can give several examples to illustrate the question.

For array [1], its transformed array is still 1

For array 1    2

                3   4 , 

the transformed array is     3     1  

                                              4      2

For array 1  2  3

                 4  5  6

                 7  8  9

the transformed array is  7  4  1

                                           8  5  2

                                           9  6  3

So it is not very difficult to see that the transformed array is actually putting first row of the original array into last column of the transformed array, and so on. 

Out-of-place Solution:

Out-of-place solution is very easy. Just crate a buffer to store the transformed array and copy back into the original array after the transformation. 

Code (Java):

public class Solution {
    public void rotate(int[][] matrix) {
        if (matrix == null || matrix.length == 0) return;
        // n * n matrix
        int n = matrix.length;
        
        // Temporary buffter to store rotated image
        int [][] temp = new int[n][n];
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                temp[j][n - i - 1] = matrix[i][j];
            }
        }
        
        // copy back the results
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = temp[i][j];
            }
        }
    }
}

In-place Solution:
An in-place method is to first transpose the array, then swap the elements in each row.
For example, for array
 1  2  3
 4  5  6
 7  8  9
The transposed array is:
1  4  7
2  5  8
3  6  9
Then swap elements in each row
7  4  1
8  5  2
9  6  3

Code (Java):

public class Solution {
    public void rotate(int[][] matrix) {
        if (matrix == null || matrix.length < 2) return;
        
        // length of the matrix
        int n = matrix.length;
        
        // transpose the matrix
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = tmp;
            }
        }
        
        // swap elements for each row
        int mid = n / 2;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < mid; j++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[i][n - j - 1];
                matrix[i][n - j - 1] = tmp;
            }
        }
    }
}

Discussion:
The time complexity is O(n^2), which is the best we can do for this algorithm. The space complexity is O(1). Note the matrix transpose algorithm, the inner loop index j starting from i + 1. That is because we have already swapped the element before i. If j starts from 0, it will swap the elements back again.

Another in-place solution:
Check cc150 1.6

Code (Java):

public class Solution {
    public void rotate(int[][] matrix) {
        // check if matrix is null or empty or length equals to 1
        if (matrix == null || matrix.length < 2) return;
        
        int n = matrix.length;
        
        for (int layer = 0; layer < n/2; layer++) {
            int first = layer;
            int last = n - layer - 1;
            
            for (int i = first; i < last; i++) {
                int offset = i - first;
                int top = matrix[first][i];
                
                // left -> top
                matrix[first][i] = matrix[last - offset][first];
                
                // bottom -> left
                matrix[last - offset][first] = matrix[last][last - offset];
                
                // right -> bottom
                matrix[last][last - offset] = matrix[i][last];
                
                // top - > right;
                matrix[i][last] = top;
            }
        }
    }
} 

Summary:
In this post, we learned how to rotate an array in place. The third method is very tricky. Make sure to understand the details, especially for how to calculate the indices. 

Leetcode: Spiral Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

You should return [1,2,3,6,9,8,7,4,5].

Analysis:
The problem asks for returning all elements of the matrix in spiral order. So the key of the question is to understand what is the spiral order. We may use several examples to illustrate that. 

For empty array, we return empty as well.
For array [ 1,  2], the spiral order is 1, 2
For array [1]
                 [2], the spiral order still 1 and 2
For array 1,   2,   3
                 4,   5,   6
                 7,   8 ,  9 , the spiral order is 1, 2, 3, 6, 9, 8, 7, 4, 5

For array  1,   2,   3
                  4,   5,   6
                  7,   8,   9
                  10, 11, 12, the spiral order is 1, 2, 3, 6, 9, 12, 11, 10, 7, 4, 5, 8

From the above examples, we could see that the traverse order is to scan the out-most elements, then inner, and inner until we go through all the elements in the matrix.

Solution:

Code (Java):

public class Solution {
    public ArrayList<Integer> spiralOrder(int[][] matrix) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        
        // if matrix is null or empty
        if (matrix == null || matrix.length == 0) return result;
        
        int m = matrix.length;
        int n = matrix[0].length;
        
        int row = 0;
        int col = 0;
        
        
        // Handle the circle
        while (m > 0 & n > 0) {
            // For matrix has only 1 row
            if (m == 1) {
                for (int i = 0; i < n; i++) {
                    result.add(matrix[row][col++]);
                }
                break;
            } else if (n == 1) {
                for (int i = 0; i < m; i++) {
                    result.add(matrix[row++][col]);
                }
                break;
            }
            
            // move right
            for (int i = 0; i < n - 1; i++) {
                result.add(matrix[row][col++]);
            }
            
            // move down
            for (int i = 0; i < m - 1; i++) {
                result.add(matrix[row++][col]);
            }
            
            // move left
            for (int i = 0; i < n - 1; i++) {
                result.add(matrix[row][col--]);
            }
            
            // move up
            for (int i = 0; i < m - 1; i++) {
                result.add(matrix[row--][col]);
            }
            
            // move to the inner circle
            row++;
            col++;
            m -= 2;
            n -= 2;
        }
        
        return result;
    }
}

Discussion:
Note that in the while loop we must first handle if the matrix has only one row or column left. Why was that? That is because otherwise we will generate repeated numbers. For instance, for the matrix 1, 2, 3. If we don't copy the  1, 2, 3 out and stop, we will output 1, 2, 3, 2, 1. 
The time complexity of this solution is O(m * n) which is linear to the size of matrix.

Summary:
The problem itself is not hard to understand. But the implementation is very tricky. Make sure you understand the ideas of the implementation of the this question. 

Leetcode: Set Matrix Zeros

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
Follow up:

Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

Understand the problem:
The problem looks quite simple at the first glance. It just needs to traverse the matrix, when we see a zero, we set the entire row and column zero. However, the problem is if we set the entire row and column zero, when we meet the zero later, we will set other rows and columns as other. And we could imagine that all matrix elements will become zero in short.
How can we get rid of this problem?

Naive Solution:
A native solution is to allocate another matrix, when we meet a zero element, we mark the entire row and column zero in the new array. However, it will take O(mn) space.

A Better Solution:
Do we really need an entire array to store the zero elements? Not really. We only need to know row i is zeros and column j is zeros, etc.. Therefore, instead of allocating an  m * n array, we only need to allocate two arrays, one with size m to store the row zero information, i.e, indicate which row is zero, the other with size n to indicate which column is zero. At last, we only need to copy those zeros into the original array. It is obviously to see that the space complexity now becomes O(m + n).

Code (Java):

public class Solution {
    public void setZeroes(int[][] matrix) {
        if (matrix == null || matrix.length == 0) return;
        
        // get rows and columns of the matrix
        int m = matrix.length;
        int n = matrix[0].length;
        
        // allocate two addtional space to store zeros
        boolean[] row = new boolean[m];
        boolean[] col = new boolean[n];
        
        // iterate the matrix and set the zero flags
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    row[i] = true;
                    col[j] = true;
                }
            }
        }
        
        // set the corresponding row and columns of the original matrix as zeros
        for (int i = 0; i < m; i++) {
            if (row[i] == true) {
                for (int j = 0; j < n; j++) {
                    matrix[i][j] = 0;
                }
            }
        }
        for (int j = 0; j < n; j++) {
            if (col[j] == true) {
                for (int i = 0; i < m; i++) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}

Constant Space Solution:
Since the problem asks for a constant space solution, we must think of one without allocating additional space. Remember in last solution, we used additional row and column to store the zero information. How about we use the first column and row to save the zero information? It sounds doable. But what about the first or column contains zeros thus needs to be set as zeros as well? We could work around by using a flag to mark the first row or column as zeros. Consequently, the solution can be devised into following steps:
1. Check the first column and row contains zeros, if yes, mark the flag as true to indicate first row and column need to set to zeros.
2. Starting from matrix[1][1], check if each element  is zero, if yes, mark the corresponding first row and column elements as zeros.
3. Check back the first column and row, and set the corresponding elements in the matrix as zero.
4. Check the first row and column zero flag, if needed, set the first row and column zeros.


Code (Java):

public class Solution {
    public void setZeroes(int[][] matrix) {
        if (matrix == null || matrix.length == 0) return;
        
        int m = matrix.length;
        int n = matrix[0].length;
        
        boolean firstRowZero = false;
        boolean firstColZero = false;
        
        // check if the first row contains zero
        for (int i = 0; i < n; i++) {
            if (matrix[0][i] == 0) {
                firstRowZero = true;
            }
        }
        
        // check if the first col contains zero
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                firstColZero = true;
            }
        }
        
        // check the rest of the matrix elements
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }
        
        // set the corresponding row and col as zero
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        
        // check and set the first row and col as zeros, if necessary
        if (firstRowZero) {
            for (int i = 0; i < n; i++) {
                matrix[0][i] = 0;
            }
        }
        
        if (firstColZero) {
            for (int j = 0; j < m; j++) {
                matrix[j][0] = 0;
            }
        }
        
    }
}

Discussion:
In this solution, since we only used two additional flag to mark the first row and column as zeros, the space complexity is constant. 

Summary:
In this post, we learned how to set zeros in a 2D matrix. Be careful about the pitfall of the problem. You cannot just set zeros in place else all matrix will become zeros eventually. We introduced three methods to reduce space cost. The third method is tricky, which used the first row and col as marker. Make sure you understand the details and try not to just memorize the solution.