solutions


Remove Linked List Elements

Remove all elements from a linked list of integers that have value val. Example Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6 Return: 1 --> 2 --> 3 --> 4 --> 5

In [ ]:
class Solution(object):
    def removeElements(self, head, val):
        """
        :type head: ListNode
        :type val: int
        :rtype: ListNode
        """
        if head is None:
            return head
        dummy = ListNode(0)
        dummy.next = head
        pos = dummy
        while pos.next:
            if pos.next.val == val:
                pos.next = pos.next.next
            else:
                pos = pos.next
        return dummy.next

Happy Number

Write an algorithm to determine if a number is "happy". A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers. Example: 19 is a happy number 12 + 92 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1

In [ ]:
class Solution(object):
    def isHappy(self, n):
        """
        :type n: int
        :rtype: bool
        """
        def split(N):
            ans = []
            while N > 0:
                ans.append(N%10)
                N /= 10
            return ans
        nums = {}
        while True:
            val = sum([x**2 for x in split(n)])
            if val == 1:
                return True
            elif val in nums:
                return False
            else:
                nums[val] = 1
                n = val

House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night. Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

In [ ]:
class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        L = len(nums)
        if L == 0:
            return 0
        elif L == 1:
            return nums[0]
        elif L == 2:
            return max(nums[0], nums[1])
        dp = [0] * L
        dp[0] = nums[0]
        if nums[1] > nums[0]:
            dp[1] = nums[1]
        else:
            dp[1] = nums[0]
        for n in xrange(2, L):
            dp[n] = max(dp[n-1], nums[n]+dp[n-2])
        return dp[-1]

Number of 1 Bits

Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight). For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.

In [ ]:
class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        num = 0
        for _ in xrange(32):
            if n % 2 == 1:
                num += 1
            n = n >> 1
        return num

Reverse Bits

Reverse bits of a given 32 bits unsigned integer. For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100101000000). Follow up: If this function is called many times, how would you optimize it?

In [ ]:
class Solution:
    # @param n, an integer
    # @return an integer
    def reverseBits(self, n):
        new = 0
        for i in xrange(32):
            new = (new << 1) | ((n >> i) % 2)
        return new

Rotate Array

Rotate an array of n elements to the right by k steps. For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4]. Note: Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

In [ ]:
class Solution(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        L = len(nums)
        k = k%L
        buff =  nums[L-k:]
        for i in xrange(L-k-1, -1, -1):
            nums[i+k] = nums[i]
        for i in xrange(k):
            nums[i] = buff[i]

Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!. Note: Your solution should be in logarithmic time complexity.

In [ ]:
class Solution(object):
    def trailingZeroes(self, n):
        """
        :type n: int
        :rtype: int
        """
        ans, base = 0, 5
        while base <= n:
            ans += n/base
            base *= 5
        return ans

Excel Sheet Column Number

Related to question Excel Sheet Column Title Given a column title as appear in an Excel sheet, return its corresponding column number. For example: A -> 1 B -> 2 C -> 3 ... Z -> 26 AA -> 27 AB -> 28

In [ ]:
class Solution(object):
    def titleToNumber(self, s):
        """
        :type s: str
        :rtype: int
        """
        L = len(s)
        num = 0
        for pos in xrange(L):
            num += (ord(s[L-pos-1]) - 64) * 26**pos
        return num

Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times. You may assume that the array is non-empty and the majority element always exist in the array.

In [ ]:
class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        lim = len(nums)/2
        pre = {}
        for n in nums:
            if n in pre:
                pre[n] += 1
                if pre[n] > lim:
                    return n
            else:
                pre[n] = 1
        return pre.keys()[-1]

Excel Sheet Column Title

Given a positive integer, return its corresponding column title as appear in an Excel sheet. For example: 1 -> A 2 -> B 3 -> C ... 26 -> Z 27 -> AA 28 -> AB

In [ ]:
class Solution(object):
    def convertToTitle(self, n):
        """
        :type n: int
        :rtype: str
        """
        col = ''
        while n > 26:
            s = n % 26
            if s == 0:
                s = 26
            n = (n-s) / 26
            col = chr(s+64) + col
        col = chr(n+64) + col
        return col

Compare Version Numbers

Compare two version numbers version1 and version2. If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0. You may assume that the version strings are non-empty and contain only digits and the . character. The . character does not represent a decimal point and is used to separate number sequences. For instance, 2.5 is not "two and a half" or "half way to version three", it is the fifth second-level revision of the second first-level revision. Here is an example of version numbers ordering: 0.1 < 1.1 < 1.2 < 13.37

In [ ]:
class Solution(object):
    def compareVersion(self, version1, version2):
        """
        :type version1: str
        :type version2: str
        :rtype: int
        """
        v1 = map(int, version1.split('.'))
        v2 = map(int, version2.split('.'))
        i, j = 0, 0
        L1, L2 = len(v1), len(v2)
        while i < L1 and j < L2:
            if v1[i] > v2[j]:
                return 1
            elif v1[i] < v2[j]:
                return -1
            else:
                i += 1
                j += 1
        while i < L1:
            if v1[i] > 0:
                return 1
            i += 1
        while j < L2:
            if v2[j] > 0:
                return -1
            j += 1
        return 0

Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins. For example, the following two linked lists: A: a1 → a2 ↘ c1 → c2 → c3 ↗ B: b1 → b2 → b3 begin to intersect at node c1. Notes: If the two linked lists have no intersection at all, return null. The linked lists must retain their original structure after the function returns. You may assume there are no cycles anywhere in the entire linked structure. Your code should preferably run in O(n) time and use only O(1) memory.

In [ ]:
class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        if headA == None or headB == None:
            return None
        
        La, tailA = 0, headA
        while tailA.next:
            La += 1
            tailA = tailA.next
        
        Lb, tailB = 0, headB
        while tailB.next:
            Lb += 1
            tailB = tailB.next
        
        if tailA != tailB:
            return None
        
        if La > Lb:
            for _ in xrange(La-Lb):
                headA = headA.next
        else:
            for _ in xrange(Lb-La):
                headB = headB.next
        
        while headA and headA != headB:
            headA = headA.next
            headB = headB.next
        return headA

Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. push(x) -- Push element x onto stack. pop() -- Removes the element on top of the stack. top() -- Get the top element. getMin() -- Retrieve the minimum element in the stack. Example: MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> Returns -3. minStack.pop(); minStack.top(); --> Returns 0. minStack.getMin(); --> Returns -2.

In [ ]:
class MinStack(object):

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.minVals = []
        self.vals = []

    def push(self, x):
        """
        :type x: int
        :rtype: void
        """
        self.vals.append(x)
        if len(self.minVals) == 0 or x <= self.minVals[-1]:
            self.minVals.append(x)

    def pop(self):
        """
        :rtype: void
        """
        if self.minVals[-1] == self.vals[-1]:
            self.minVals.pop()
        self.vals.pop()

    def top(self):
        """
        :rtype: int
        """
        return self.vals[-1]

    def getMin(self):
        """
        :rtype: int
        """
        return self.minVals[-1]

Contains Duplicate

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

In [ ]:
class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        dic = {}
        for n in nums:
            if n in dic:
                return True
            else:
                dic[n] = 1
        return False

Best Time to Buy and Sell Stock III

Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most two transactions. Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

In [ ]:
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        L = len(prices)
        if L == 0:
            return 0
        profits = [0] * L
        leftBuy, leftProfit = prices[0], 0
        for i in xrange(1,L):
            if prices[i] < leftBuy:
                leftBuy = prices[i]
            else:
                leftProfit = max(leftProfit, prices[i] - leftBuy)
            profits[i] = leftProfit
        
        rightSell, rightProfit, ans = prices[-1], 0, profits[-1]
        for j in xrange(L-2, -1, -1):
            if prices[j] > rightSell:
                rightSell = prices[j]
            else:
                rightProfit = max(rightProfit, rightSell - prices[j])
            ans = max(ans, rightProfit+profits[j])
        return ans

Best Time to Buy and Sell Stock II

Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

In [ ]:
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        profit = 0
        for i in xrange(1, len(prices)):
            if prices[i] > prices[i-1]:
                profit += (prices[i]-prices[i-1])
        return profit

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?

In [ ]:
class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if head is None:
            return False
        fast, slow = head, head
        while fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                return True
        return False

Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. For example, "A man, a plan, a canal: Panama" is a palindrome. "race a car" is not a palindrome. Note: Have you consider that the string might be empty? This is a good question to ask during an interview. For the purpose of this problem, we define empty string as valid palindrome.

In [ ]:
class Solution(object):
    def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        s = re.sub('[^A-Za-z0-9]+', '', s)
        if s == "":
            return True
        i, j = 0, len(s)-1
        while i < j:
            if s[i].lower() != s[j].lower():
                return False
            i += 1
            j -= 1
        return True

Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i. If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit. Example 1: Input: [7, 1, 5, 3, 6, 4] Output: 5 max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price) Example 2: Input: [7, 6, 4, 3, 1] Output: 0 In this case, no transaction is done, i.e. max profit = 0.

