Leetcode (Python): Unique Binary Search Trees II

Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.

For example,
Given n = 3, your program should return all 5 unique BST's shown below.

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

Solution:

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

class Solution:
    # @return a list of tree node
    def generateTrees(self, n):
        return self.generateTrees2(1,n)
    
    def generateTrees2(self, begin, end):
        solution = []
        if begin > end:
            solution.append(None)
            return solution
        for root in range(begin,end+1):
            leftNodes = self.generateTrees2(begin, root-1)
            rightNodes = self.generateTrees2(root+1, end)
            for leftNode in leftNodes:
                for rightNode in rightNodes:
                    node = TreeNode(root)
                    node.left = leftNode
                    node.right = rightNode
                    solution.append(node)
        return solution

Leetcode (Python): Combination Sum II

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
• The solution set must not contain duplicate combinations.

For example, given candidate set 10,1,2,7,6,1,5 and target 8, 
A solution set is: 
[1, 7] 
[1, 2, 5] 
[2, 6] 
[1, 1, 6] 

Solution

class Solution:
    # @param candidates, a list of integers
    # @param target, integer
    # @return a list of lists of integers
    def combinationSum2(self, candidates, target):
        candidates.sort()
        solution =[]
        self.combinationSum2Rec(candidates, target, 0, 0, [], solution)
        return solution
    
    def combinationSum2Rec(self, candidates, target, index, sum, tempList, solution):
        if sum == target:
            solution.append(list(tempList))
            return
        for i in range(index, len(candidates)):
            if (i==index or candidates[i-1]!=candidates[i]) and sum+candidates[i]<=target:
                tempList.append(candidates[i])
                self.combinationSum2Rec(candidates, target, i+1, sum+candidates[i], tempList, solution) 
                tempList.pop()

Leetcode (Python): Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3. 

Solution:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param head, a ListNode
    # @return a ListNode
    def deleteDuplicates(self, head):
        pointer = head;
        while pointer != None and pointer.next !=None:
            if pointer.val == pointer.next.val:
                pointer.next = pointer.next.next
            else:
                pointer = pointer.next
        return head

Leetcode (Python): Distinct Subsequences

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Here is an example:
S = "rabbbit", T = "rabbit"

Return 3.

Solution:

class Solution:
    # @return an integer
    def numDistinct(self, S, T):
        numberOfSubsequences = [1]
        positions ={}
        for i in range (len(T)-1,-1,-1):
            numberOfSubsequences.append(0)
            if not T[i] in positions:
                positions[T[i]]=[]
            positions[T[i]].append(i)
        for i in range(0,len(S)):
            if S[i] in positions:
                for j in positions[S[i]]:
                    numberOfSubsequences[j+1]+=numberOfSubsequences[j]
        return numberOfSubsequences[len(T)]

Leetcode (Python): Divide Two Integers

Divide two integers without using multiplication, division and mod operator.

Solution:

The result can be seen as $a_n 2^n+ a_{n-1} 2^{n-1}+\dots+a_1 *2 +a_0$, with $a_i \in \{0,1\}$. Our solution calculates first n by obtaining the largest n that $\text{divisor} \cdot 2^n \leq \text{dividend}$. Then we just have to calculate $a_i = \left( \text{dividend} - \sum_{j=i+1}^n a_j \text{divisor} \cdot 2^j\right)>= 2^i$, even the expression is complex the code is much simpler:

class Solution:
    # @return an integer
    def divide(self, dividend, divisor):
        isNegative = (dividend<0) ^ (divisor<0)
        dividend = abs(dividend)
        divisor = abs(divisor)
        count = 1
        while dividend >= (divisor<<1):
            divisor <<= 1
            count <<=1
        result = 0
        while dividend > 0 and divisor>=1:
            if dividend>=divisor:
                dividend -= divisor
                result += count
            divisor >>= 1
            count >>=1
        if isNegative:
            return -result
        else:
            return result

Leetcode(Path): Unique paths

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

Solution:

In order to obtain O(n) we just keep the last row and the actual one

class Solution:
    # @return an integer
    def uniquePaths(self, m, n):
        for row in range(0,m):
            actualRow = []
            for col in range(0,n):
                if row ==0 and col==0:
                    actual = 1
                else:
                    actual = 0;
                if row>0:
                    actual += previousRow[col]
                if col>0:
                    actual += actualRow[col-1]
                actualRow.append(actual)
            previousRow= actualRow
        return actualRow[n-1]

Leetcode (Python): Search for a Range

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

Solution

