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):
"""
:type val: int
:rtype: ListNode
"""
dummy = ListNode(0)
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):
"""
:rtype: ListNode
"""
return None

while tailA.next:
La += 1
tailA = tailA.next

while tailB.next:
Lb += 1
tailB = tailB.next

if tailA != tailB:
return None

if La > Lb:
for _ in xrange(La-Lb):
else:
for _ in xrange(Lb-La):

``````

## 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):
"""
"""
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
for i in xrange(1,L):
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

``````

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):
"""
:rtype: bool
"""
return False
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
for sell in prices[1:]:
if sell - buy > profit:
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):
"""
:rtype: TreeNode
"""
while pos:
n += 1
pos = pos.next
def buildTree(start, end):
if start > end:
return None
mid = (start+end)/2
left = buildTree(start, mid-1)
root.left = left
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

``````

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

"""
: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

``````

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

In [ ]:

class Solution(object):
"""
: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 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):
while k > 0:
k -= 1
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
"""
:type m: int
:type n: int
:rtype: ListNode
"""
dummy = ListNode(0)
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]
while n > 0:
for num in ans[::-1]:
n -= 1
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):
"""
:type x: int
:rtype: ListNode
"""
atail = atail.next
else:
btail = btail.next
btail.next = None

``````

## 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 [ ]:

# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
"""
:rtype: ListNode
"""
now = ListNode(0)
new = now
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 [ ]:

# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
"""
:rtype: ListNode
"""
while pos:
if pos.val == last:
prev.next = pos.next
else:
last = pos.val
prev = pos
pos = pos.next

``````

## 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 [ ]:

# 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):
"""
:type k: int
:rtype: ListNode
"""
path = {}
L = 0
L += 1
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):
"""
: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

``````

## 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 [ ]:

# 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 [ ]:

# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
"""
:type n: int
:rtype: ListNode
"""
paths = {}
index = 0
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

``````

## 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

``````

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):
"""
: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

``````