Editorial problems.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 32. Longest Valid Parentheses"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.\n",
    "\n",
    "For \"(()\", the longest valid parentheses substring is \"()\", which has length = 2.\n",
    "\n",
    "Another example is \")()())\", where the longest valid parentheses substring is \"()()\", which has length = 4."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: The idea is to use a stack to store \"(\". If a \")\" is encountered, the possible cases are as follows:\n",
    "\n",
    "1. There is still \"(\" in the stack: we pop \"(\" and length+=2\n",
    "2. stack is empty: we reset length=0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def longestValidParentheses(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        maximum_length=0\n",
    "        length=0\n",
    "        stack=[]\n",
    "        for e in s:\n",
    "            if e=='(':\n",
    "                stack.append(e)\n",
    "            elif stack==[]:\n",
    "                length=0\n",
    "            else:\n",
    "                stack.pop()\n",
    "                length+=2\n",
    "                maximum_length=max(maximum_length,length)\n",
    "                \n",
    "        return maximum_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 84,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.longestValidParentheses(')))()())(((())))')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above solution is wrong on the testcase \"()(()\"."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Stack solution**: https://leetcode.com/articles/longest-valid-parentheses/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 128,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def longestValidParentheses(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        maximum_length=0\n",
    "        length=0\n",
    "        stack=[-1]\n",
    "        n=len(s)\n",
    "        for i in xrange(n):\n",
    "            if s[i]=='(':\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                stack.pop()\n",
    "                if stack==[]:\n",
    "                    stack.append(i)\n",
    "                else:\n",
    "                    length=i-stack[-1]\n",
    "                maximum_length=max(length,maximum_length)\n",
    "                \n",
    "        return maximum_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 131,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 131,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.longestValidParentheses('()(())')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**DP solution**: Given the maximum length of valid parenthesis **ending at index i**, how can we get the maximum length of valid parenthesis of index i+1?\n",
    "\n",
    "1. if s[i+1]=='(', then dp[i+1]=0\n",
    "2. if s[i]=='(', s[i+1]==')', then dp[i+1]=dp[i]+2\n",
    "3. if s[i]==')', s[i+1]==')':\n",
    "      if dp[i-dp[i]]=='(':\n",
    "          dp[i+1]=dp[i-dp[i]-1]+dp[i]+2\n",
    "      else:\n",
    "          dp[i+1]=0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 171,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def longestValidParentheses(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        maximum_length=0\n",
    "        n=len(s)\n",
    "        if n==0:\n",
    "            return 0\n",
    "        dp=[0]*n\n",
    "        for i in xrange(n-1):\n",
    "            if s[i]=='(' and s[i+1]==')':\n",
    "                dp[i+1]+=2\n",
    "                if i-1>=0:\n",
    "                    dp[i+1]+=dp[i-1]\n",
    "            elif s[i]==')' and s[i+1]==')':\n",
    "                if i-dp[i]>=0 and s[i-dp[i]]=='(':\n",
    "                    dp[i+1]+=dp[i]+2\n",
    "                    if i-dp[i]-1>=0:\n",
    "                        dp[i+1]+=dp[i-dp[i]-1]      \n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 172,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 172,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.longestValidParentheses(\"(()))())(\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 84. Largest Rectangle in Histogram"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.\n",
    "\n",
    "<img src=http://www.leetcode.com/wp-content/uploads/2012/04/histogram.png>\n",
    "\n",
    "Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].\n",
    "\n",
    "<img src=http://www.leetcode.com/wp-content/uploads/2012/04/histogram_area.png>\n",
    "\n",
    "The largest rectangle is shown in the shaded area, which has area = 10 unit. For example,\n",
    "Given heights = [2,1,5,6,2,3],\n",
    "return 10."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Brutal foce solution O(n^2). From the brutal force solution, we know that the area of the rectangle given a range is decided by the largest height."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Brutal force**:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def largestRectangleArea(self, heights):\n",
    "        \"\"\"\n",
    "        :type heights: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n=len(heights)\n",
    "        max_area=0\n",
    "        for i in xrange(n):\n",
    "            min_height=heights[i]\n",
    "            for j in xrange(i,n):\n",
    "                min_height=min(heights[j],min_height)\n",
    "                max_area=max(max_area,(j-i+1)*min_height)\n",
    "                \n",
    "        return max_area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.largestRectangleArea([2,1,5,6,2,3])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Divide and conquer solution**: We divide the heights into left and right subarray and then find max_left_area, max_right_area. Then we compare it with the maximum area expanding from the middle. Can we do it in O(n) time? Notice that we have to include heights[mid],heights[mid+1]. The way we expand is towards the higher side."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def largestRectangleArea(self, heights):\n",
    "        \"\"\"\n",
    "        :type heights: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if heights==[]:\n",
    "            return 0\n",
    "        return self.helper(heights,0,len(heights)-1)\n",
    "        \n",
    "    def helper(self,heights,start,end):\n",
    "        if start==end:\n",
    "            return heights[start]\n",
    "        mid=(start+end)/2\n",
    "        max_left_area=self.helper(heights,start,mid)\n",
    "        max_right_area=self.helper(heights,mid+1,end)\n",
    "        i=mid\n",
    "        j=mid+1\n",
    "        height=min(heights[i],heights[j])\n",
    "        max_mid_area=0\n",
    "        while i>=start and j<=end:\n",
    "            height=min(height,min(heights[i],heights[j]))\n",
    "            max_mid_area=max(max_mid_area,height*(j-i+1))\n",
    "            if i==start:\n",
    "                j+=1\n",
    "            elif j==end:\n",
    "                i-=1\n",
    "            elif heights[i-1]<=heights[j+1]:\n",
    "                j+=1\n",
    "            else:\n",
    "                i-=1\n",
    "                \n",
    "        return max(max_left_area,max_right_area,max_mid_area)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "20"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.largestRectangleArea([3,6,5,7,4,8,1,0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Stack solution**: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def largestRectangleArea(self, heights):\n",
    "        \"\"\"\n",
    "        :type heights: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        stack=[]\n",
    "        n=len(heights)\n",
    "        max_area=0\n",
    "        i=0\n",
    "        while i<n:\n",
    "            if stack==[] or heights[stack[-1]]<=heights[i]:\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                while stack!=[] and heights[stack[-1]]>heights[i]:\n",
    "                    top=stack[-1]\n",
    "                    stack.pop()\n",
    "                    if stack==[]:\n",
    "                        max_area=max(max_area,heights[top]*i)\n",
    "                    else:\n",
    "                        max_area=max(max_area,heights[top]*(i-stack[-1]-1))\n",
    "                stack.append(i)\n",
    "                \n",
    "            i+=1\n",
    "            \n",
    "        while stack!=[]:\n",
    "            top=stack[-1]\n",
    "            stack.pop()\n",
    "            if stack==[]:\n",
    "                max_area=max(max_area,heights[top]*i)\n",
    "            else:\n",
    "                max_area=max(max_area,heights[top]*(i-stack[-1]-1))\n",
    "            \n",
    "        return max_area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 107,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.largestRectangleArea([1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 139. Word Break"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.\n",
    "\n",
    "For example, given\n",
    "s = \"leetcode\",\n",
    "dict = [\"leet\", \"code\"].\n",
    "\n",
    "Return true because \"leetcode\" can be segmented as \"leet code\"."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Consider a recursive solution, If s[start:i] is in the dictionary, we examine s[i:end]."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def wordBreak(self, s, wordDict):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type wordDict: List[str]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        start=0\n",
    "        end=len(s)-1\n",
    "        return self.helper(s,start,end,wordDict)\n",
    "        \n",
    "    def helper(self,s,start,end,wordDict):\n",
    "        if s[start:end+1] in wordDict:\n",
    "            return True\n",
    "        else:\n",
    "            for i in xrange(start+1,end+1):\n",
    "                if s[start:i] in wordDict and self.helper(s,i,end,wordDict):\n",
    "                    return True\n",
    "                \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "wordDict=['a','b']\n",
    "o.wordBreak('ab',wordDict)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above solution is TLE. We consider a DP solution: Create an index array, as we scan through the array, we record the positions that s[start,i] is a word in wordDict. Then we consider s[i,j] for i in previous positions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def wordBreak(self, s, wordDict):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type wordDict: List[str]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if s=='':\n",
    "            return False\n",
    "        n=len(s)\n",
    "        prev_pos=[-1]\n",
    "        for i in xrange(n):\n",
    "            for pos in prev_pos:\n",
    "                if s[pos+1:i+1] in wordDict:\n",
    "                    prev_pos.append(i)\n",
    "                    break\n",
    "            \n",
    "        return n-1 in prev_pos"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "wordDict=['a','bc']\n",
    "o.wordBreak('ab',wordDict)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 164. Maximum Gap"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given an unsorted array, find the maximum difference between the successive elements in its sorted form.\n",
    "\n",
    "Try to solve it in linear time/space.\n",
    "\n",
    "Return 0 if the array contains less than 2 elements.\n",
    "\n",
    "You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: The idea is bucket sort and pigeonhole principle.\n",
    "\n",
    "1. choose bucketsize b=max(1,(max-min)/(n-1)), then the number of buckets is given by k=(max-min)/b\n",
    "\n",
    "2. Each bucket hold the range of values $[min+i* b, min+(i+1)* b)$\n",
    "\n",
    "3. special caes, n<=2, max==min"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 131,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def maximumGap(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n=len(nums)\n",
    "        if n<2:\n",
    "            return 0\n",
    "        maximum=max(nums)\n",
    "        minimum=min(nums)\n",
    "        if maximum==minimum:\n",
    "            return 0\n",
    "        # bucket size\n",
    "        b=max(1,(maximum-minimum)/(n-1))\n",
    "        # number of buckets\n",
    "        k=(maximum-minimum)/b+1\n",
    "        buckets=[[] for i in xrange(k)]\n",
    "        for i in xrange(n):\n",
    "            index=(nums[i]-minimum)/b\n",
    "            buckets[index].append(nums[i])\n",
    "        \n",
    "        prev_max=max(buckets[0])\n",
    "        max_gap=0\n",
    "        for i in xrange(1,k):\n",
    "            if buckets[i]!=[]:\n",
    "                max_gap=max(max_gap,min(buckets[i])-prev_max)\n",
    "                prev_max=max(buckets[i])\n",
    "                \n",
    "        return max_gap"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 133,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "9999"
      ]
     },
     "execution_count": 133,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "nums=[1,10000]\n",
    "o.maximumGap(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 220. Contains Duplicate III(Bucket sort)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Brutal force: $O(n*k)$. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def containsNearbyAlmostDuplicate(self, nums, k, t):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :type t: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        n=len(nums)\n",
    "        for i in xrange(n):\n",
    "            for j in xrange(1,k+1):\n",
    "                if i+j<n and abs(nums[i]-nums[i+j])<=t:\n",
    "                    return True\n",
    "                \n",
    "        return False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We could implement the idea of bucket sort to reduce the time complexity. Bucketing means we map a range of values to the a bucket. For example, if the bucket size is 3, we consider 0, 1, 2 all map to the same bucket. However, if t == 3, (0, 3) is a considered duplicates but does not map to the same bucket. This is fine since we are checking the buckets immediately before and after as well. So, as a rule of thumb, just make sure the size of the bucket is reasonable such that elements having the same bucket is immediately considered duplicates or duplicates must lie within adjacent buckets. So this actually gives us a range of possible bucket size, i.e. t and t + 1. We just choose it to be t and a bucket mapping to be num / t.\n",
    "\n",
    "Another complication is that negative ints are allowed. A simple num / t just shrinks everything towards 0. Therefore, we can just reposition every element to start from Integer.MIN_VALUE.\n",
    "\n",
    "If two numbers appear to be in the same bucket or adjacent bucket, we return true. If the number of buckets are greater than k, we can remove the one correspond to num[i-k]/t\n",
    "\n",
    "We could use a hashtable to realize the algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def containsNearbyAlmostDuplicate(self, nums, k, t):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :type t: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if t<0:\n",
    "            return False\n",
    "        n=len(nums)\n",
    "        bucket_table={}\n",
    "        for i in xrange(n):\n",
    "            index=nums[i]/(t+1)\n",
    "            if bucket_table.get(index)!=None \\\n",
    "            or (bucket_table.get(index-1)!=None and abs(bucket_table[index-1]-nums[i])<=t) \\\n",
    "            or (bucket_table.get(index+1)!=None and abs(bucket_table[index+1]-nums[i])<=t):\n",
    "                return True\n",
    "            else:\n",
    "                bucket_table[index]=nums[i]\n",
    "                \n",
    "            if i>=k:\n",
    "                bucket_table.pop(nums[i-k]/(t+1))\n",
    "                \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "nums=[3,6,0,2]\n",
    "o.containsNearbyAlmostDuplicate(nums,2,2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice the special case t<=0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 278. First Bad Version"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.\n",
    "\n",
    "Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.\n",
    "\n",
    "You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: This can be done by binary search"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# The isBadVersion API is already defined for you.\n",
    "# @param version, an integer\n",
    "# @return a bool\n",
    "# def isBadVersion(version):\n",
    "\n",
    "class Solution(object):\n",
    "    def firstBadVersion(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        return self.helper(1,n)\n",
    "    \n",
    "    def helper(self,start,end):\n",
    "        if start==end:\n",
    "            if isBadVersion(start):\n",
    "                return start\n",
    "            else:\n",
    "                return -1\n",
    "        mid=(start+end)/2\n",
    "        if isBadVersion(mid):\n",
    "            return self.helper(start,mid)\n",
    "        else:\n",
    "            return self.helper(mid+1,end)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 292. Nim Game"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.\n",
    "\n",
    "Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.\n",
    "\n",
    "For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: We have the following recursion.\n",
    "win(n)=any(not win(n-1), not win(n-2), not win(n-3))\n",
    "\n",
    "base case:\n",
    "win(1)=win(2)=win(3)=true"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def canWinNim(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        win=[True]*n\n",
    "        for i in xrange(3,n):\n",
    "            win[i]=any([not win[i-1],not win[i-2],not win[i-3]])\n",
    "            \n",
    "        return win[-1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above solution has memory error for large n. We can do better."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def canWinNim(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if n<=3:\n",
    "            return True\n",
    "        win_prev1=True\n",
    "        win_prev2=True\n",
    "        win_prev3=True\n",
    "        win_curr=None\n",
    "        for i in xrange(4,n+1):\n",
    "            win_curr=any([not win_prev1,not win_prev2,not win_prev3])\n",
    "            win_prev3=win_prev2\n",
    "            win_prev2=win_prev1\n",
    "            win_prev1=win_curr\n",
    "            \n",
    "        return win_curr"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Hint:\n",
    "\n",
    "If there are 5 stones in the heap, could you figure out a way to remove the stones such that you will always be the winner?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above solution is TLE for n=1348820612. There turns out to be a O(1) mathematical solution:\n",
    "\n",
    "suppose there are x stones left for first player (A), he can take 1,2,3 stones away, so second player B will have three cases to deal with (x -1), (x-2), (x-3). after he pick the stones, there will be 9 cases left for A.\n",
    "\n",
    "B (x-1) -> A: (x-2), (x-3), (x-4)\n",
    "\n",
    "B (x-2) -> A: (x-3), (x-4), (x-5)\n",
    "\n",
    "B (x-3) -> A: (x-4), (x-5), (x-6)\n",
    "\n",
    "Now, if A can guarantee he win at either of three groups, then he can force B to into that one of the three states and A can end up in that particular group after B's move.\n",
    "\n",
    "f(x) = (f(x-2)&&f(x-3)&&f(x-4)) || (f(x-3)&&f(x-4)&&f(x-5)) || (f(x-4)&&f(x-5)&&f(x-6))\n",
    "\n",
    "if we examine the equation a little closer, we can find f(x - 4) is a critical point, if f(x-4) is false, then f(x) will be always false.\n",
    "\n",
    "we can also find out the initial conditions, f(1), f(2), f(3) will be true (A always win), and f(4) will be false. so\n",
    "based on previous equation and initial conditions f(5) = f(6) = f(7) = true, f(8) = false;\n",
    "obviously, f(1), f(2), f(3) can make all f(4n + 1), f(4n + 2), f(4n + 3) to be true, only f(4n) will be false then.\n",
    "so here we go our one line solution:\n",
    "\n",
    "return (n % 4 != 0);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def canWinNim(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        return n%4!=0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 295. Find Median from Data Stream"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.\n",
    "\n",
    "Examples: \n",
    "\n",
    "[2,3,4] , the median is 3\n",
    "\n",
    "[2,3], the median is (2 + 3) / 2 = 2.5\n",
    "\n",
    "Design a data structure that supports the following two operations:\n",
    "\n",
    "void addNum(int num) - Add a integer number from the data stream to the data structure.\n",
    "double findMedian() - Return the median of all elements so far.\n",
    "For example:\n",
    "\n",
    "addNum(1)\n",
    "\n",
    "addNum(2)\n",
    "\n",
    "findMedian() -> 1.5\n",
    "\n",
    "addNum(3) \n",
    "\n",
    "findMedian() -> 2\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Naive solution is insertion sort. addNum will be O(n) and findMedian will be O(1). Can we do better? We can use two list to store the numbers, but in this case addNum still takes O(n) time if we are unlucky. The best we can do is to keep a maxheap of nums[:n/2] and a minheap of nums[n/2:]. Then add a number will take O(log n) time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import heapq\n",
    "\n",
    "class MedianFinder(object):\n",
    "\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        initialize your data structure here.\n",
    "        \"\"\"\n",
    "        self.maxheap=[]\n",
    "        self.minheap=[]\n",
    "        heapq.heapify(self.maxheap)\n",
    "        heapq.heapify(self.minheap)\n",
    "        self.sizemax=0\n",
    "        self.sizemin=0\n",
    "\n",
    "    def addNum(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: void\n",
    "        \"\"\"\n",
    "        heapq.heappush(self.minheap,num)\n",
    "        self.sizemin+=1\n",
    "        \n",
    "        if self.sizemin-self.sizemax==1 and self.sizemax>0 and self.minheap[0]<-self.maxheap[0]:\n",
    "            maxtop=heapq.heappop(self.maxheap)\n",
    "            mintop=heapq.heappop(self.minheap)\n",
    "            heapq.heappush(self.maxheap,-mintop)\n",
    "            heapq.heappush(self.minheap,-maxtop)\n",
    "        elif self.sizemin-self.sizemax==2:\n",
    "            heapq.heappush(self.maxheap,-heapq.heappop(self.minheap))\n",
    "            self.sizemin-=1\n",
    "            self.sizemax+=1\n",
    "\n",
    "    def findMedian(self):\n",
    "        \"\"\"\n",
    "        :rtype: float\n",
    "        \"\"\"\n",
    "        if (self.sizemax+self.sizemin)==0:\n",
    "            return None\n",
    "        if (self.sizemax+self.sizemin)%2==0:\n",
    "            return float(self.minheap[0]-self.maxheap[0])/float(2)\n",
    "        else:\n",
    "            return float(self.minheap[0])\n",
    "\n",
    "\n",
    "# Your MedianFinder object will be instantiated and called as such:\n",
    "# obj = MedianFinder()\n",
    "# obj.addNum(num)\n",
    "# param_2 = obj.findMedian()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 208,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.5"
      ]
     },
     "execution_count": 208,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import heapq\n",
    "a=[2,1]\n",
    "heapq.heapify(a)\n",
    "len(a)\n",
    "1/float(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 307. Range Sum Query - Mutable(Binary Indexed Tree to be figured out later)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.\n",
    "\n",
    "The update(i, val) function modifies nums by updating the element at index i to val.\n",
    "\n",
    "Example:\n",
    "Given nums = [1, 3, 5]\n",
    "\n",
    "sumRange(0, 2) -> 9\n",
    "\n",
    "update(1, 2)\n",
    "\n",
    "sumRange(0, 2) -> 8\n",
    "\n",
    "Note:\n",
    "1. The array is only modifiable by the update function.\n",
    "2. You may assume the number of calls to update and sumRange function is distributed evenly.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Naive solution: create a summation array. For sumRange the run time is O(1) but for update the run time is O(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Segment Tree**: https://leetcode.com/articles/range-sum-query-mutable/\n",
    "\n",
    "To implement segment tree method, we need three functions:\n",
    "\n",
    "1. BuildTree: We need $1+2+4+...+2^x, 2^x=n$ extra space to build up the tree from bottom up. So the number of nodes in the tree is\n",
    "\n",
    "$$\n",
    "2^{x+1}-1=2n-1\n",
    "$$\n",
    "\n",
    "We will create a tree of size $2*n$ and use last $n$ slots to store nums as leaves and then use the first n slots to store the parents which is the summation of its left and right child, i.e.\n",
    "\n",
    "$$\n",
    "tree[i]=tree[2*i]+tree[2*i+1]\n",
    "$$\n",
    "\n",
    "BuildTree takes O(n) time and should be done in the preprocessing step.\n",
    "\n",
    "2. Update: First we update the leaf tree[i+n], then we trace its parent to update the value of all the parents. This operation takes O(log n) time.\n",
    "3. sumRange: If we want to sum range [i to j], we first pick up leaf i and leaf j, then\n",
    "\n",
    "while i<=j:\n",
    "\n",
    "if i is right child: we sum nums[i] to the total sum, and let i move to the next leaf and then move to its parent\n",
    "if i is left child: we let i point to its parent\n",
    "\n",
    "if j is left child: we sum nums[j] to the total sum, and let i move to the previous leaf and then move to its parent\n",
    "if j is right child: we let j point to its parent.\n",
    "\n",
    "This operation takes O(log n) time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class NumArray(object):\n",
    "\n",
    "    def __init__(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        \"\"\"\n",
    "        self.n=len(nums)\n",
    "        self.tree=[0]*(2*self.n)\n",
    "        self.buildTree(nums);\n",
    "\n",
    "    def update(self, i, val):\n",
    "        \"\"\"\n",
    "        :type i: int\n",
    "        :type val: int\n",
    "        :rtype: void\n",
    "        \"\"\"\n",
    "        m=i+self.n\n",
    "        self.tree[m]=val\n",
    "        m/=2\n",
    "        while m>0:\n",
    "            self.tree[m]=self.tree[2*m]+self.tree[2*m+1]\n",
    "            m/=2\n",
    "\n",
    "    def sumRange(self, i, j):\n",
    "        \"\"\"\n",
    "        :type i: int\n",
    "        :type j: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        i+=self.n\n",
    "        j+=self.n\n",
    "        result=0\n",
    "        while i<=j:\n",
    "            if i%2==1:\n",
    "                result+=self.tree[i]\n",
    "                i+=1\n",
    "            if j%2==0:\n",
    "                result+=self.tree[j]\n",
    "                j-=1\n",
    "            i/=2\n",
    "            j/=2\n",
    "        return result\n",
    "        \n",
    "    def buildTree(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        \"\"\"\n",
    "        n=len(nums)\n",
    "        for i in xrange(n):\n",
    "            self.tree[i+n]=nums[i]\n",
    "        for i in xrange(n-1,0,-1):\n",
    "            self.tree[i]=self.tree[2*i]+self.tree[2*i+1]\n",
    "\n",
    "\n",
    "# Your NumArray object will be instantiated and called as such:\n",
    "# obj = NumArray(nums)\n",
    "# obj.update(i,val)\n",
    "# param_2 = obj.sumRange(i,j)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Greatest common divisor by using segment tree**:\n",
    "\n",
    "We can construct the same tree as in the summation case. But this time we replace the parent node value with the greatest common divisor of its left and right child. The greatest common divisor can be found by euclidean algorithm.\n",
    "\n",
    "<https://en.wikipedia.org/wiki/Euclidean_algorithm>\n",
    "\n",
    "Likewise, we could implement segment tree in calculating the least common multiple of an array. Notice that for two numbers a,b:\n",
    "$$\n",
    "lcm(a,b)=\\frac{a*b}{gcd(a,b)}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Binary Indexed Tree**: https://discuss.leetcode.com/topic/31599/java-using-binary-indexed-tree-with-clear-explanation\n",
    "\n",
    "https://www.topcoder.com/community/data-science/data-science-%20tutorials/binary-indexed-trees/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class NumArray(object):\n",
    "\n",
    "    def __init__(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        \"\"\"\n",
    "        \n",
    "\n",
    "    def update(self, i, val):\n",
    "        \"\"\"\n",
    "        :type i: int\n",
    "        :type val: int\n",
    "        :rtype: void\n",
    "        \"\"\"\n",
    "        \n",
    "\n",
    "    def sumRange(self, i, j):\n",
    "        \"\"\"\n",
    "        :type i: int\n",
    "        :type j: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        \n",
    "    def buildTree(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        \"\"\"\n",
    "        \n",
    "\n",
    "\n",
    "# Your NumArray object will be instantiated and called as such:\n",
    "# obj = NumArray(nums)\n",
    "# obj.update(i,val)\n",
    "# param_2 = obj.sumRange(i,j)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 329. Longest Increasing Path in a Matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given an integer matrix, find the length of the longest increasing path.\n",
    "\n",
    "From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).\n",
    "\n",
    "Example 1:\n",
    "\n",
    "nums = [\n",
    "  [9,9,4],\n",
    "  [6,6,8],\n",
    "  [2,1,1]\n",
    "]\n",
    "\n",
    "Return 4\n",
    "\n",
    "The longest increasing path is [1, 2, 6, 9].\n",
    "\n",
    "Example 2:\n",
    "\n",
    "nums = [\n",
    "  [3,4,5],\n",
    "  [3,2,6],\n",
    "  [2,2,1]\n",
    "]\n",
    "\n",
    "Return 4\n",
    "\n",
    "The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Brutal force solution: Do dfs starting from every entry and calculate the longest path. O(n^2). To improve runtime, we use a matrix to record the longest path corresponding to each entry."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 144,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def longestIncreasingPath(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n=len(matrix)\n",
    "        if n==0:\n",
    "            return 0\n",
    "        m=len(matrix[0])\n",
    "        if m==0:\n",
    "            return 0\n",
    "        path_lengths=[[0]*m for i in xrange(n)]\n",
    "        max_length=0\n",
    "        for i in xrange(n):\n",
    "            for j in xrange(m):\n",
    "                if path_lengths[i][j]==0:\n",
    "                    path_lengths[i][j]=self.dfs(i,j,n,m,matrix, path_lengths)\n",
    "                    max_length=max(max_length,path_lengths[i][j])\n",
    "                    \n",
    "        return max_length\n",
    "    \n",
    "    def dfs(self,i,j,n,m,matrix, path_lengths):\n",
    "        \"\"\"\n",
    "        :type i,j,n,m: int\n",
    "        :type matrix, path_lengths: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        left=1\n",
    "        right=1\n",
    "        up=1\n",
    "        down=1\n",
    "        # left\n",
    "        if j-1>=0 and matrix[i][j]<matrix[i][j-1]:\n",
    "            if path_lengths[i][j-1]==0:\n",
    "                left+=self.dfs(i,j-1,n,m,matrix,path_lengths)\n",
    "            else:\n",
    "                left+=path_lengths[i][j-1]\n",
    "        # right\n",
    "        if j+1<m and matrix[i][j]<matrix[i][j+1]:\n",
    "            if path_lengths[i][j+1]==0:\n",
    "                right+=self.dfs(i,j+1,n,m,matrix,path_lengths)\n",
    "            else:\n",
    "                right+=path_lengths[i][j+1]\n",
    "        # up\n",
    "        if i-1>=0 and matrix[i][j]<matrix[i-1][j]:\n",
    "            if path_lengths[i-1][j]==0:\n",
    "                up+=self.dfs(i-1,j,n,m,matrix,path_lengths)\n",
    "            else:\n",
    "                up+=path_lengths[i-1][j]\n",
    "        # down\n",
    "        if i+1<n and matrix[i][j]<matrix[i+1][j]:\n",
    "            if path_lengths[i+1][j]==0:\n",
    "                down+=self.dfs(i+1,j,n,m,matrix,path_lengths)\n",
    "            else:\n",
    "                down+=path_lengths[i+1][j]\n",
    "        \n",
    "        path_lengths[i][j]=max(left,right,up,down)\n",
    "        \n",
    "        return path_lengths[i][j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 146,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 146,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "matrix= [[9,9,4], [6,6,8], [2,1,1]]\n",
    "o.longestIncreasingPath(matrix)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 330. Patching Array(Greedy)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a sorted positive integer array nums and an integer n, add/patch elements to the array such that any number in range [1, n] inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.\n",
    "\n",
    "Example 1:\n",
    "\n",
    "nums = [1, 3], n = 6\n",
    "\n",
    "Return 1.\n",
    "\n",
    "Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.\n",
    "Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3].\n",
    "Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6].\n",
    "\n",
    "So we only need 1 patch.\n",
    "\n",
    "Example 2:\n",
    "\n",
    "nums = [1, 5, 10], n = 20\n",
    "\n",
    "Return 2.\n",
    "\n",
    "The two patches can be [2, 4].\n",
    "\n",
    "Example 3:\n",
    "\n",
    "nums = [1, 2, 2], n = 5\n",
    "\n",
    "Return 0.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: We can apply a Greedy algorithm to solve the problem. We start from the beginning of nums to scan the array. For the current number nums[i], the maximum range we can reach is max_range+=nums[i]. while nums[i+1]>max_range+1, we fill in the number max_range+1 and update max_range+=max_range+1. Then for nums[i+1]<=max_range+1, we can update the maximum range by max_range+=nums[i+1]."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 153,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def minPatches(self, nums, n):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        max_range=0\n",
    "        num_patches=0\n",
    "        for i in xrange(len(nums)):\n",
    "            if nums[i]>n:\n",
    "                break\n",
    "            if max_range>=n:\n",
    "                return num_patches\n",
    "            while nums[i]>max_range+1:\n",
    "                max_range+=max_range+1\n",
    "                num_patches+=1\n",
    "            max_range+=nums[i]\n",
    "            \n",
    "        while max_range<n:\n",
    "            max_range+=max_range+1\n",
    "            num_patches+=1\n",
    "            \n",
    "        return num_patches"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 154,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 154,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "nums=[1,99]\n",
    "o.minPatches(nums,5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A more concise coding with the same idea is as follows:\n",
    "\n",
    "https://discuss.leetcode.com/topic/35517/share-my-greedy-solution-by-java-with-simple-explanation-time-1-ms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 374. Guess Number Higher or Lower"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We are playing the Guess Game. The game is as follows:\n",
    "\n",
    "I pick a number from 1 to n. You have to guess which number I picked.\n",
    "\n",
    "Every time you guess wrong, I'll tell you whether the number is higher or lower.\n",
    "\n",
    "You call a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0):\n",
    "\n",
    "-1 : My number is lower\n",
    "\n",
    " 1 : My number is higher\n",
    " \n",
    " 0 : Congrats! You got it!\n",
    " \n",
    "Example:\n",
    "\n",
    "n = 10, I pick 6.\n",
    "\n",
    "Return 6.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Naive solution O(n), which does not make use of the high and low information. Improved solution: Binary search"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# The guess API is already defined for you.\n",
    "# @param num, your guess\n",
    "# @return -1 if my number is lower, 1 if my number is higher, otherwise return 0\n",
    "# def guess(num):\n",
    "\n",
    "class Solution(object):\n",
    "    def guessNumber(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        return self.helper(1,n)\n",
    "    \n",
    "    def helper(self,start,end):\n",
    "        \"\"\"\n",
    "        :type start,end: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if start==end:\n",
    "            return start\n",
    "        mid=(start+end)/2\n",
    "        if guess(mid)==1:\n",
    "            return self.helper(mid+1,end)\n",
    "        elif guess(mid)==-1:\n",
    "            return self.helper(start,mid-1)\n",
    "        else:\n",
    "            return mid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'[1, 2, 3]'"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "str([1,2,3])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 375. Guess Number Higher or Lower II(minimax)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We are playing the Guess Game. The game is as follows:\n",
    "\n",
    "I pick a number from 1 to n. You have to guess which number I picked.\n",
    "\n",
    "Every time you guess wrong, I'll tell you whether the number I picked is higher or lower.\n",
    "\n",
    "However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked.\n",
    "\n",
    "Example:\n",
    "\n",
    "n = 10, I pick 8.\n",
    "\n",
    "First round:  You guess 5, I tell you that it's higher. You pay $5.\n",
    "\n",
    "Second round: You guess 7, I tell you that it's higher. You pay $7.\n",
    "\n",
    "Third round:  You guess 9, I tell you that it's lower. You pay $9.\n",
    "\n",
    "Game over. 8 is the number I picked.\n",
    "\n",
    "You end up paying $5 + $7 + $9 = $21.\n",
    "Given a particular n ≥ 1, find out how much money you need to have to guarantee a win."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: We need to figure out the minimum we need to pay in the worst case. Given the payment so far in the best strategy of the worst case and suppose we can choose from i to j, if we pick up x then\n",
    "\n",
    "result[i,j]=min([x+max(result[i,x-1],result[x+1,j]) for x in range(i,j+1)])\n",
    "\n",
    "if i==j: \n",
    "result[i,j]=0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import sys\n",
    "\n",
    "class Solution(object):\n",
    "    def getMoneyAmount(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        result=[[0]*n for i in xrange(n)]\n",
    "        for l in xrange(1,n):\n",
    "            for i in xrange(n-l):\n",
    "                result[i][i+l]=sys.maxint\n",
    "                for k in range(i,i+l+1):\n",
    "                    temp=k+1\n",
    "                    if k-1<i:\n",
    "                        temp+=result[k+1][i+l]\n",
    "                    elif k+1>i+l:\n",
    "                        temp+=result[i][k-1]\n",
    "                    else:\n",
    "                        temp+=max(result[i][k-1],result[k+1][i+l])\n",
    "                    result[i][i+l]=min(result[i][i+l],temp)\n",
    "                \n",
    "        return result[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "16"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.getMoneyAmount(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Hint:\n",
    "\n",
    "1. The best strategy to play the game is to minimize the maximum loss you could possibly face. Another strategy is to minimize the expected loss. Here, we are interested in the first scenario.\n",
    "2. Take a small example (n = 3). What do you end up paying in the worst case?\n",
    "3. Check out this article if you're still stuck.\n",
    "4. The purely recursive implementation of minimax would be worthless for even a small n. You MUST use dynamic programming.\n",
    "5. As a follow-up, how would you modify your code to solve the problem of minimizing the expected loss, instead of the worst-case loss?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 403. Frog Jump"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A frog is crossing a river. The river is divided into x units and at each unit there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.\n",
    "\n",
    "Given a list of stones' positions (in units) in sorted ascending order, determine if the frog is able to cross the river by landing on the last stone. Initially, the frog is on the first stone and assume the first jump must be 1 unit.\n",
    "\n",
    "If the frog's last jump was k units, then its next jump must be either k - 1, k, or k + 1 units. Note that the frog can only jump in the forward direction.\n",
    "\n",
    "Note:\n",
    "\n",
    "* The number of stones is ≥ 2 and is < 1,100.\n",
    "* Each stone's position will be a non-negative integer < 2^31.\n",
    "* The first stone's position is always 0.\n",
    "\n",
    "Example 1:\n",
    "\n",
    "[0,1,3,5,6,8,12,17]\n",
    "\n",
    "There are a total of 8 stones.\n",
    "The first stone at the 0th unit, second stone at the 1st unit,\n",
    "third stone at the 3rd unit, and so on...\n",
    "The last stone at the 17th unit.\n",
    "\n",
    "Return true. The frog can jump to the last stone by jumping \n",
    "1 unit to the 2nd stone, then 2 units to the 3rd stone, then \n",
    "2 units to the 4th stone, then 3 units to the 6th stone, \n",
    "4 units to the 7th stone, and 5 units to the 8th stone.\n",
    "\n",
    "Example 2:\n",
    "\n",
    "[0,1,2,3,4,8,9,11]\n",
    "\n",
    "Return false. There is no way to jump to the last stone as \n",
    "the gap between the 5th and 6th stone is too large.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: We could perform a dfs search from the first stone and check if the frog is able to reach the last."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 166,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def canCross(self, stones):\n",
    "        \"\"\"\n",
    "        :type stones: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        n=len(stones)\n",
    "        return self.dfs(stones,0,stones[-1],0)\n",
    "        \n",
    "    def dfs(self,stones,start,end,last):\n",
    "        \"\"\"\n",
    "        :type stones: List[int]\n",
    "        :type start,end,last: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if start==end:\n",
    "            return True\n",
    "        next_stones=[stones[i] for i in xrange(len(stones)) if stones[i]>start]\n",
    "        if last-1>0 and (start+last-1 in next_stones) and self.dfs(next_stones,start+last-1,end,last-1):\n",
    "            return True\n",
    "        if last>0 and (start+last in next_stones) and self.dfs(next_stones,start+last,end,last):\n",
    "            return True\n",
    "        if last+1>0 and (start+last+1 in next_stones) and self.dfs(next_stones,start+last+1,end,last+1):\n",
    "            return True\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 168,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 168,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "stones=[0,1,3,5,6,8,12,17]\n",
    "o.canCross(stones)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above solution is TLE. This is due to the fact that we make duplicate calls from different paths to the same position and the same last jumpsize. If we memorize these informations in the dfs process, we will be able to save much work."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 178,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 180,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 180,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "stones=[0,1,2,3,4,8,9,11]\n",
    "o.canCross(stones)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "An alternative solution is DP. We create a hashtable with stones[i] as the key and the list of all possible last jumpsizes as the value. The hashtable is initialized with stones[0]:{0}. Then we do a forward scan over stones, and add new_jumpsize into the list if stones[i]+new-jumpsize is in the key."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 198,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def canCross(self, stones):\n",
    "        \"\"\"\n",
    "        :type stones: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        n=len(stones)\n",
    "        hashtable={stones[i]:set() for i in xrange(n)}\n",
    "        hashtable[stones[0]]=set([0])\n",
    "        for i in xrange(n-1):\n",
    "            for last_jump in hashtable[stones[i]]:\n",
    "                if last_jump>0 and hashtable.get(stones[i]+last_jump)!=None:\n",
    "                    hashtable[stones[i]+last_jump].add(last_jump)\n",
    "                if last_jump-1>0 and hashtable.get(stones[i]+last_jump-1)!=None:\n",
    "                    hashtable[stones[i]+last_jump-1].add(last_jump-1)\n",
    "                if last_jump+1>0 and hashtable.get(stones[i]+last_jump+1)!=None:\n",
    "                    hashtable[stones[i]+last_jump+1].add(last_jump+1)\n",
    "                    \n",
    "        return hashtable[stones[-1]]!=set()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 199,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{0: set([0]), 1: set([1]), 3: set([2]), 5: set([2]), 6: set([1, 3]), 8: set([2, 3]), 12: set([4]), 17: set([5])}\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 199,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "stones=[0,1,3,5,6,8,12,17]\n",
    "o.canCross(stones)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that in the above solution it is important to use a set as the values in the hashtable otherwise there could be duplicate last jumps in the values. See the following example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 196,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def canCross(self, stones):\n",
    "        \"\"\"\n",
    "        :type stones: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        n=len(stones)\n",
    "        hashtable={stones[i]:[] for i in xrange(n)}\n",
    "        hashtable[stones[0]]=[0]\n",
    "        for i in xrange(n-1):\n",
    "            for last_jump in hashtable[stones[i]]:\n",
    "                if last_jump>0 and hashtable.get(stones[i]+last_jump)!=None:\n",
    "                    hashtable[stones[i]+last_jump].append(last_jump)\n",
    "                if last_jump-1>0 and hashtable.get(stones[i]+last_jump-1)!=None:\n",
    "                    hashtable[stones[i]+last_jump-1].append(last_jump-1)\n",
    "                if last_jump+1>0 and hashtable.get(stones[i]+last_jump+1)!=None:\n",
    "                    hashtable[stones[i]+last_jump+1].append(last_jump+1)\n",
    "        print hashtable            \n",
    "        return hashtable[stones[-1]]!=set()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 197,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{0: [0], 1: [1], 3: [2], 5: [2], 6: [3, 1], 8: [3, 2, 2], 12: [4], 17: [5]}\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 197,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "stones=[0,1,3,5,6,8,12,17]\n",
    "o.canCross(stones)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 477. Total Hamming Distance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Hamming distance between two integers is the number of positions at which the corresponding bits are different.\n",
    "\n",
    "Now your job is to find the total Hamming distance between all pairs of the given numbers.\n",
    "\n",
    "Example:\n",
    "Input: 4, 14, 2\n",
    "\n",
    "Output: 6\n",
    "\n",
    "Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just\n",
    "showing the four bits relevant in this case). So the answer will be:\n",
    "HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.\n",
    "\n",
    "Note:\n",
    "1. Elements of the given array are in the range of 0 to 10^9\n",
    "2. Length of the array will not exceed 10^4.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Brutal force O(n^2) solution. In order to improve the run time, we can use an array of length 32 to record the number of 1's in the digit as we pass through the nums for i in xrange(len(nums)) then the number of 0's in that digit is just i+1-number of 1's"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def totalHammingDistance(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n=len(nums)\n",
    "        num_ones=[0]*32\n",
    "        count=0\n",
    "        for i in xrange(n):\n",
    "            for j in xrange(32):\n",
    "                digit=(nums[i]>>j)&1\n",
    "                if digit==1:\n",
    "                    count+=i-num_ones[31-j]\n",
    "                    num_ones[31-j]+=1\n",
    "                else:\n",
    "                    count+=num_ones[31-j]\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 75,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.totalHammingDistance([4,14,2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2147483648"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "2**31"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "11&1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## <font color=red>480. Sliding Window Median"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.\n",
    "\n",
    "Examples:\n",
    "\n",
    "[2,3,4] , the median is 3\n",
    "\n",
    "[2,3], the median is (2 + 3) / 2 = 2.5\n",
    "\n",
    "Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Your job is to output the median array for each window in the original array.\n",
    "\n",
    "For example,\n",
    "\n",
    "Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.\n",
    "\n",
    "Window position                Median\n",
    "---------------               -----\n",
    "[1  3  -1] -3  5  3  6  7       1\n",
    " 1 [3  -1  -3] 5  3  6  7       -1\n",
    " 1  3 [-1  -3  5] 3  6  7       -1\n",
    " 1  3  -1 [-3  5  3] 6  7       3\n",
    " 1  3  -1  -3 [5  3  6] 7       5\n",
    " 1  3  -1  -3  5 [3  6  7]      6\n",
    " \n",
    " \n",
    "Therefore, return the median sliding window as [1,-1,-1,3,5,6].\n",
    "\n",
    "Note: \n",
    "You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: If we use the two heap method, the runtime will be O(n log k). Removing an element from one of the two heaps could be painful but should be done in O(log k) time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def medianSlidingWindow(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: List[float]\n",
    "        \"\"\""
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}