class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        d = {}
        for i in nums:
            if i in d:
                return i
            else:
                d[i] = 1

class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        low = 0
        high = len(nums) - 1
        mid = (high + low) / 2
        while high - low > 1:
            count = 0
            for x in nums:
                if mid < x <= high:
                    count += 1
            if count > high - mid:
                low = mid
            else:
                high = mid
            mid = (high + low) / 2
        return high

class Solution(object):
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return (set([x for x in xrange(len(nums) + 1)]) - set(nums)).pop()

class Solution(object):
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        return n * (n+1) / 2 - sum(nums)

import heapq
class Solution(object):
    def kthSmallest(self, matrix, k):
        """
        :type matrix: List[List[int]]
        :type k: int
        :rtype: int
        """
        return list(heapq.merge(*matrix))[k-1]
        
        
In [11]: heapq.merge?
Signature: heapq.merge(*iterables)
Docstring:
Merge multiple sorted inputs into a single sorted output.
Similar to sorted(itertools.chain(*iterables)) but returns a generator,
does not pull the data into memory all at once, and assumes that each of
the input streams is already sorted (smallest to largest).
>>> list(merge([1,3,5,7], [0,2,4,8], [5,10,15,20], [], [25]))
[0, 1, 2, 3, 4, 5, 5, 7, 8, 10, 15, 20, 25]

In [104]: s = Solution(); t = s.kthSmallest([[1,5,9],[10,11,13],[12,13,15]], 8)
In [105]: print t
13

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        if not nums:
            return None
        i = len(nums) / 2
        node = TreeNode(nums[i])
        node.left = self.sortedArrayToBST(nums[:i])
        node.right = self.sortedArrayToBST(nums[i+1:])
        return node

Given the sorted array: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
      0
     / \
   -3   9
   /   /
 -10  5
In [1]: class TreeNode(object):
   ...:     def __init__(self, x):
   ...:         self.val = x
   ...:         self.left = None
   ...:         self.right = None
   ...:
In [42]: s = Solution(); t = s.sortedArrayToBST([-10,-3,0,5,9])

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        def helper(left, right):
            if left > right:
                return None
            idx = (left + right) / 2
            node = TreeNode(nums[idx])
            node.left = helper(left, idx - 1)
            node.right = helper(idx + 1, right)
            return node
        return helper(0, len(nums) - 1)

Given the sorted array: [-10,-3,0,5,9],
One possible answer is: [0,-10,5,null,-3,null,9]
      0
     / \
   -10   5
      \   \
      -3    9
In [1]: class TreeNode(object):
   ...:     def __init__(self, x):
   ...:         self.val = x
   ...:         self.left = None
   ...:         self.right = None
   ...:
In [58]: s = Solution(); t = s.sortedArrayToBST([-10,-3,0,5,9])

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        ret = []
        stack = []
        while True:
            while root:
                stack.append(root)
                root = root.left
            if not stack:
                return ret[k - 1]
            node = stack.pop()
            ret.append(node.val)
            root = node.right

Input: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
Output: 1
In [1]: class TreeNode(object):
   ...:     def __init__(self, x):
   ...:         self.val = x
   ...:         self.left = None
   ...:         self.right = None
   ...:
In [2]: one = TreeNode(1)
In [3]: two = TreeNode(2)
In [4]: one.right = two
In [5]: four = TreeNode(4)
In [6]: three = TreeNode(3)
In [7]: three.left = one
In [8]: three.right = four