class Solution:
    # @param A, a list of integers
    # @param target, an integer to be searched
    # @return a list of length 2, [index1, index2]
    def searchRange(self, A, target):
        solution =[-1,-1];
        start = 0
        end = len(A)-1
        while start<end:
            midpoint = (start + end )/2
            if A[midpoint] == target:
                end = midpoint
            elif A[midpoint] < target:
                start = midpoint+1
            else:
                end = midpoint -1
        if A[start]!= target:
            return solution
        solution[0] = start
        end = len(A)-1
        while start<end:
            midpoint = (start + end +1)/2
            if A[midpoint] == target:
                start = midpoint
            else:
                end = midpoint -1
        solution[1] = start
        return solution

Leetcode (Python): Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Solution:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param two ListNodes
    # @return a ListNode
    def mergeTwoLists(self, l1, l2):
        dummy = ListNode(0)
        pointer = dummy
        while l1 !=None and l2 !=None:
            if l1.val<l2.val:
                pointer.next = l1
                l1 = l1.next
            else:
                pointer.next = l2
                l2 = l2.next
            pointer = pointer.next
        if l1 == None:
            pointer.next = l2
        else:
            pointer.next = l1
        return dummy.next

Leetcode: Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Solution:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode pointer = dummy;
        ListNode pointerL1 = l1;
        ListNode pointerL2 = l2;
        while(l1!=null && l2 !=null)
        {
            if(l1.val < l2.val)
            {
                pointer.next= l1;
                l1 = l1.next;
            }
            else
            {
                pointer.next= l2;
                l2 = l2.next;
            }
            pointer = pointer.next;
        }
        if (l1 == null)
            pointer.next = l2;
        else
            pointer.next =l1;
        return dummy.next;
    }
}

Sink Zeros in Binary Tree

 Swap zero value of a node with non-zero value of one of its descendants so that no node with value zero could be parent of node with non-zero.

Solution: 

We use a postorder traversal of the tree where instead of sinking we rise the leafs, we keep the nodes that we are sure that have not a zero ancestor.

public  void sink0(TreeNode root)
 {
  HashSet<TreeNode> finished = new HashSet<TreeNode>();
  sink0(root, new HashMap<TreeNode,TreeNode>(), finished, false);
 }
 
 public void sink0(TreeNode root, HashMap<TreeNode, TreeNode> parentMap, HashSet<TreeNode> finished, boolean zerosOver)
 {
  if(root.val==0)
   zerosOver = true;
  if(!zerosOver)
   finished.add(root);
  
  if(root.left != null)
  {
   parentMap.put(root.left, root);
   sink0(root.left, parentMap, finished, zerosOver);
  }
  if(root.right != null)
  {
   parentMap.put(root.right, root);
   sink0(root.right, parentMap, finished, zerosOver);
  }
  if(root.val!=0 && !finished.contains(root))
  {
   TreeNode temp = root;
   ArrayDeque<TreeNode> nonZeroNodes = new ArrayDeque<TreeNode>();
   ArrayDeque<TreeNode>nodes = new ArrayDeque<TreeNode>();
   while(temp!=null && !finished.contains(temp))
   {
    nodes.push(temp);
    if(temp.val!=0)
     nonZeroNodes.push(temp);
    temp = parentMap.get(temp);
   }
   
   while(!nonZeroNodes.isEmpty())
   {
    TreeNode tempNode = nonZeroNodes.pop();
    TreeNode toModify = nodes.pop();
    toModify.val = tempNode.val;
    finished.add(toModify);
   }
   while(!nodes.isEmpty())
   {
    TreeNode toModify = nodes.pop();
    toModify.val=0;
   }
  }
 }

Leetcode (Python): Combination Sum

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
• The solution set must not contain duplicate combinations.

For example, given candidate set 2,3,6,7 and target 7, 
A solution set is: 
[7] 
[2, 2, 3]

Solution:

class Solution:
    # @param candidates, a list of integers
    # @param target, integer
    # @return a list of lists of integers
    def combinationSum(self, candidates, target):
        candidates.sort()
        solution=[]
        self.combinationSumRec(candidates, target, 0, 0, [], solution)
        return solution
        
    def combinationSumRec(self, candidates, target, index, sum, listT, solution):
        if sum == target:
            solution.append(list(listT))
        for i in range(index,len(candidates)):
            if sum + candidates[i] > target:
                break;
            listT.append(candidates[i])
            self.combinationSumRec(candidates, target, i, sum+candidates[i], listT, solution)
            listT.pop()

Leetcode (Python): N-Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.
For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

Solution:

class Solution:
    # @return a list of lists of string
    def solveNQueens(self, n):
        solution = []
        
        oneSolution = []
        for i in range(0, n):
            row =[]
            for j in range(0, n):
                row.append('.')
            oneSolution.append(row)
        self.solveNQueensRec(0, n, oneSolution, solution)
        return solution
    
    def solveNQueensRec(self, row, n, oneSolution, solution):
        if row==n:
            tempSolution = []
            for i in range(0,n):
                tempSolution.append(''.join(oneSolution[i]))
            solution.append(tempSolution)
            
        for col in range(0,n):
            if self.canAdd(oneSolution, row, col):
                oneSolution[row][col]='Q'
                self.solveNQueensRec(row+1, n, oneSolution, solution)
                oneSolution[row][col]='.'
                
    def canAdd(self, oneSolution, row, col):
        for i in range(0,row):
            if oneSolution[i][col]=='Q':
                return False
            if col-row+i>=0 and oneSolution[i][col-row+i]=='Q':
                return False
            if col+row-i<len(oneSolution) and oneSolution[i][col+row-i]=='Q':
                return False
        return True

Leetcode: N-Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.
For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

Solution

public class Solution {
    public List<String[]> solveNQueens(int n) {
        boolean[][] board = new boolean[n][n];
        List<String[]> solution = new ArrayList<String[]>();
        solveNQueens(board, 0, solution);
        return solution;
    }
    
    public void solveNQueens(boolean[][]board, int row, List<String[]> solution)
    {
        if(row==board.length)
        {
            String[] oneSolution = new String[board.length];
            for(int i=0; i<board.length;i++)
            {
                StringBuilder sb = new StringBuilder();
                for(int j=0; j<board[0].length; j++)
                    if(board[i][j])
                        sb.append('Q');
                    else
                        sb.append('.');
                oneSolution[i] = sb.toString();
            } 
            solution.add(oneSolution);
            return;
        }
        for(int i=0; i<board[0].length; i++)
        {
            if(canAdd(board, row, i))
            {
                board[row][i]=true;
                solveNQueens(board, row+1, solution);
                board[row][i]=false;
            }
        }
    }
    
    private boolean canAdd(boolean[][] board, int row, int col)
    {
        for(int i=0; i<row; i++)
        {
            if(board[i][col])
                return false;
            if(col+i-row>=0 && board[i][col+i-row])
                return false;
            if(col+row-i<board[0].length && board[i][col+row-i])
                return false;
        }
        return true;
    }
}

Leetcode (Python): Maximal Rectangle

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.

Solution:

We keep the number of following rows and cols with a '1'.

class Solution:
    # @param matrix, a list of lists of 1 length string
    # @return an integer
    def maximalRectangle(self, matrix):
        maxArea = 0
        rows = []
        cols = []
        for i in range(0,len(matrix)):
            rowTemp = []
            colTemp = []
            for j in range(0, len(matrix[0])):
                rowTemp.append(0)
                colTemp.append(0)
            rows.append(rowTemp)
            cols.append(colTemp)
                
        for i in range(len(matrix)-1,-1,-1):
            for j in range(len(matrix[0])-1,-1,-1):
                area = 0
                if matrix[i][j]=='1':
                    if i==len(matrix)-1:
                        rows[i][j] = 1
                    else:
                        rows[i][j] = rows[i+1][j] + 1
                    if j == len(matrix[0])-1:
                        cols[i][j] = 1
                    else:
                        cols[i][j] = cols[i][j+1]+1
                    area = cols[i][j]
                    minCol = cols[i][j]
                for k in range(1, rows[i][j]):
                    if minCol > cols[i+k][j]:
                        minCol = cols[i+k][j]
                    if (k+1)*minCol > area:
                        area = (k+1)*minCol
                if maxArea < area:
                    maxArea = area
        return maxArea

Leetcode: Maximal Rectangle

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.

Solution:

We keep the number of following rows and cols with a '1'.

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if(matrix.length==0)
            return 0;
        int[][] rows = new int[matrix.length][matrix[0].length];
        int[][] cols = new int[matrix.length][matrix[0].length];
        int maxArea = 0;
        for(int i =matrix.length-1; i>=0; i--)
        {
            for(int j= matrix[0].length-1; j>=0; j--)
            {
                if(matrix[i][j]=='0')
                {
                    rows[i][j] = 0;
                    cols[i][j] = 0;
                }
                else
                {
                    rows[i][j]= i+1<matrix.length ? rows[i+1][j]+1 : 1;
                    cols[i][j]= j+1<matrix[0].length ? cols[i][j+1]+1 : 1;
                    int area = cols[i][j];
                    int minCol = cols[i][j];
                    for(int k=1; k<rows[i][j]; k++)
                    {
                        minCol = minCol > cols[i+k][j] ?cols[i+k][j] : minCol;
                        area = area < minCol * (k+1) ? minCol * (k+1) : area;
                    }
                    maxArea = maxArea < area ? area : maxArea;
                }
            }
        }
        return maxArea;
    }
}