In [ ]:
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if prices == []:
            return 0
        buy, profit = prices[0], 0
        for sell in prices[1:]:
            if sell - buy > profit:
                profit = sell - buy
            elif sell < buy:
                buy = sell
        return profit

Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below. For example, given the following triangle [ [2], [3,4], [6,5,7], [4,1,8,3] ] The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11). Note: Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

In [ ]:
class Solution(object):
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        rows = len(triangle)
        if rows == 0:
            return 0
        nums = triangle[-1]
        for row in xrange(rows-2, -1, -1):
            for col in xrange(len(triangle[row])):
                nums[col] = min(nums[col], nums[col+1]) + triangle[row][col]
        return nums[0]

Pascal's Triangle II

Given an index k, return the kth row of the Pascal's triangle. For example, given k = 3, Return [1,3,3,1]. Note: Could you optimize your algorithm to use only O(k) extra space?

In [ ]:
class Solution(object):
    def getRow(self, rowIndex):
        """
        :type rowIndex: int
        :rtype: List[int]
        """
        nums = [0] * (rowIndex+2)
        nums[1] = 1
        for i in xrange(1, rowIndex+1):
            for j in xrange(rowIndex+1, 0, -1):
                nums[j] += nums[j-1]
        return nums[1:]

Pascal's Triangle

Given numRows, generate the first numRows of Pascal's triangle. For example, given numRows = 5, Return [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ]

In [ ]:
class Solution(object):
    def generate(self, numRows):
        """
        :type numRows: int
        :rtype: List[List[int]]
        """
        if numRows < 1:
            return []
        ans = [[1]]
        while numRows > 1:
            i, last = 0, ans[-1]
            L, temp = len(last), []
            while i+1 < L:
                temp.append(last[i]+last[i+1])
                i += 1
            ans.append([1]+temp+[1])
            numRows -= 1
                
        return ans

Populating Next Right Pointers in Each Node

Given a binary tree struct TreeLinkNode { TreeLinkNode *left; TreeLinkNode *right; TreeLinkNode *next; } Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL. Initially, all next pointers are set to NULL. Note: You may only use constant extra space. You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children). For example, Given the following perfect binary tree, 1 / \ 2 3 / \ / \ 4 5 6 7 After calling your function, the tree should look like: 1 -> NULL / \ 2 -> 3 -> NULL / \ / \ 4->5->6->7 -> NULL

In [ ]:
class Solution:
    # @param root, a tree link node
    # @return nothing
    def connect(self, root):
        now = root
        leftMost = None
        while now and now.left:
            if leftMost is None:
                leftMost = now.left
            now.left.next = now.right
            if now.next:
                now.right.next = now.next.left
                now = now.next
            else:
                now = leftMost
                leftMost = None

Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place. For example, Given 1 / \ 2 5 / \ \ 3 4 6 The flattened tree should look like: 1 \ 2 \ 3 \ 4 \ 5 \ 6

In [ ]:
class Solution(object):
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: void Do not return anything, modify root in-place instead.
        """
        if root is None:
            return None
        def clean(node):
            if node is None:
                return None
            if node.left is None and node.right is None:
                return (node, node)
            right = clean(node.right)
            left = clean(node.left)
            if left:
                node.right = left[0]
                node.left = None
                if right:
                    left[1].right = right[0]
                    return (node, right[1])
                else:
                    return (node, left[1])
            else:
                if right:
                    return (node, right[1])
        clean(root)

Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum. For example: Given the below binary tree and sum = 22, 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1 return [ [5,4,11,2], [5,8,4,5] ]

In [ ]:
class Solution(object):
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: List[List[int]]
        """
        paths = []
        def findPath(node, path, S):
            if node is None:
                return
            if node.left is None and node.right is None:
                if node.val == S:
                    paths.append(path+[node.val])
            findPath(node.left, path+[node.val], S-node.val)
            findPath(node.right, path+[node.val], S-node.val)
        findPath(root, [], sum)
        return paths

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.

In [ ]:
class Solution(object):
    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        def pathSum(node, S):
            if node.left == None and node.right == None:
                return S == node.val
            elif node.left:
                if node.right:
                    return pathSum(node.left, S-node.val) or pathSum(node.right, S-node.val)
                else:
                    return pathSum(node.left, S-node.val)
            elif node.right:
                return pathSum(node.right, S-node.val)
            else:
                return False
        
        if root is None:
            return False
        return pathSum(root, sum)

Balanced Binary Tree

Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

In [ ]:
class Solution(object):
    def findDepth(self, root):
        if root == None:
            return 0
        left = self.findDepth(root.left)
        if left == -1:
            return -1
        right = self.findDepth(root.right)
        if right == -1:
            return -1
        if abs(right-left) <= 1:
            return max(right, left) + 1
        else:
            return -1
    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        return self.findDepth(root) != -1

Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

In [ ]:
class Solution(object):
    def sortedListToBST(self, head):
        """
        :type head: ListNode
        :rtype: TreeNode
        """
        n, pos = 0, head
        while pos:
            n += 1
            pos = pos.next
        self.head = head
        def buildTree(start, end):
            if start > end:
                return None
            mid = (start+end)/2
            left = buildTree(start, mid-1)
            root = TreeNode(self.head.val)
            root.left = left
            self.head = self.head.next
            root.right = buildTree(mid+1, end)
            return root
        return buildTree(0, n-1)

Convert Sorted Array to Binary Search Tree

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

