Leetcode (python): 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.

Solution:

class Solution:
    # @param board, a 9x9 2D array
    # @return a boolean
    def isValidSudoku(self, board):
        
        for i in range(0,9):
            row = []
            col = []
            square = []
            for j in range(0,9):
                row.append(False)
                col.append(False)
                square.append(False)
            for j  in range(0,9):
                if board[i][j] != '.':
                    if board[i][j].isdigit() and int(board[i][j])>0 and int(board[i][j])<=9 and not row[int(board[i][j])-1]:
                        row[int(board[i][j])-1] = True
                    else:
                        return False
                if board[j][i] != '.':
                    if board[j][i].isdigit() and int(board[j][i])>0 and int(board[j][i])<=9 and not col[int(board[j][i])-1]:
                        col[int(board[j][i])-1] = True
                    else:
                        return False
                rowSquare = int(i / 3)*3 + int(j / 3);
                colSquare = (i % 3)*3 + j % 3;
                if board[rowSquare][colSquare] != '.':
                    if board[rowSquare][colSquare].isdigit() and int(board[rowSquare][colSquare])>0 and int(board[rowSquare][colSquare])<=9 and not square[int(board[rowSquare][colSquare])-1]:
                        square[int(board[rowSquare][colSquare])-1] = True
                    else:
                        return False
        return True

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.

Solution:

public class Solution {
    public boolean isValidSudoku(char[][] board) {
        
        for(int i=0; i<9; i++)
        {
            boolean[] row = new boolean[9];
            boolean[] col = new boolean[9];
            boolean[] square = new boolean[9];
            for(int j=0; j<9; j++)
            {
                if(board[i][j] != '.')    
                {
                    if(Character.isDigit(board[i][j]) && !row[board[i][j]-'1']  )
                        row[board[i][j]-'1'] = true;
                    else 
                        return false;
                }
                
                if(board[j][i] != '.')    
                {
                    if(Character.isDigit(board[j][i]) && !col[board[j][i]-'1']  )
                        col[board[j][i]-'1'] = true;
                    else 
                        return false;
                }
                int colS = (i%3)*3+ j%3;
                int rowS = (i/3)*3 + j/3;
                if(board[rowS][colS] != '.')    
                {
                    if(Character.isDigit(board[rowS][colS]) && !square[board[rowS][colS]-'1'] )
                        square[board[rowS][colS]-'1'] = true;
                    else 
                        return false;
                }
            }
        }
        return true;
    }
}

LeetCode (Python): Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Solution:

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param root, a tree node
    # @return an integer
    def minDepth(self, root):
        if root == None:
            return 0
        if root.left == None:
            return self.minDepth(root.right) + 1
        if root.right == None:
            return self.minDepth(root.left) + 1
        return min(self.minDepth(root.left),self.minDepth(root.right))+1

Leetcode: Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Solution:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 
public class Solution {
    public int minDepth(TreeNode root) {
        if(root==null)
            return 0;
        if (root.right == null)
            return minDepth(root.left) + 1;
        if (root.left == null)
            return minDepth(root.right) + 1;
        return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
    }
}

Leetcode (Python): Unique Binary Search Trees

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,
Given n = 3, there are a total of 5 unique BST's.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Solution:

class Solution:
    # @return an integer
    def numTrees(self, n):
        return self.numTrees2(1, n)
        
    def numTrees2(self, minV, maxV):
        if minV >= maxV:
            return 1
        val = 0
        for i in range(minV,maxV+1):
            val = val + self.numTrees2(minV, i-1)*self.numTrees2(i+1, maxV)
        return val

Leetcode: Unique Binary Search Trees

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,
Given n = 3, there are a total of 5 unique BST's.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Solution:

public class Solution {
    public int numTrees(int n) 
    {
        return numTrees(1, n);
    }
    
    public int numTrees(int min, int max) 
    {
        if(min>=max)
            return 1;
        int val = 0;
        for (int i=min; i<=max; i++)
        {
            val += numTrees(min, i-1) *numTrees(i+1, max);
        }
        return val;
    }
}

Leetcode (Python): Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

Solution

If we traverse the tree inorder, we just need to identify the 2 elements that are misplaced and swap their values. We also keep a third pointer that points to the previous element as it is needed to identify when an element is misplaced.

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param root, a tree node
    # @return a tree node
    
    def recoverTree(self, root):
        self.pre = None
        self.node1 = None
        self.node2 = None
        self.inOrder(root)
        val = self.node1.val
        self.node1.val = self.node2.val
        self.node2.val = val
        return root
        
    def inOrder(self, root):
        if root == None:
            return
        self.inOrder(root.left)
        if self.pre == None:
            self.pre = root
        if self.node1 == None and self.pre.val > root.val:
            self.node1 = self.pre
            self.node2 = root
        elif self.pre.val > root.val:
            self.node2 = root
        self.pre = root;
        self.inOrder(root.right)
        return