Leetcode (Python): Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

Solution:

class Solution:
    # @param x, an integer
    # @return an integer
    def sqrt(self, x):
        if x < 0: 
            return -1
        begin = 0
        end = x
        while begin < end:
            midpoint = (begin+end+1)/2
            if midpoint* midpoint ==x:
                return midpoint
            if midpoint* midpoint < x:
                begin = midpoint
            else:
                end = midpoint - 1
        return begin

Leetcode: Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

Solution:

public class Solution {
    public int sqrt(int x) {
        if(x <= 0)
            return 0; //Is an error
        int i = 1;
        while(i<Integer.MAX_VALUE/(4*i) && (4*i*i)<x) i*=2;
        
      //Binary search between i and 2*i extended to long to avoid overflow issues
        long begin = i;
        long end = 2 * i;
        while(begin<end)
        {
            long midpoint = (begin + end +1)/2;
            if (midpoint * midpoint == x)
                return (int) midpoint;
            if (midpoint * midpoint < x)
                begin = midpoint;
            else
                end = midpoint-1;
        }
        return (int) begin;
    }
}

Leetcode (Python): Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example, 
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Solution:

class Solution:
    # @param A, a list of integers
    # @return an integer
    def trap(self, A):
        max = 0
        maxIndex = 0
        for i in range(0,len(A)):
            if A[i] > max:
                max = A[i]
                maxIndex = i
                
        previousMax = 0
        count = 0
        for i in range(0, maxIndex):
            if A[i] > previousMax:
                previousMax = A[i]
            count += previousMax - A[i]
        
        previousMax = 0
        for i in range(len(A)-1, maxIndex, -1):
            if A[i] > previousMax:
                previousMax = A[i]
            count += previousMax - A[i]
        return count

Leetcode: Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example, 
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Solution:

public class Solution {
    public int trap(int[] A) {
        int max = 0;
        int maxIndex=0;
        for(int i=0; i< A.length; i++)
        {
            if(A[i]>max)
            {  
                max = A[i];
                maxIndex = i;
            }
        }
        
        int prevMax = 0;
        int count = 0;
        for(int i=0; i<maxIndex; i++)
        {
            if(A[i]>prevMax)
                prevMax = A[i];
            count += prevMax - A[i];
        }
        
        prevMax = 0;
        for(int i=A.length-1; i>maxIndex; i--)
        {
            if(A[i]>prevMax)
                prevMax = A[i];
            count += prevMax -A[i];
        }
        return count;
    }
}

LeetCode (Python): Add Binary

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

Solution:

class Solution:
    # @param a, a string
    # @param b, a string
    # @return a string
    def addBinary(self, a, b):
        solution = []
        sum = 0
        for i in range(0,max(len(a),len(b))):
            if i < len(a) and a[len(a)-1-i]=='1':
                sum += 1
            if i < len(b) and b[len(b)-1-i]=='1':
                sum += 1
            solution.insert(0,str(sum%2))
            sum /= 2
        if sum >0:
            solution.insert(0,str(sum%2))
        return ''.join(solution)

Leetcode (Python): Gray Code

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2

Note:
For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

Solution:

class Solution:
    # @return a list of integers
    def grayCode(self, n):
        used =[]
        solution =[]
        for i in range(0,2**n):
            used.append(False)
        self.grayCodeRec(0, n, used, solution)
        return solution
        
    def grayCodeRec(self, num, n, used, solution):
        solution.append(num)
        used[num] = True
        if len(solution)==2**n:
            return True
        for i in range(0,n):
            num2 = num ^ (1<<i)
            if not used[num2] and self.grayCodeRec(num2, n, used, solution):
                return True
        used[num] = False
        solution.pop()
        return False

Leetcode (Python): Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

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
    # @param sum, an integer
    # @return a boolean
    def hasPathSum(self, root, sum):
        return self.hasPathSumRec(root, sum, 0)
    
    def hasPathSumRec(self, root, sum, tempSum):
        if root == None:
            return False
        if root.left == None and root.right == None:
            return tempSum+root.val == sum
        return self.hasPathSumRec(root.left, sum, tempSum + root.val) or self.hasPathSumRec(root.right, sum, tempSum + root.val)

Leetcode: Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

Solution:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        return hasPathSum(root, sum, 0);
    }
    
    public boolean hasPathSum(TreeNode root, int sum, int tempSum) 
    {
        if(root == null)
            return false;
        if( root.left==null && root.right == null)
            return tempSum + root.val == sum;
        return hasPathSum(root.left, sum, tempSum+root.val) ||  hasPathSum(root.right, sum, tempSum+root.val);
    }
}