In [ ]:
class Solution(object):
    def finder(self, nums, val):
        left, right = 0, len(nums)-1
        while left <= right:
            mid = (left+right)/2
            if nums[mid] == val:
                right = mid-1
            else:
                left = mid+1
        return right+1
    def sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        L = len(nums)
        if L == 0:
            return None
        mid = L/2
        val = nums[mid]
        if val == nums[mid-1]:
            mid = self.finder(nums[:mid], val)
        root = TreeNode(val)
        root.left = self.sortedArrayToBST(nums[:mid])
        root.right = self.sortedArrayToBST(nums[mid+1:])
        return root

Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root). For example: Given binary tree [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 return its bottom-up level order traversal as: [ [15,7], [9,20], [3] ]

In [ ]:
class Solution(object):
    def levelOrderBottom(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        ans = []
        nodes = [root]
        while len(nodes) > 0:
            vals, temp = [], []
            for node in nodes:
                if node:
                    vals.append(node.val)
                    temp.append(node.left)
                    temp.append(node.right)
            if vals:
                ans = [vals] + ans
            nodes = temp
        return ans

Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree. Note: You may assume that duplicates do not exist in the tree.

In [ ]:
class Solution(object):
    def buildTree(self, inorder, postorder):
        """
        :type inorder: List[int]
        :type postorder: List[int]
        :rtype: TreeNode
        """
        self.i = len(postorder)-1
        def helper(Inorder):
            if Inorder == []:
                return None
            root = TreeNode(postorder[self.i])
            j = Inorder.index(postorder[self.i])
            self.i -= 1
            root.right = helper(Inorder[j+1:])
            root.left = helper(Inorder[:j])
            return root
        return helper(inorder)

Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree. Note: You may assume that duplicates do not exist in the tree.

In [ ]:
class Solution(object):
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        self.i = 0
        def helper(Inorder):
            if Inorder == []:
                return None
            root = TreeNode(preorder[self.i])
            j = Inorder.index(preorder[self.i])
            self.i += 1
            root.left = helper(Inorder[:j])
            root.right = helper(Inorder[j+1:])
            return root
        return helper(inorder)

Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

In [ ]:
class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root is None:
            return 0
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between). For example: Given binary tree [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 return its zigzag level order traversal as: [ [3], [20,9], [15,7] ]

In [ ]:
class Solution(object):
    def zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        order = 1
        ans = []
        nodes = [root]
        while len(nodes) > 0:
            vals, temp = [], []
            for node in nodes:
                if node:
                    vals.append(node.val)
                    if order == 0:
                        temp = [node.left, node.right] + temp
                    else:
                        temp = [node.right, node.left] + temp
            if vals != []:
                ans.append(vals)
            nodes = temp
            order = (order+1)%2
        return ans

Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level). For example: Given binary tree [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 return its level order traversal as: [ [3], [9,20], [15,7] ]

In [ ]:
class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        ans = []
        nodes = [root]
        while len(nodes) > 0:
            vals, temp = [], []
            for node in nodes:
                if node:
                    vals.append(node.val)
                    temp.append(node.left)
                    temp.append(node.right)
            if vals != []:
                ans.append(vals)
            nodes = temp
        return ans

Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). For example, this binary tree [1,2,2,3,4,4,3] is symmetric: 1 / \ 2 2 / \ / \ 3 4 4 3 But the following [1,2,2,null,3,null,3] is not: 1 / \ 2 2 \ \ 3 3 Note: Bonus points if you could solve it both recursively and iteratively.

In [ ]:
class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if root == None:
            return True
        def helper(left, right):
            if left == None or right == None:
                return left == None and right == None
            if left.val != right.val:
                return False
            return helper(left.right, right.left) and helper(left.left, right.right)
        return helper(root.left, root.right)

Same Tree

Given two binary trees, write a function to check if they are equal or not. Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

In [ ]:
class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        if p == None:
            return q == None
        if q == None:
            return p == None
        if p.val != q.val:
            return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys greater than the node's key. Both the left and right subtrees must also be binary search trees. Example 1: 2 / \ 1 3 Binary tree [2,1,3], return true. Example 2: 1 / \ 2 3 Binary tree [1,2,3], return false.

In [ ]:
class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        self.lim = None
        def helper(node):
            if node:
                if helper(node.left):
                    if self.lim == None or self.lim < node.val:
                        self.lim = node.val
                        return helper(node.right)
                    else:
                        return False
                else:
                    return False
            else:
                return True
        return helper(root)

Unique Binary Search Trees II

Given an integer 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

In [ ]:
class Solution(object):
    def dfs(self, start, end):
        if start > end:
            return [None]
        ans = []
        for rootVal in xrange(start, end+1):
            leftTrees = self.dfs(start, rootVal-1)
            rightTrees = self.dfs(rootVal+1, end)
            for left in leftTrees:
                for right in rightTrees:
                    root = TreeNode(rootVal)
                    root.left = left
                    root.right = right
                    ans.append(root)
        return ans
                    
    def generateTrees(self, n):
        """
        :type n: int
        :rtype: List[TreeNode]
        """
        if n < 1:
            return []
        return self.dfs(1, n)

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

In [ ]:
class Solution(object):
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp, i = [1,1], 2
        while i <= n:
            count = 0
            for left in xrange(i):
                right = i-left-1
                count += (dp[left]*dp[right])
            dp.append(count)
            i += 1
        return dp[n]

Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes' values. For example: Given binary tree [1,null,2,3], 1 \ 2 / 3 return [1,3,2].

In [ ]:
class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        ans = []
        def helper(node):
            if node.left:
                helper(node.left)
            ans.append(node.val)
            if node.right:
                helper(node.right)
        if root:
            helper(root)
        return ans

Restore IP Addresses

Given a string containing only digits, restore it by returning all possible valid IP address combinations. For example: Given "25525511135", return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

In [ ]:
class Solution(object):
    def isValid(self, num):
        L = len(num)
        if L == 0 or L > 3:
            return False
        if L > 1 and num[0] == '0':
            return False
        if L == 3 and int(num) > 255:
            return False
        return True
        
    def restoreIpAddresses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        ips = []
        def helper(S, ip, level):
            if level == 4:
                if S == '':
                    ips.append('.'.join(ip))
                else:
                    return 
            i = 0
            while i < len(S) and i < 3:
                if self.isValid(S[:i+1]):
                    helper(S[i+1:], ip+[S[:i+1]], level+1)
                i += 1
        helper(s, [], 0)
        return ips

Add Binary

Given two binary strings, return their sum (also a binary string). For example, a = "11" b = "1" Return "100".

In [ ]:
class Solution(object):
    def addBinary(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: str
        """
        def helper(m, n, buf):
            if m == '0' and n == '0':
                if buf == '1':
                    ans, buf = '1', '0'
                else:
                    ans = '0'
            elif m == '1' and n == '1':
                if buf == '1':
                    ans = '1'
                else:
                    ans = '0'
                buf = '1'
            else:
                if buf == '1':
                    ans = '0'
                else:
                    ans, buf = '1', '0'
            return ans, buf
        buf, ans = '0', ''
        i, j = len(a)-1, len(b)-1
        while i >= 0 and j >= 0:
            temp, buf = helper(a[i], b[j], buf)
            ans = temp + ans
            i -= 1
            j -= 1
        while i >= 0:
            temp, buf = helper(a[i], '0', buf)
            ans = temp + ans
            i -= 1
        while j >= 0:
            temp, buf = helper(b[j], '0', buf)
            ans = temp + ans
            j -= 1
        if buf == '1':
            ans = buf + ans
        return ans

Reverse Linked List II

Reverse a linked list from position m to n. Do it in-place and in one-pass. For example: Given 1->2->3->4->5->NULL, m = 2 and n = 4, return 1->4->3->2->5->NULL. Note: Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.

In [ ]:
class Solution(object):
    def findNode(self, head, k):
        while k > 0:
            head = head.next
            k -= 1
        return head
    def reverse(self, start, k):
        last, now = start, start.next
        while k > 0:
            temp = now.next
            now.next = last
            last = now
            now = temp
            k -= 1
        return last, now
    def reverseBetween(self, head, m, n):
        """
        :type head: ListNode
        :type m: int
        :type n: int
        :rtype: ListNode
        """
        dummy = ListNode(0)
        dummy.next = head
        pivot = self.findNode(dummy, m-1)
        start = pivot.next
        last, now = self.reverse(start, n-m)
        start.next = now
        pivot.next = last
        return dummy.next

Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. Note: You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.

In [ ]:
class Solution(object):
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: void Do not return anything, modify nums1 in-place instead.
        """
        i, j, k = m-1, n-1, m+n-1
        while i >= 0 and j >= 0:
            if nums1[i] >= nums2[j]:
                nums1[k] = nums1[i]
                i -= 1
            else:
                nums1[k] = nums2[j]
                j -= 1
            k -= 1
        while j >= 0:
            nums1[k] = nums2[j]
            j -= 1
            k -= 1

Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given an encoded message containing digits, determine the total number of ways to decode it. For example, Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12). The number of ways decoding "12" is 2.

In [ ]:
class Solution(object):
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        if s == '' or s[0] == '0':
            return 0
        dp = [1,1]
        L = len(s)
        for i in xrange(1, L):
            n = int(s[i-1:i+1])
            count = 0
            if 9 < n < 27:
                count += dp[i-1]
            if s[i] != '0':
                count += dp[i]
            if count == 0:
                return 0
            else:
                dp.append(count)
        return dp[L]

Subsets II

Given a collection of integers that might contain duplicates, nums, return all possible subsets. Note: The solution set must not contain duplicate subsets. For example, If nums = [1,2,2], a solution is: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]