Leetcode (Python): Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

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 num, a list of integers
    # @return a tree node
    def sortedArrayToBST(self, num):
        return self.sortedArrayToBSTRec(num, 0, len(num)-1)
        
    def sortedArrayToBSTRec(self, num, begin, end):
        if begin>end:
            return None
        midPoint = (begin+end)//2
        root = TreeNode(num[midPoint])
        root.left = self.sortedArrayToBSTRec(num, begin, midPoint-1)
        root.right = self.sortedArrayToBSTRec(num, midPoint+1,end)
        return root

Leetcode (Python): Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

For example,
Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

Solution

Using two binary searches: one to find the row to look into and then one internal to the row.

class Solution:
    # @param matrix, a list of lists of integers
    # @param target, an integer
    # @return a boolean
    def searchMatrix(self, matrix, target):
        if len(matrix)==0 or len(matrix[0]) ==0 or matrix[0][0]> target:
            return False
        start = 0
        end = len(matrix)-1
        while start<end:
            midpoint = (start+end+1)/2
            if matrix[midpoint][0]==target:
                return True
            if matrix[midpoint][0] > target:
                end = midpoint-1
            else:
                start = midpoint
        row = start
        
        start = 0
        end = len(matrix[row])-1
        while start <= end:
            midpoint = (start+end)/2
            if matrix[row][midpoint]==target:
                return True
            if matrix[row][midpoint]<target:
                start = midpoint + 1
            else:
                end = midpoint - 1
        return False

Leetcode: Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

For example,
Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

Solution

Using two binary searches: one to find the row to look into and then one internal to the row.

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        //Find the row 
        int start = 0;
        int end = matrix.length-1;
        if(matrix.length==0 || matrix[0].length == 0 || matrix[0][0]>target)
            return false;
        while(start < end)
        {
            int midpoint = (start+end+1)/2;
            if (matrix[midpoint][0]==target)
                return true;
            if (matrix[midpoint][0]>target)
                end = midpoint-1;
            else
                start = midpoint;
        }
        int row = start;

        //Binary search internal to the row
        start = 0;
        end =  matrix[row].length-1;
        
        while(start <= end)
        {
            int midpoint = (start+end)/2;
            if (matrix[row][midpoint]==target)
                return true;
            if (matrix[row][midpoint]<target)
                start = midpoint+1;
            else
                end = midpoint-1;
                
        }
        return false;
    }
}

Leetcode (Python): Plus One

Given a number represented as an array of digits, plus one to the number.

Solution:

class Solution:
    # @param digits, a list of integer digits
    # @return a list of integer digits
    def plusOne(self, digits):
        carryOn = True
        for i in range(len(digits)-1,-1,-1):
            if carryOn == False:
                break
            digits[i] += 1
            carryOn = digits[i] >9
            digits[i] %= 10
        if carryOn:
            digits.insert(0,1)
        return digits

Leetcode (Python) : Text Justification

Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly Lcharacters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

For the last line of text, it should be left justified and no extra space is inserted between words.

For example,
words: ["This", "is", "an", "example", "of", "text", "justification."]
L: 16.

Return the formatted lines as:

[
   "This    is    an",
   "example  of text",
   "justification.  "
]

Note: Each word is guaranteed not to exceed L in length.

Solution:

class Solution:
    # @param words, a list of strings
    # @param L, an integer
    # @return a list of strings
    def fullJustify(self, words, L):
        firstWord =0
        numWords = 0
        caractersInLine = 0
        solution = []
        for i in range(0,len(words)):
            if caractersInLine + numWords + len(words[i])>L:
                line = []
                if numWords>1:
                    spaces = (L-caractersInLine) // (numWords-1)
                    extraspaces = (L-caractersInLine) % (numWords-1)
                for j in range(firstWord, i):
                    line.append(words[j])
                    if j == i-1:
                        break
                    for n in range(0, spaces):
                        line.append(' ')
                    if j-firstWord < extraspaces:
                        line.append(' ')
                if numWords == 1:
                    for n in range(len(words[firstWord]), L):
                        line.append(' ')
                solution.append(''.join(line))
                firstWord =i
                numWords = 0
                caractersInLine = 0
            numWords += 1
            caractersInLine += len(words[i])
        line = []
        if firstWord == 0 or firstWord < len(words):
            line =[]
            for j in range(firstWord, len(words)):
                line.append(words[j])
                if j == len(words)-1:
                    break
                line.append(' ')
            for n in range(len(''.join(line)),L):
                line.append(' ')
            solution.append(''.join(line))
        return solution

Leetcode (Python): Linked List Cycle

Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space? 

Solution:

Using a fast pointer that advances two nodes each time and a slow pointer that advances on node, we always detect a cycle as the fast pointer cannot overtake the slow one without being in the same node in one of the ``turns".

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param head, a ListNode
    # @return a boolean
    def hasCycle(self, head):
        fastPointer = head
        slowPointer = head
        while fastPointer != None and fastPointer.next != None:
            fastPointer = fastPointer.next.next
            slowPointer = slowPointer.next
            if fastPointer == slowPointer:
                return True
        return False

Leetcode: Linked List Cycle

Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space? 

Solution:

Using a fast pointer that advances two nodes each time and a slow pointer that advances on node, we always detect a cycle as the fast pointer cannot overtake the slow one without being in the same node in one of the ``turns".

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast!=null && fast.next !=null)
        {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow)
                return true;
        }
        return false;
    }
}

Leetcode (Python): Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

Solution:

class Solution:
    # @return a string
    def longestCommonPrefix(self, strs):
        if len(strs) == 0:
            return ""
        for i in range(len(strs[0])-1,-1,-1):
            prefix = strs[0][:i+1]
            validPrefix = True
            for j in range(1,len(strs)):
                if len(strs[j])<=i or strs[j][:i+1]!=prefix:
                    validPrefix = False
                    break
            if validPrefix:
                return prefix
        return ""

Leetcode: Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

Solution:

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs.length==0)
            return "";
        outerloop:
        for(int i=strs[0].length(); i>0; i--)
        {
            String prefix = strs[0].substring(0,i);
            for(int j=1; j<strs.length; j++)
            {
                if(strs[j].length()<i || ! strs[j].substring(0,i).equals(prefix))
                    continue outerloop;
            }
            return prefix;
        }
        return "";
    }
}

Leetcode (Python): Container With Most Water

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

Solution:

class Solution:
    # @return an integer
    def maxArea(self, height):
        maxArea = 0
        start = 0
        end = len(height)-1
        while start < end:
            area = (end-start)* min(height[end],height[start])
            if area > maxArea:
                maxArea = area
            if height[end]<height[start]:
                end-=1
            else:
                start +=1
        return maxArea

Leetcode (Python): Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Solution

# Definition for singly-linked list with a random pointer.
# class RandomListNode:
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None

class Solution:
    # @param head, a RandomListNode
    # @return a RandomListNode
    def copyRandomList(self, head):
        return self.copyRandomListRec(head, {})
        
    def copyRandomListRec(self, head, used):
        if head == None:
            return None
        if head in used:
            return used[head]
        node = RandomListNode(head.label)
        used[head] = node
        node.next = self.copyRandomListRec(head.next, used)
        node.random = self.copyRandomListRec(head.random, used)
        return node

Leetcode (Python): Valid Number

Validate if a given string is numeric.

Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true

Solution:

This problem deals with a common problem in compilers in the lexical analysis, i.e.  knowing if a certain string is a valid token.

We accept the following regular grammar, shown as UNIX regular expression by simplicity:
\s*[\+\-]?(([0-9]+(\.[0-9]*)?)|\.[0-9]+)([eE][+-]?[0-9]+)?\s*
where \s represents [ \t].

This regular expression is accepted by the underneath DFA(Deterministic Finite Automata):

where any transition not shown takes to an error state, that in the code is represented by -1.

class Solution:
    # @param s, a string
    # @return a boolean
    def isNumber(self, s):
        state = 0
        for i in xrange(0,len(s)):
            state = self.nextState(state, s[i])
            if state == -1: 
                return False
        state = self.nextState(state, ' ')
        return state == 8
    
    def nextState(self, state,char):
        transititionTable = [[0,2,1,3,-1,-1], [-1,2,-1,3,-1,-1], [8,2,-1,4,5,-1], [-1,4,-1,-1,-1,-1], [8,4,-1,-1,5,-1],[-1,7,6,-1,-1,-1],[-1,7,-1,-1,-1,-1], [8,7,-1,-1,-1,-1], [8,-1,-1,-1,-1,-1]];
        return transititionTable[state][self.getSymbol(char)]
    
    def getSymbol(self, char):
        if char == ' ' or char == '\t':
            return 0
        if char.isdigit():
            return 1
        if char == '+'  or char == '-':
            return 2
        if char == '.':
            return 3
        if char == 'E' or char =='e':
            return 4
        return 5

More information:
[1, Chapter 1] J. Glen Brookshear, "Theory of Computation: Formal Languages, Automata, and Complexity", Addison-Wesley.

[2, Chapters 2-3] Rajeev Motwani, Jeffrey Ullman, and John Hopcroft, "Introduction to Automata Theory, Languages, and Computation", Addison-Wesley.

Leetcode (Python): Set Matrix Zeroes

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

Solution:

We could use two arrays to mark the rows and cols that have a zero in it, but to use constant space we can use the first row and column (or any other). As afterwards we do not know if this row and col had at the beginning a zero or not, we save this information before modifying them.