In [ ]:
class Solution(object):
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        pre = {}
        ans = []
        for n in nums:
            if n in pre:
                pre[n] += 1
            else:
                pre[n] = 1

        def helper(Keys, parents):
            if Keys == []:
                ans.append(parents)
            else:
                i = 0
                while i <= pre[Keys[0]]:
                    helper(Keys[1:], parents + [Keys[0]] * i)
                    i += 1
        helper(pre.keys(), [])
        return ans

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. For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

In [ ]:
class Solution(object):
    def grayCode(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        ans = [0]
        add = 1
        while n > 0:
            for num in ans[::-1]:
                ans.append(num+add)
            n -= 1
            add *= 2
        return ans

Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x. You should preserve the original relative order of the nodes in each of the two partitions. For example, Given 1->4->3->2->5->2 and x = 3, return 1->2->2->4->3->5.

In [ ]:
class Solution(object):
    def partition(self, head, x):
        """
        :type head: ListNode
        :type x: int
        :rtype: ListNode
        """
        if head is None:
            return head
        ahead, bhead = ListNode(0), ListNode(0)
        atail, btail = ahead, bhead
        while head:
            if head.val < x:
                atail.next = head
                atail = atail.next
            else:
                btail.next = head
                btail = btail.next
            head = head.next
        btail.next = None
        atail.next = bhead.next
        return ahead.next

Search in Rotated Sorted Array II

Follow up for "Search in Rotated Sorted Array": What if duplicates are allowed? Would this affect the run-time complexity? How and why? Write a function to determine if a given target is in the array.

In [ ]:
class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: bool
        """
        L = len(nums)
        left, right = 0, L-1
        while left <= right:
            mid = (left+right)/2
            if nums[mid] == target:
                return True
            elif nums[mid] > nums[left]:
                if nums[left] <= target and target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            elif nums[mid] < nums[left]:
                if nums[mid] < target and target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
            else:
                left += 1
        return False

Search in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). You are given a target value to search. If found in the array return its index, otherwise return -1. You may assume no duplicate exists in the array.

In [ ]:
class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        left, right = 0, len(nums)-1
        while left <= right:
            mid = (left+right)/2
            if nums[mid] == target:
                return mid
            elif nums[mid] >= nums[left]:
                if nums[left] <= target and target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                if nums[mid] < target and target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
        return -1

Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example, Given 1->2->3->3->4->4->5, return 1->2->5. Given 1->1->1->2->3, return 2->3.


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

class Solution(object):
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head == None:
            return head
        now = ListNode(0)
        new = now
        pos = head
        while pos:
            if pos.next and pos.val == pos.next.val:
                while pos.next and pos.val == pos.next.val:
                    pos = pos.next
            else:
                print pos.val
                now.next = pos
                now = now.next
            pos = pos.next
        now.next = None
        return new.next

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.

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

class Solution(object):
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head == None:
            return head
        last = head.val
        prev, pos = head, head.next
        while pos:
            if pos.val == last:
                prev.next = pos.next
            else:
                last = pos.val
                prev = pos
            pos = pos.next
        return head

Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

In [ ]:
class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        pre = {}
        def helper(N):
            if N == 0:
                return 1
            elif N < 0:
                return 0
            else:
                if N not in pre:
                    a, b = helper(N-1), helper(N-2)
                    pre[N] = a+b
                return pre[N]
        return helper(n)

Remove Duplicates from Sorted Array II

Follow up for "Remove Duplicates": What if duplicates are allowed at most twice? For example, Given sorted array nums = [1,1,1,2,2,3], Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn't matter what you leave beyond the new length.

In [ ]:
class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        counts = {}
        for n in nums:
            if n in counts:
                counts[n] += 1
            else:
                counts[n] = 1
        L = 0
        for n in sorted(counts.keys()):
            end = L + min(2, counts[n])
            while L < end:
                nums[L] = n
                L += 1
        return L

Regular Expression Matching

Implement regular expression matching with support for '.' and '*'. '.' Matches any single character. '*' Matches zero or more of the preceding element. The matching should cover the entire input string (not partial). The function prototype should be: bool isMatch(const char *s, const char *p) Some examples: isMatch("aa","a") → false isMatch("aa","aa") → true isMatch("aaa","aa") → false isMatch("aa", "a*") → true isMatch("aa", ".*") → true isMatch("ab", ".*") → true isMatch("aab", "c*a*b") → true

In [ ]:
class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        Ls, Lp = len(s), len(p)
        dp = [[False for _ in xrange(Lp+1)] for _ in xrange(Ls+1)]
        dp[0][0] = True
        for i in xrange(1, Lp+1):
            if p[i-1] == '*':
                dp[0][i] = dp[0][i-2]
        for j in xrange(1, Ls+1):
            for i in xrange(1, Lp+1):
                if p[i-1] == '*':
                    dp[j][i] = dp[j][i-2]
                    if not dp[j][i] and (p[i-2] == '.' or s[j-1] == p[i-2]):
                        dp[j][i] = dp[j-1][i]
                elif p[i-1] == '.' or s[j-1] == p[i-1]:
                    dp[j][i] = dp[j-1][i-1]
        return dp[-1][-1]
Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once. For example, Given board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] word = "ABCCED", -> returns true, word = "SEE", -> returns true, word = "ABCB", -> returns false.

In [ ]:
class Solution(object):
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        if word == '':
            return True
        m, n = len(board), len(board[0])
        if m == 0 or n == 0:
            return False
        visited = [[False for _ in xrange(n)] for _ in xrange(m)]
        
        def search(i, j, w):
            if w == '':
                return True
            if i < 0 or i >= n or j < 0 or j >= m:
                return False
            elif w[0] != board[j][i] or visited[j][i]:
                return False
            else:
                visited[j][i] = True
                if search(i+1, j, w[1:]) or search(i-1, j, w[1:]) or search(i, j+1, w[1:]) or search(i, j-1, w[1:]):
                    return True
                else:
                    visited[j][i] = False
                    return False
                
        for j in xrange(m):
            for i in xrange(n):
                if search(i, j, word):
                    return True
        return False

Subsets

Given a set of distinct integers, nums, return all possible subsets. Note: The solution set must not contain duplicate subsets. For example, If nums = [1,2,3], a solution is: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]

In [ ]:
class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        ans = []
        def helper(rest, parents):
            if rest == []:
                ans.append(parents)
            else:
                helper(rest[1:], parents)
                helper(rest[1:], parents+rest[:1])
        helper(nums, [])
        return ans

Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively. A rather straight forward solution is a two-pass algorithm using counting sort. First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's. Could you come up with an one-pass algorithm using only constant space?

In [ ]:
class Solution(object):
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        colors = {0: 0, 1: 0, 2: 0}
        for n in nums:
            colors[n] += 1
        i = 0
        for c in xrange(3):
            for _ in xrange(colors[c]):
                nums[i] = c
                i += 1

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.

In [ ]:
class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        m, n = len(matrix), len(matrix[0])
        if m == 0 or n == 0:
            return False

        def helper(nums, L):
            left, right = 0, L-1
            while right-left > 1 and nums[left] <= target and target <= nums[right]:
                mid = (left+right)/2
                if nums[mid] == target:
                    return mid
                elif nums[mid] > target:
                    right = mid
                else:
                    left = mid
            if nums[left] <= target and target < nums[right]:
                return left
            else:
                return right
        rows = [r[0] for r in matrix]
        row = helper(rows, m)
        col = helper(matrix[row], n)
        return matrix[row][col] == target

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. 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?

In [ ]:
class Solution(object):
    def setZeroes(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        firstRow, firstCol = False, False
        m, n = len(matrix), len(matrix[0])
        for i in xrange(n):
            if matrix[0][i] == 0:
                firstRow = True
                break
        for j in xrange(m):
            if matrix[j][0] == 0:
                firstCol = True
                break
        for j in xrange(1, m):
            for i in xrange(1, n):
                if matrix[j][i] == 0:
                    matrix[j][0], matrix[0][i] = 0, 0
        
        for i in xrange(1, n):
            if matrix[0][i] == 0:
                for j in xrange(1, m):
                    matrix[j][i] = 0
        for j in xrange(1, m):
            if matrix[j][0] == 0:
                for i in xrange(1, n):
                    matrix[j][i] = 0
        if firstRow:
            for i in xrange(n):
                matrix[0][i] = 0
        if firstCol:
            for j in xrange(m):
                matrix[j][0] = 0

Simplify Path

Given an absolute path for a file (Unix-style), simplify it. For example, path = "/home/", => "/home" path = "/a/./b/../../c/", => "/c" Corner Cases: Did you consider the case where path = "/../"? In this case, you should return "/". Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/". In this case, you should ignore redundant slashes and return "/home/foo".

In [ ]:
class Solution(object):
    def simplifyPath(self, path):
        """
        :type path: str
        :rtype: str
        """
        P = ['/']
        for f in path.split('/'):
            if f == '' or f == '.':
                continue
            elif f == '..':
                if P [-1] != '/':
                    P.pop()
            else:
                P.append('/'+f)
        if len(P) == 1:
            return '/'
        else:
            return ''.join(P[1:])

Sqrt(x)

Implement int sqrt(int x). Compute and return the square root of x.

In [ ]:
class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x <= 1:
            return x
        left = 1
        right = x
        mid = (left + right) / 2
        while mid > left:
            temp = mid * mid
            if temp == x:
                return mid
            elif temp > x:
                right = mid
            else:
                left = mid
            mid = (left + right) / 2
        return left

Merge K Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

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

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        def merge2Lists(L1, L2):
            ans = ListNode(0)
            pos = ans
            while L1 and L2:
                if L1.val > L2.val:
                    pos.next = L2
                    L2 = L2.next
                    pos = pos.next
                else:
                    pos.next = L1
                    L1 = L1.next
                    pos = pos.next
            if L1:
                pos.next = L1
            elif L2:
                pos.next = L2
            return ans.next
        if lists == []:
            return []
        while len(lists) > 1:
            L1, L2 = lists[:2]
            lists = lists[2:]
            lists.append(merge2Lists(L1,L2))
        return lists[0]

Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. Note: You can only move either down or right at any point in time.

In [ ]:
class Solution(object):
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        costs = grid
        for i in xrange(len(grid)):
            for j in xrange(len(grid[i])):
                if i == 0 and j == 0:
                    continue
                elif i == 0:
                    grid[i][j] += grid[i][j-1]
                elif j == 0:
                    grid[i][j] += grid[i-1][j]
                else:
                    grid[i][j] += min(grid[i][j-1], grid[i-1][j])
        return grid[-1][-1]

Unique Paths II

Follow up for "Unique Paths": Now consider if some obstacles are added to the grids. How many unique paths would there be? An obstacle and empty space is marked as 1 and 0 respectively in the grid. For example, There is one obstacle in the middle of a 3x3 grid as illustrated below. [ [0,0,0], [0,1,0], [0,0,0] ] The total number of unique paths is 2. Note: m and n will be at most 100.

In [ ]:
class Solution(object):
    def uniquePathsWithObstacles(self, obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        counts = obstacleGrid
        for i in xrange(len(obstacleGrid)):
            for j in xrange(len(obstacleGrid[i])):
                if obstacleGrid[i][j] == 1:
                    obstacleGrid[i][j] = 0
                elif i == 0 and j == 0:
                    obstacleGrid[i][j] = 1
                elif i == 0:
                    obstacleGrid[i][j] = obstacleGrid[i][j-1]
                elif j == 0:
                    obstacleGrid[i][j] = obstacleGrid[i-1][j]
                else:
                    obstacleGrid[i][j] = obstacleGrid[i][j-1] + obstacleGrid[i-1][j]
        return obstacleGrid[-1][-1]

Plus One

Given a non-negative number represented as an array of digits, plus one to the number. The digits are stored such that the most significant digit is at the head of the list.

In [ ]:
class Solution(object):
    def plusOne(self, digits):
        """
        :type digits: List[int]
        :rtype: List[int]
        """
        carry = 1
        i = len(digits) - 1
        while i >= 0 and carry > 0:
            carry += digits[i]
            digits[i] = carry % 10
            carry = carry / 10
            i -= 1
        if carry > 0:
            return [carry] + digits
        return digits

Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). Example 1: nums1 = [1, 3] nums2 = [2] The median is 2.0 Example 2: nums1 = [1, 2] nums2 = [3, 4] The median is (2 + 3)/2 = 2.5

In [ ]:
class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        
        def findKth(k, A, m, B, n):
            if m <= 0:
                return B[k-1]
            if n == 0:
                return A[k-1]
            if k == 1:
                return min(A[0], B[0])
            a, b = m/2, n/2
            pivot = a + b + 1
            if A[a] >= B[b]:
                if pivot >= k:
                    return findKth(k, A[:a], a, B, n)
                else:
                    return findKth(k-b-1, A, m, B[b+1:], n-b-1)
            else:
                if pivot >= k:
                    return findKth(k, A, m, B[:b], b)
                else:
                    return findKth(k-a-1, A[a+1:], m-a-1, B, n)
        m, n = len(nums1), len(nums2)
        S = m+n
        if S % 2 == 0:
            return 0.5 * (findKth(S/2, nums1, m, nums2, n) + findKth(S/2+1, nums1, m, nums2, n))
        else:
            
            return findKth(S/2+1, nums1, m, nums2, n)

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?

In [ ]:
class Solution(object):
    def uniquePaths(self, M, N):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        pre = {}
        def helper(m, n):
            if m == 1 or n == 1:
                return 1
            a, b = (m, n) if m > n else (n, m)
            if (a, b) in pre:
                return pre[(a,b)]
            else:
                ans = helper(m-1, n) + helper(m, n-1)
                pre[(a,b)] = ans
                return ans
        return helper(M, N)

Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative. For example: Given 1->2->3->4->5->NULL and k = 2, return 4->5->1->2->3->NULL.

In [ ]:
class Solution(object):
    def rotateRight(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if head == None:
            return head
        path = {}
        L = 0
        while head:
            path[L] = head
            L += 1
            head = head.next
        k = k % L
        if k == 0:
            return path[0]
        ans = path[L-k]
        path[L-k-1].next = None
        if k == 1:
            ans.next = path[0]
        else:
            path[L-1].next = path[0]
        return ans

Permutation Sequence

The set [1,2,3,…,n] contains a total of n! unique permutations. By listing and labeling all of the permutations in order, We get the following sequence (ie, for n = 3): "123" "132" "213" "231" "312" "321" Given n and k, return the kth permutation sequence. Note: Given n will be between 1 and 9 inclusive.

In [ ]:
class Solution(object):
    def getPermutation(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        nums = range(1,n+1)
        fac = [1]
        for i in xrange(2, n):
            fac.append(fac[-1]*i)
        ans = []
        for p in fac[::-1]:
            remainder = k % p
            carry = k / p
            if remainder == 0:
                carry -= 1
            ans.append(nums[carry])
            nums.remove(nums[carry])
            k = remainder
        ans += nums
        return ''.join(map(str, ans))

Spiral Matrix II

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order. For example, Given n = 3, You should return the following matrix: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]

In [ ]:
class Solution(object):
    def generateMatrix(self, n):
        """
        :type n: int
        :rtype: List[List[int]]
        """
        matrix = []
        if n == 0:
            return matrix
        for _ in xrange(n):
            matrix.append([0]*n)
        left = 0
        right = n-1
        top = 0
        bottom = n-1
        pos = 1
        while left < right and top < bottom:
            for i in xrange(right-left+1):
                matrix[top][left+i] = pos
                pos += 1
            top += 1
            for j in xrange(bottom-top+1):
                matrix[top+j][right] = pos
                pos += 1
            right -= 1
            for i in xrange(right-left+1):
                matrix[bottom][right-i] = pos
                pos += 1
            bottom -= 1
            for j in xrange(bottom-top+1):
                matrix[bottom-j][left] = pos
                pos += 1
            left += 1
        if left == right and top == bottom:
            matrix[top][left] = pos
        return matrix

Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index. For example: A = [2,3,1,1,4], return true. A = [3,2,1,0,4], return false.

In [ ]:
class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        pos = 0
        ans = 0
        for jump in nums[:-1]:
            ans = max(ans, pos+jump)
            if (ans <= pos):
                return False
            pos += 1
        return True

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].

In [ ]:
class Solution(object):
    def spiralOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        m = len(matrix)
        if m == 0:
            return matrix
        n = len(matrix[0])
        left = 0
        right = n-1
        top = 0
        bottom = m-1
        ans = []
        while left < right and top < bottom:
            for i in xrange(left, right+1):
                ans.append(matrix[top][i])
            top += 1
            for j in xrange(top, bottom+1):
                ans.append(matrix[j][right])
            right -= 1
            for i in xrange(right, left-1, -1):
                ans.append(matrix[bottom][i])
            bottom -= 1
            for j in xrange(bottom, top-1, -1):
                ans.append(matrix[j][left])
            left += 1
        if left <= right and top == bottom:
            ans += matrix[top][left:right+1]
        if top < bottom and left == right:
            for j in xrange(top, bottom+1):
                ans.append(matrix[j][right])
        return ans

Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum. For example, given the array [-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,-1,2,1] has the largest sum = 6.

In [ ]:
class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        L = len(nums)
        if L == 0:
            return None
        ans = nums[0]
        S = 0
        for i in xrange(L):
            S += nums[i]
            if S > ans:
                ans = S
            if S < 0:
                S = 0
        return ans

Pow(x, n)

Implement pow(x, n).

In [ ]:
class Solution(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        if n == 0:
            return 1.0
        elif n == 1:
            return x
        if n < 0:
            x = 1.0 / x
            n = -n
        if n % 2 == 1:
            return x * self.myPow(x, n-1)
        else:
            return self.myPow(x*x, n/2)

Group Anagrams

Given an array of strings, group anagrams together. For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"], Return: [ ["ate", "eat","tea"], ["nat","tan"], ["bat"] ] Note: All inputs will be in lower-case.

In [ ]:
class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        pre = {}
        for word in strs:
            W = ''.join(sorted(word))
            if W in pre:
                pre[W].append(word)
            else:
                pre[W] = [word]
        return pre.values()

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?

In [ ]:
class Solution(object):
    def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)
        left = 0
        right = n-1
        top = 0
        bottom = n-1

        while left < right and top < bottom:
            temp1 = matrix[top][left:right+1]
            temp2 = temp1[:]
            L = right-left+1
            for j in xrange(L):
                temp1[j] = matrix[top+j][right]
                matrix[top+j][right] = temp2[j]
            temp2 = temp1[:]
            for i in xrange(1,L):
                temp1[i] = matrix[bottom][right-i]
                matrix[bottom][right-i] = temp2[i]
            temp2 = temp1[:]
            for j in xrange(1,L):
                temp1[j] = matrix[bottom-j][left]
                matrix[bottom-j][left] = temp2[j]
            temp2 = temp1[:]
            for i in xrange(1,L-1):
                temp1[i] = matrix[top][left+i]
                matrix[top][left+i] = temp2[i]
            left += 1
            right -= 1
            top += 1
            bottom -= 1

Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations. For example, [1,1,2] have the following unique permutations: [ [1,1,2], [1,2,1], [2,1,1] ]

In [ ]:
class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        ans = []
        nums.sort()
        def helper(Nums, parents=[]):
            L = len(Nums)
            if L == 0:
                ans.append(parents)
            else:
                for i in xrange(L):
                    if i == 0 or Nums[i] != Nums[i-1]:
                        helper(Nums[:i]+Nums[i+1:], parents+[Nums[i]])
        helper(nums)
        return ans

Permutations

Given a collection of distinct numbers, return all possible permutations. For example, [1,2,3] have the following permutations: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

In [ ]:
class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        ans = []
        def helper(Nums, parents=[]):
            L = len(Nums)
            if L == 0:
                ans.append(parents)
            else:
                for i in xrange(L):
                    helper(Nums[:i]+Nums[i+1:], parents+[Nums[i]])
        helper(nums)
        return ans

Multiply Strings

Given two numbers represented as strings, return multiplication of the numbers as a string. Note: The numbers can be arbitrarily large and are non-negative. Converting the input string to integer is NOT allowed. You should NOT use internal library such as BigInteger.

In [ ]:
class Solution(object):
    def multiply(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        num1 = num1[::-1]
        num2 = num2[::-1]
        L1 = len(num1)
        L2 = len(num2)
        pre = {}
        ans = ''
        for i in xrange(L1):
            for j in xrange(L2):
                S = int(num1[i]) * int(num2[j])
                if i+j in pre:
                    pre[i+j] += S
                else:
                    pre[i+j] = S
        carry = 0
        for i in xrange(L1+L2-1):
            digit = (carry+pre[i]) % 10
            carry = (carry+pre[i]) / 10
            ans = str(digit) + ans
        if carry > 0:
            ans = str(carry) + ans
        else:
            while ans[0] == '0' and len(ans) > 1:
                ans = ans[1:]
        return ans

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. 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] ]

In [ ]:
class Solution(object):
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        candidates.sort()
        L = len(candidates)
        ans = []
        used = [0] * len(candidates)
        def dfs(now, index, temp):
            if now == target:
                ans.append(temp[:])
                return
            else:
                for i in xrange(index, L):
                    if candidates[i] + now <= target and (i == 0 or candidates[i] != candidates[i-1] or used[i-1] == 1):
                        temp.append(candidates[i])
                        used[i] = 1
                        dfs(now + candidates[i], i+1, temp) 
                        used[i] = 0
                        temp.pop()
        dfs(0, 0, [])
        return ans

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. 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] ]

In [ ]:
class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        candidates.sort()
        def helper(nums, T):
            L = len(nums)
            ans = []
            if L == 0 or T <= 0:
                return ans
            index = L-1
            while index >= 0:
                mul = 1
                S = nums[index] * mul
                while S < T:
                    combs = helper(nums[:index], T - S)
                    for comb in combs:
                        ans.append(comb + [nums[index]] * mul)
                    mul += 1
                    S = nums[index] * mul
                if S == T:
                    ans.append([nums[index]] * mul)
                index -= 1
            return ans
        return helper(candidates, target)

Count and Say

The count-and-say sequence is the sequence of integers beginning as follows: 1, 11, 21, 1211, 111221, ... 1 is read off as "one 1" or 11. 11 is read off as "two 1s" or 21. 21 is read off as "one 2, then one 1" or 1211. Given an integer n, generate the nth sequence. Note: The sequence of integers will be represented as a string.

In [ ]:
class Solution(object):
    def countAndSay(self, n):
        """
        :type n: int
        :rtype: str
        """
        ans = '1'
        while n > 1:
            strs = ''
            i = 0
            while i < len(ans):
                j = i + 1
                temp = ans[i]
                count = 1
                while temp == ans[j:j+1]:
                    count += 1
                    j += 1
                i = j
                strs += '{}{}'.format(count,temp)
            n -= 1
            ans = strs
        return ans

Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array. Here are few examples. [1,3,5,6], 5 → 2 [1,3,5,6], 2 → 1 [1,3,5,6], 7 → 4 [1,3,5,6], 0 → 0

In [ ]:
class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        L = len(nums)
        start = 0
        end = L
        pivot = (start+end)/2
        while start < end:
            if nums[pivot] == target:
                return pivot
            elif nums[pivot] > target:
                end = pivot
            else:
                start = pivot+1
            pivot = (start + end)/2
        return pivot

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 '.'. Note: A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

In [ ]:
class Solution(object):
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        def valid(nums):
            pre = {}
            for n in nums:
                if n == ".":
                    continue
                if n in pre:
                    return False
                else:
                    pre[n] = 1
            return True
            
        def smallBoard(i, j):
            grid = []
            for y in xrange(j,j+3):
                for x in xrange(i,i+3):
                    grid.append(board[y][x])
            return grid
        
        for row in board:
            if not valid(row):
                return False
        
        for col in xrange(9):
            nums = [board[row][col] for row in range(9)]
            if not valid(nums):
                return False
        
        for j in xrange(0,8,3):
            for i in xrange(0,8,3):
                if not valid(smallBoard(i, j)):
                    return False
        return True

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].

In [ ]:
class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        
        def helper(Nums):
            L = len(Nums)
            if L == 0:
                return [-1,-1]
            elif L == 1:
                if Nums[0] == target:
                    return [0,0]
                else:
                    return [-1,-1]
            pivot = L/2
            if Nums[pivot] == target:
                ans = [pivot, pivot]
                left = helper(Nums[:pivot])
                if left[0] != -1:
                    ans[0] = left[0]
                right = helper(Nums[pivot+1:])
                if right[1] != -1:
                    ans[1] += (right[1]+1)
                return ans
            elif Nums[pivot] < target:
                ans = helper(Nums[pivot+1:])
                if ans != [-1,-1]:
                    return [x+pivot+1 for x in ans]
                return ans
            else:
                return helper(Nums[:pivot])
        return helper(nums)

Implement strStr()

Implement strStr(). Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

In [ ]:
class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        L_needle = len(needle)
        L_haystack = len(haystack)
        i = 0
        while i+L_needle <= L_haystack:
            if haystack[i:i+L_needle] == needle:
                return i
            i += 1
        return -1

Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order). The replacement must be in-place, do not allocate extra memory. Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column. 1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1

In [ ]:
class Solution(object):
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        L = len(nums)
        i = L-2
        while i >= 0:
            if nums[i+1] > nums[i]:
                break
            i -= 1
        if i < 0:
            nums.sort()
            return
        pivot, j = i+1, i+2
        while j < L:
            if nums[j] > nums[i] and nums[j] < nums[pivot]:
                pivot = j
            j += 1
        nums[i], nums[pivot] = nums[pivot], nums[i]
        for end in xrange(L-1,i,-1):
            for start in xrange(i+1, end):
                if nums[start] > nums[start+1]:
                    nums[start], nums[start+1] = nums[start+1], nums[start]

Divide Two Integers

Divide two integers without using multiplication, division and mod operator. If it is overflow, return MAX_INT.

In [ ]:
class Solution(object):
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        if divisor == 0:
            return -1
        ans, shift = 0, 31
        neg = (dividend > 0 and divisor < 0) or (dividend < 0 and divisor > 0)
        a, b = abs(dividend), abs(divisor)
        while shift >= 0:
            if a >= b << shift:
                a -= b << shift
                ans += 1 << shift
            shift -= 1
        if neg:
            ans = -ans
        if ans > 2147483647:
            return 2147483647
        elif ans < -2147483648:
            return -2147483648
        
        return ans

Remove Element

Given an array and a value, remove all instances of that value in place and return the new length. Do not allocate extra space for another array, you must do this in place with constant memory. The order of elements can be changed. It doesn't matter what you leave beyond the new length.

In [ ]:
class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        for i in xrange(len(nums)-1, -1, -1):
            if nums[i] == val:
                del nums[i]
        return len(nums)

Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this in place with constant memory. For example, Given input array nums = [1,1,2], Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.

In [ ]:
class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        left = 0
        L = len(nums)
        while left < L:
            right = left + 1
            while right < L and nums[left] == nums[right]:
                right += 1
            del nums[left+1:right]
            left += 1
            L = len(nums)
        return len(nums)

Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head. For example, Given 1->2->3->4, you should return the list as 2->1->4->3. Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

In [ ]:
class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        def helper(node):
            if node and node.next:
                temp = node.next
                node.next = helper(node.next.next)
                temp.next = node
                return temp
            else:
                return node
        return helper(head)

Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is: [ "((()))", "(()())", "(())()", "()(())", "()()()" ]

In [ ]:
class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        def helper(l, r, item, res):
            if r < l:
                return
            if r == 0 and l == 0:
                res.append(item)
            if l > 0:
                helper(l-1, r, item+"(", res)
            if r > 0:
                helper(l, r-1, item+")", res)
        
        res = []
        helper(n,n,"", res)
        return res

Letter Combinations of a Phone Number

Given a digit string, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below.

In [ ]:
class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        letter = {"0": " ", "1": "*", "2": "abc",
                  "3": "def", "4": "ghi", "5": "jkl",
                  "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
        
        def helper(D):
            ans = []
            if D == "":
                return ans
            elif len(D) == 1:
                return list(letter[D])
            else:
                combs = helper(D[1:])
                for c in letter[D[0]]:
                    if combs == []:
                        ans.append(c)
                    else:
                        for comb in combs:
                            ans.append(c+comb)
            return ans
        return helper(digits)

3Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution. For example, given array S = {-1 2 1 -4}, and target = 1. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

In [ ]:
class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        L = len(nums)
        ans = 0
        diff = None
        if L < 3:
            return ans
        # Sorting the array
        nums.sort()
        last = None
        for i in range(L-2):
            # Ignore those duplicated computation
            if last == nums[i]:
                continue
            new_target = target - nums[i]
            left = i+1
            right = L-1
            while left < right:
                S = nums[left] + nums[right]
                if S == new_target:
                    return target
                else:
                    # Update the difference
                    temp = abs(S - new_target)
                    if diff == None or temp < diff:
                        diff = temp
                        ans = S + nums[i]
                    if S < new_target:
                        left += 1
                        while left < right and nums[left] == nums[left-1]:
                            left += 1
                    else:
                        right -= 1
                        while left < right and nums[right] == nums[right+1]:
                            right -= 1
        return ans

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.

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

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        ans = ListNode(0)
        pointer = ans
        while l1 and l2:
            if l2.val > l1.val:
                pointer.next = l1
                l1 = l1.next
            else:
                pointer.next = l2
                l2 = l2.next
            pointer = pointer.next
        while l1:
            pointer.next = l1
            l1 = l1.next
            pointer = pointer.next
        while l2:
            pointer.next = l2
            l2 = l2.next
            pointer = pointer.next
        return ans.next

Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

In [ ]:
class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        ans = ""
        A = {"}": "{", ")": "(", "]": "["}
        for c in s:
            if c in "({[":
                ans += c
            else:
                if len(ans) > 0 and ans[-1] == A[c]:
                    ans = ans[:-1]
                else:
                    return False
        return ans == ""

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.

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

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        paths = {}
        index = 0
        node = head
        while node:
            paths[index] = node
            index += 1
            node = node.next
        if index - n == 0:
            if 1 in paths:
                return paths[1]
            else:
                return []
        else:
            node = paths[index-n-1]
            if index-n+1 in paths:
                node.next = paths[index-n+1]
            else:
                node.next = None
            return head

4Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target. Note: The solution set must not contain duplicate quadruplets. For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0. A solution set is: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]

In [ ]:
class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        result = []
        L = len(nums)
        if L < 4:
            return result
            
        nums.sort()
        last1 = None
        for i in range(L-3):
            if nums[i] == last1:
                continue
            last2 = None
            for j in range(i+1, L-2):
                if nums[j] == last2:
                    continue
                new_target = target - nums[i] - nums[j]
                left = j+1
                right = L-1
                while left < right:
                    if nums[left] + nums[right] == new_target:
                        result.append([nums[i], nums[j], nums[left], nums[right]])
                        left += 1
                        right -= 1
                        while left < right and nums[left] == nums[left-1]:
                            left += 1
                        while left < right and nums[right] == nums[right+1]:
                            right -= 1
                    elif nums[left] + nums[right] < new_target:
                        left += 1
                    else:
                        right -= 1
                last2 = nums[j]
            last1 = nums[i]
        return result

3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Note: The solution set must not contain duplicate triplets. For example, given array S = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]

In [ ]:
class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        L = len(nums)
        result = []
        if L < 3:
            return result
        nums.sort()
        last = None
        for i in range(L-2):
            if nums[i] == last:
                continue
            target = -1 * nums[i]
            left = i + 1
            right = L - 1
            while left < right:
                if nums[left] + nums[right] == target:
                    result.append([nums[i], nums[left], nums[right]])
                    left += 1
                    right -= 1
                    while left < right and nums[left] == nums[left-1]:
                        left += 1
                    while left < right and nums[right] == nums[right+1]:
                        right -= 1
                elif nums[left] + nums[right] < target:
                    left += 1
                else:
                    right -= 1
            last = nums[i]
        return result

Longest Common Prefix

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

In [ ]:
class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if len(strs) < 1:
            return ''
            
        def prefix(s1, s2):
            L1 = len(s1)
            L2 = len(s2)
            if L1 > L2:
                s1, s2 = s2, s1
                L1, L2 = L2, L1
            
            while s1 != s2[:L1]:
                s1 = s1[:-1]
                L1 -= 1
            return s1
        
        ans = strs[0]
        for s in strs[1:]:
            ans = prefix(ans, s)
        return ans

Roman to Integer

Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

In [ ]:
class Solution(object):
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        if s == '':
            return 0
            
        MAP = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
        result = MAP[s[-1]]
        last = s[-1]
        for c in s[-2::-1]:
            if MAP[c] >= MAP[last]:
                result += MAP[c]
            else:
                result -= MAP[c]
            last = c
        return result

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.

In [ ]:
class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        l = 0
        r = len(height) - 1
        ans = 0
        while(l < r):
            if height[l] > height[r]:
                temp = (r -l) * height[r]
                r -= 1
            else:
                temp = (r - l) * height[l]
                l += 1
            if temp > ans:
                ans = temp
        return ans

Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

In [ ]:
class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if s == '':
            return s
        L = len(s)
        def expand(c1, c2):
            while(c1 >= 0 and c2 <= L-1 and s[c1] == s[c2]):
                c1 -= 1
                c2 += 1
            return s[c1+1:c2]
        maxL = 1
        ans = s[0]
        for i in range(L):
            temp = expand(i, i)
            if len(temp) > maxL:
                maxL = len(temp)
                ans = temp
            temp = expand(i, i+1)
            if len(temp) > maxL:
                maxL = len(temp)
                ans = temp
        return ans

Palindrome Number

Determine whether an integer is a palindrome. Do this without extra space. Could negative integers be palindromes? (ie, -1) If you are thinking of converting the integer to string, note the restriction of using extra space. You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?

In [ ]:
class Solution(object):
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """
        if x < 0:
            return False
        div = 1
        while(x/div >= 10):
            div *= 10
        while(x > 0):
            l = x/div
            r = x%10
            if l != r:
                return False
            x = x%div/10
            div /= 100
        return True

String to Integer (atoi)

Implement atoi to convert a string to an integer. The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value. The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function. If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed. If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

In [ ]:
class Solution(object):
    def myAtoi(self, s):
        """
        :type str: s
        :rtype: int
        """
        def clean(s):
            t = ''
            if s:
                s = s.strip()
                if s[0] in '-+' or s[0].isdigit():
                    t += s[0]
                    for c in s[1:]:
                        if c.isdigit():
                            t += c
                        else:
                            return t
            return t
            
        result = 0
        sign = 1
        s = clean(s)
        if s:
            if s[0] == '-':
                sign = -1
                s = s[1:]
            s = s[::-1]
            for i in range(len(s)):
                if s[i].isdigit():
                    result += int(s[i]) * (10**i)
                else:
                    break
            if result > 2147483647 and sign == 1:
                result = 2147483647
            elif result > 2147483648 and sign == -1:
                result = 2147483648
        return sign * result

Reverse Integer

Reverse digits of an integer. Example1: x = 123, return 321 Example2: x = -123, return -321 If the integer's last digit is 0, what should the output be? ie, cases such as 10, 100. Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases? For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

In [ ]:
class Solution(object):
    def reverse(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x >= 0:
            sign = 1
        else:
            sign = -1
        result = int(str(abs(x))[::-1])
        if result > 2147483647:
            return 0
        else:
            return sign * result

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. Examples: Given "abcabcbb", the answer is "abc", which the length is 3. Given "bbbbb", the answer is "b", with the length of 1. Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

In [ ]:
class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        ans, start, end = 0, 0, 0
        counts = {}
        for c in s:
            end += 1
            counts[c] = counts.get(c, 0) + 1
            while counts[c] > 1:
                counts[s[start]] -= 1
                start += 1
            ans = max(ans, end - start)
        return ans

ZigZag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility) P A H N A P L S I I G Y I R And then read line by line: "PAHNAPLSIIGYIR" Write the code that will take a string and make this conversion given a number of rows: string convert(string text, int nRows) convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

In [ ]:
class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        if numRows <= 1:
            return s
        n = len(s)
        ans = ''
        window = 2 * numRows - 2
        for i in range(numRows):
            flag = i > 0 and i < numRows-1
            j = 0
            index = i + window * j
            while index < n:
                ans += s[index]
                if flag and index + window - 2*i<n:
                    ans += s[index + window - 2*i]
                j += 1
                index = i + window * j
        return ans

Add Two Numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8

In [ ]:
class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if l1 == None: return l2
        if l2 == None: return l1
        buffer = 0
        ans = ListNode(0)
        pos = ans
        while l1 and l2:
            n1 = l1.val
            n2 = l2.val
            val = buffer + n1 + n2
            buffer = val / 10
            val = val % 10
            pos.next = ListNode(val)
            pos = pos.next
            l1 = l1.next
            l2 = l2.next
        l3 = None
        if l1:
            l3 = l1
        elif l2:
            l3 = l2
        while l3:
            n3 = l3.val
            val = buffer + n3
            buffer = val / 10
            val = val % 10
            pos.next = ListNode(val)
            pos = pos.next
            l3 = l3.next
        if buffer > 0:
            pos.next = ListNode(buffer)
        return ans.next

Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution. Example: Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

In [ ]:
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        L = len(nums)
        Nums = {}
        for i in range(L):
            n = target-nums[i]
            if n in Nums:
                return [Nums[n], i]
            else:
                Nums[nums[i]] = i

Single Number II


In [ ]:
Given an array of integers, every element appears twice except for one. Find that single one.

Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

In [ ]:
class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ones = 0
        twos = 0
        for n in nums:
            twos |= ones&n
            ones ^= n
            threes = twos & ones
            ones &= ~threes
            twos &= ~threes
        return ones

Single Number

Given an array of integers, every element appears twice except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

In [ ]:
class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        result = 0
        for n in nums:
            result ^= n
        return result

Length of Last Word

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string. If the last word does not exist, return 0. Note: A word is defined as a character sequence consists of non-space characters only. For example, Given s = "Hello World", return 5.

In [ ]:
class Solution(object):
    def lengthOfLastWord(self, s):
        """
        :type s: str
        :rtype: int
        """
        count = 0
        for c in s.strip()[::-1]:
            if c.isalpha():
                count += 1
            else:
                break
        return count

Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n. For example, If n = 4 and k = 2, a solution is: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]

In [ ]:
class Solution(object):
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        result = []
        def helper(start=1, end=n-k+1, parent=[], level=k):
            last = (level == 1)
            for i in range(start, end+1):
                if last:
                    result.append(parent+[i])
                else:
                    helper(i+1, end+1, parent+[i], level-1)
        helper()
        return result

Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number. An example is the root-to-leaf path 1->2->3 which represents the number 123. Find the total sum of all root-to-leaf numbers. For example, 1 / \ 2 3 The root-to-leaf path 1->2 represents the number 12. The root-to-leaf path 1->3 represents the number 13. Return the sum = 12 + 13 = 25.

In [ ]:
class Solution(object):
    def findPaths(self, root):
        paths = []
        def helper(node, path=''):
            if node:
                path += str(node.val)
                if node.left == None and node.right == None:  
                    paths.append(path)
                else:
                    if node.left:
                        helper(node.left, path)
                    if node.right:
                        helper(node.right, path)
        helper(root)
        return paths
    def sumNumbers(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        result = 0
        for path in self.findPaths(root):
            result += int(path)
        return result

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.

In [ ]:
class Solution(object):
    def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root == None:
            return 0
        elif root.left:
            if root.right:
                return min(self.minDepth(root.left), self.minDepth(root.right))+1
            else:
                return self.minDepth(root.left)+1
        elif root.right:
            return self.minDepth(root.right)+1
        else:
            return 1