class Solution:
    # @param matrix, a list of lists of integers
    # RETURN NOTHING, MODIFY matrix IN PLACE.
    def setZeroes(self, matrix):
        firstRowHasZero = False
        firstColHasZero = False
        if len(matrix)==0 or len(matrix[0]) == 0:
            return
        for col in range(0,len(matrix[0])):
            if matrix[0][col]==0:
                firstRowHasZero = True
                break
        for row in range(0, len(matrix)):
            if matrix[row][0]==0:
                firstColHasZero = True
                break
            
        for row in range(1, len(matrix)):
            for col in range(1,len(matrix[0])):
                if matrix[row][col] == 0:
                    matrix[0][col] = 0
                    matrix[row][0] = 0
        
        for row in range(1, len(matrix)):
            for col in range(1,len(matrix[0])):
                if matrix[row][0] == 0 or matrix[0][col] == 0:
                    matrix[row][col] = 0
        
        if firstRowHasZero:
            for col in range(0,len(matrix[0])):
                matrix[0][col] = 0
        
        if firstColHasZero:
            for row in range(0, len(matrix)):
                matrix[row][0] = 0

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

Solution

This problem logic is easy, we have only to be careful with the position index.  For instance,

1     2     3     4

5     6     7     8

9   10    11   12

13   14   15   16

We have marked in pink the elements that rotate for row 0, column 1.

class Solution:
    # @param matrix, a list of lists of integers
    # @return a list of lists of integers
    def rotate(self, matrix):
        for i in range(0, len(matrix)//2):
            for j in range(i, len(matrix)-1-i):
                temp = matrix[i][j]
                matrix[i][j] = matrix[len(matrix)-1-j][i]
                matrix[len(matrix)-1-j][i] = matrix[len(matrix)-1-i][len(matrix)-1-j]
                matrix[len(matrix)-1-i][len(matrix)-1-j] = matrix[j][len(matrix)-1-i]
                matrix[j][len(matrix)-1-i] = temp
        return matrix

Leetcode (Python): Remove Nth Node From End of List

Given a linked list, remove the nth node from the end of list and return its head.

For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.
Try to do this in one pass.

Solution:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @return a ListNode
    def removeNthFromEnd(self, head, n):
        dummy = ListNode(0);
        dummy.next = head;
        fast = dummy;
        for i in range(0,n):
            if fast != None:
                fast = fast.next
        if fast == None or n==0:
            return head
        
        slow = dummy
        while fast.next != None:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return dummy.next

Leetcode: Remove Nth Node From End of List

Given a linked list, remove the nth node from the end of list and return its head.

For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.
Try to do this in one pass.

Solution:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode fast = dummy;
        for (int i=0; i<n; i++)
        {
            fast = fast != null ? fast.next : null;
        }
        
        if(fast == null || n < 0)
            return head;
            
        ListNode slow = dummy;
        while(fast.next != null)
        {
            fast = fast.next;
            slow = slow.next;
        }
        
        slow.next = slow.next.next;
        return dummy.next;
    }
}

Leetcode: Word Ladder II

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

Return

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

Note:

• All words have the same length.
• All words contain only lowercase alphabetic characters.

Solution:

BFS

public class Solution {
     public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) {
        
        //construct graph
        HashMap<String, HashSet<String>> graph = new HashMap<String, HashSet<String>>();
        dict.add(start);
        dict.add(end);
        for(String key : dict){
            HashSet<String> neighbours = new HashSet<String>();
            char[] chars = key.toCharArray();
            for(int i = 0; i < chars.length; i++){
                char c = chars[i];
                for(char replace = 'a'; replace <='z'; replace ++){
                    if(replace == c) continue;
                    chars[i] = replace;
                    String temp = new String(chars);
                    if(dict.contains(temp)){
                        neighbours.add(temp);
                    }
                chars[i] = c;
                }
            }
            graph.put(key, neighbours);
        }
        
        return BFS(dict, graph, start, end);
    }
    
    public ArrayList<ArrayList<String>> BFS(HashSet<String> dict,  HashMap<String, HashSet<String>> graph, String start, String end){
        ArrayList<String> level = new ArrayList<String>();
        level.add(start);
        ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
        HashMap<String, ArrayList<String>> predecessors = new HashMap<String, ArrayList<String>> ();
        dict.remove(start);
        predecessors.put(start, new ArrayList<String>());
        
        while(!level.isEmpty()){
            ArrayList<String> nextLevel = new ArrayList<String>();
            for(String s : level){
                HashSet<String> children = graph.get(s);
            
                for(String child : children){
                    if(!dict.contains(child)) continue;
                    
                    if(!nextLevel.contains(child))
                        nextLevel.add(child);
                    if(predecessors.containsKey(child)){
                        predecessors.get(child).add(s);
                    }else{
                        ArrayList<String> list = new ArrayList<String>();
                        list.add(s);
                        predecessors.put(child, list);
                    }
                }
                
                
            }
            
            
            level = nextLevel;
            dict.removeAll(level);
            
            if(level.contains(end)){
                
                    buildPaths(result, predecessors, new ArrayList<String>(), end, start);
                    return result;

            }
        }
        
        return result;
    }
    

    public void buildPaths(ArrayList<ArrayList<String>> result,  HashMap<String, ArrayList<String>> predecessors, ArrayList<String> path, String current, String start){
        path.add(0, current);
        if(current.equals(start)){
            result.add(path);
            return;
        }
        for(String s : predecessors.get(current)){
            ArrayList<String> nextPath = new ArrayList<String>(path);
            buildPaths(result, predecessors, nextPath, s, start);
        }
    }
}

Two directions

In order to improve the performance, we try to traverse the graph starting from the both extremes and detecting when one has overlapped.

public class Solution {
    public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) 
    {
        HashMap<String, HashSet<String>> neighborMap = new HashMap<String, HashSet<String>>();
        HashMap<String, ArrayList<String>> predecessors = new HashMap<String, ArrayList<String>>();
        for(String word: dict)
        {
            HashSet<String> neighbors = new HashSet<String>();
            char[] wordArray = word.toCharArray();
            for(int i=0; i< wordArray.length; i++)
            {
                char originalLetter = wordArray[i];
                for (char newLetter = 'a'; newLetter<='z'; newLetter++)
                {
                    if (newLetter == originalLetter)
                        continue;
                    wordArray[i] = newLetter;
                    if (dict.contains(new String(wordArray)))
                        neighbors.add(new String(wordArray));
                }
                wordArray[i] = originalLetter;
            }
            neighborMap.put(word, neighbors);
            predecessors.put(word, new ArrayList<String>());
        }
        
        
        HashSet<String> fromBegin = new HashSet<String>();
        HashSet<String> fromEnd = new HashSet<String>();
        fromBegin.add(start);
        fromEnd.add(end);
        
        ArrayList<String> nextFromTop = new ArrayList<String>();
        ArrayList<String> nextFromBottom = new ArrayList<String>();
         ArrayList<String> actual;
        nextFromTop.add(start);
        nextFromBottom.add(end);
        
        
        boolean isBeginTurn = true;
        boolean completed = false;
        
        while(!completed)
        {
            
            if(isBeginTurn)
            {
                HashSet<String> level = new HashSet<String>();
                actual = nextFromTop;
                if(actual.size()==0)
                    return new ArrayList<ArrayList<String>>();
                nextFromTop = new ArrayList<String>();
                for(String node: actual)
                {
                    for(String child: neighborMap.get(node))
                    {
                        if(fromBegin.contains(child))
                            continue;
                        if(!level.contains(child))
                        {
                            nextFromTop.add(child);
                            level.add(child);
                        }
                        predecessors.get(child).add(node);
                        if(fromEnd.contains(child))
                            completed = true;
                    }
                }
                fromBegin.addAll(level);
                isBeginTurn = false;
            }
            else
            {
                HashSet<String> level = new HashSet<String>();
                actual = nextFromBottom;
                if(actual.size()==0)
                    return new ArrayList<ArrayList<String>>();
                nextFromBottom = new ArrayList<String>();
                for(String node: actual)
                {
                    for(String child: neighborMap.get(node))
                    {
                        if(fromEnd.contains(child))
                            continue;
                        if(!level.contains(child))
                        {
                            nextFromBottom.add(child);
                            level.add(child);
                        }
                        predecessors.get(node).add(child);
                        if(fromBegin.contains(child))
                            completed = true;
                    }
                }
                fromEnd.addAll(level);
                isBeginTurn = true;
            }
        }
        ArrayList<ArrayList<String>> solution =new ArrayList<ArrayList<String>>();
        createSolution(start, end, predecessors, new ArrayList<String>(), solution);
        return solution;
    }
    
    private void createSolution(String start, String word, HashMap<String, ArrayList<String>> predecessors, ArrayList<String> temp, ArrayList<ArrayList<String>> solution)
    {
        if (word == start)
            solution.add(temp);
        temp.add(0,word);
        for(String newWord: predecessors.get(word))
        {
            createSolution(start, newWord, predecessors, (ArrayList<String>) temp.clone(), solution);
        }
    }
}

Comparisong of times we obtain for this complexity running Leetcode is around 6%: 1300ms vs 1224 ms