LEETCODE_30day_challenge_august_2020.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 1: 8/1/20\n",
    "### 520. Detect Capital\n",
    "EASY  \n",
    "https://leetcode.com/problems/detect-capital/  \n",
    "https://leetcode.com/explore/challenge/card/august-leetcoding-challenge/549/week-1-august-1st-august-7th/3409/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a word, you need to judge whether the usage of capitals in it is right or not.\n",
    "\n",
    "We define the usage of capitals in a word to be right when one of the following cases holds:\n",
    "\n",
    "All letters in this word are capitals, like \"USA\".\n",
    "All letters in this word are not capitals, like \"leetcode\".\n",
    "Only the first letter in this word is capital, like \"Google\".\n",
    "Otherwise, we define that this word doesn't use capitals in a right way.\n",
    " \n",
    "\n",
    "**Example 1:**\n",
    "```\n",
    "Input: \"USA\"\n",
    "Output: True\n",
    "```\n",
    "\n",
    "**Example 2:**\n",
    "```\n",
    "Input: \"FlaG\"\n",
    "Output: False\n",
    "```\n",
    "\n",
    "**Note:** The input will be a non-empty word consisting of uppercase and lowercase latin letters."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "word1 = 'USA'\n",
    "word2 = 'FlaG'\n",
    "word3 = 'leetcode'\n",
    "word4 = 'aA'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def detectCapitalUse(self, word: str) -> bool:\n",
    "        capcount = 0\n",
    "        first = False\n",
    "        for c in word:\n",
    "            if c == word[0] and c.isupper():\n",
    "                first = True\n",
    "            if c.isupper():\n",
    "                capcount +=1 \n",
    "        \n",
    "        return (first and capcount == 1) or (capcount == len(word)) or (capcount == 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "# lulz python builtins\n",
    "class Solution:\n",
    "    def detectCapitalUse(self, word: str) -> bool:\n",
    "        return word.isupper() or word.islower() or word.istitle()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "soln = Solution()\n",
    "soln.detectCapitalUse(word4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "word3.islower()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 3: 8/3/20\n",
    "### 125. Valid Palindrome\n",
    "EASY  \n",
    "https://leetcode.com/problems/valid-palindrome/  \n",
    "https://leetcode.com/explore/challenge/card/august-leetcoding-challenge/549/week-1-august-1st-august-7th/3411/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.\n",
    "\n",
    "Note: For the purpose of this problem, we define empty string as valid palindrome.\n",
    "\n",
    "**Example 1:**\n",
    "```\n",
    "Input: \"A man, a plan, a canal: Panama\"\n",
    "Output: true\n",
    "```\n",
    "**Example 2:**\n",
    "```\n",
    "Input: \"race a car\"\n",
    "Output: false\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "s1 = \"A man, a plan, a canal: Panama\"\n",
    "s2 = \"race a car\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "# using slicing\n",
    "import string\n",
    "class Solution:\n",
    "    def isPalindrome(self, s: str) -> bool:\n",
    "        # strip punctuation\n",
    "        table = str.maketrans('','',string.punctuation)\n",
    "        s = s.translate(table)\n",
    "        \n",
    "        # remove spaces, lower case\n",
    "        s = s.replace(' ','').lower()\n",
    "        \n",
    "        return s==s[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "soln = Solution()\n",
    "soln.isPalindrome(s2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 4: 8/4/20\n",
    "### 342. Power of Four\n",
    "EASY  \n",
    "https://leetcode.com/problems/power-of-four/  \n",
    "https://leetcode.com/explore/challenge/card/august-leetcoding-challenge/549/week-1-august-1st-august-7th/3412/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given an integer (signed 32 bits), write a function to check whether it is a power of 4.\n",
    "\n",
    "**Example 1:**\n",
    "```\n",
    "Input: 16\n",
    "Output: true\n",
    "```\n",
    "**Example 2:**\n",
    "```\n",
    "Input: 5\n",
    "Output: false\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Study Notes:**\n",
    "* This is actually a bit manipulation problem (for the optimal answer at least)\n",
    "* See solution for: [Power of Two](https://leetcode.com/problems/power-of-two/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "num1 = 16\n",
    "num2 = 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [],
   "source": [
    "# direct bit checking\n",
    "class Solution:\n",
    "    def isPowerOfFour(self, num: int) -> bool:\n",
    "        binstr = bin(num)\n",
    "        if (n>1) and ('1' not in binstr[3:]) and len(binstr)%2==1:\n",
    "            return True\n",
    "        elif n==1:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 172,
   "metadata": {},
   "outputs": [],
   "source": [
    "# bit manipulation\n",
    "class Solution:\n",
    "    def isPowerOfFour(self, num: int) -> bool:\n",
    "        return (num>0) and not(num&(num-1)) and (len(bin(num))%2==1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 171,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 171,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "soln = Solution()\n",
    "soln.isPowerOfFour(16)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 5: 8/5/20\n",
    "### 211. Add and Search Word - Data structure design\n",
    "MEDIUM  \n",
    "https://leetcode.com/problems/add-and-search-word-data-structure-design/  \n",
    "https://leetcode.com/explore/challenge/card/august-leetcoding-challenge/549/week-1-august-1st-august-7th/3413/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**UPDATE**\n",
    "\n",
    "This problem has been changed to: [https://leetcode.com/problems/design-add-and-search-words-data-structure/](https://leetcode.com/problems/design-add-and-search-words-data-structure/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Design a data structure that supports the following two operations:\n",
    "```\n",
    "void addWord(word)\n",
    "bool search(word)\n",
    "```\n",
    "search(word) can search a literal word or a regular expression string containing only letters `a-z` or `..` A `.` means it can represent any one letter.\n",
    "\n",
    "**Example:**\n",
    "```\n",
    "addWord(\"bad\")\n",
    "addWord(\"dad\")\n",
    "addWord(\"mad\")\n",
    "search(\"pad\") -> false\n",
    "search(\"bad\") -> true\n",
    "search(\".ad\") -> true\n",
    "search(\"b..\") -> true\n",
    "```\n",
    "**Note:**  \n",
    "You may assume that all words are consist of lowercase letters `a-z`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# using python built-ins\n",
    "import re\n",
    "from collections import defaultdict\n",
    "class WordDictionary:\n",
    "\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        Initialize your data structure here.\n",
    "        \"\"\"\n",
    "        self.words = defaultdict(set)\n",
    "\n",
    "    def addWord(self, word: str) -> None:\n",
    "        \"\"\"\n",
    "        Adds a word into the data structure.\n",
    "        \"\"\"\n",
    "        self.words[len(word)].add(word)\n",
    "\n",
    "    def search(self, word: str) -> bool:\n",
    "        \"\"\"\n",
    "        Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.\n",
    "        \"\"\"\n",
    "        pattern = re.compile(word)\n",
    "        for w in self.words[len(word)]:\n",
    "            if pattern.fullmatch(w):\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "\n",
    "# Your WordDictionary object will be instantiated and called as such:\n",
    "# obj = WordDictionary()\n",
    "# obj.addWord(word)\n",
    "# param_2 = obj.search(word)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "wd = WordDictionary()\n",
    "wd.addWord('bad')\n",
    "wd.addWord('dad')\n",
    "wd.addWord('pad')\n",
    "wd.search('pa.')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "wd = WordDictionary()\n",
    "wd.addWord('at')\n",
    "wd.addWord('and')\n",
    "wd.addWord('an')\n",
    "wd.addWord('add')\n",
    "wd.search('.dd')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 6: 8/6/20\n",
    "### 442. Find All Duplicates in an Array\n",
    "MEDIUM  \n",
    "https://leetcode.com/problems/find-all-duplicates-in-an-array/  \n",
    "https://leetcode.com/explore/challenge/card/august-leetcoding-challenge/549/week-1-august-1st-august-7th/3414/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear **twice** and others appear **once**.\n",
    "\n",
    "Find all the elements that appear **twice** in this array.\n",
    "\n",
    "Could you do it without extra space and in O(n) runtime?\n",
    "\n",
    "**Example:**\n",
    "```\n",
    "Input:\n",
    "[4,3,2,7,8,2,3,1]\n",
    "\n",
    "Output:\n",
    "[2,3]\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [],
   "source": [
    "nums1 = [4,3,2,7,8,2,3,1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def findDuplicates(self, nums: List[int]) -> List[int]:\n",
    "        result = []\n",
    "        for n in nums:\n",
    "            i = abs(n)-1\n",
    "            if nums[i]>0:\n",
    "                nums[i] = nums[i]*(-1)\n",
    "            else: # number at index has already been flagged, n is duplicate\n",
    "                result.append(abs(n)) # only works if duplicated numbers show up TWICE\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3]"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "soln = Solution()\n",
    "soln.findDuplicates(nums1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 7: 8/7/20\n",
    "### 987. Vertical Order Traversal of a Binary Tree\n",
    "MEDIUM  \n",
    "https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/  \n",
    "https://leetcode.com/explore/challenge/card/august-leetcoding-challenge/549/week-1-august-1st-august-7th/3415/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a binary tree, return the *vertical order* traversal of its nodes values.\n",
    "\n",
    "For each node at position `(X, Y)`, its left and right children respectively will be at positions `(X-1, Y-1)` and `(X+1, Y-1)`.\n",
    "\n",
    "Running a vertical line from `X = -infinity` to `X = +infinity`, whenever the vertical line touches some nodes, we report the values of the nodes in order from top to bottom (decreasing `Y` coordinates).\n",
    "\n",
    "If two nodes have the same position, then the value of the node that is reported first is the value that is smaller.\n",
    "\n",
    "Return an list of non-empty reports in order of `X` coordinate.  Every report will have a list of values of nodes.\n",
    "\n",
    "**Example 1:**\n",
    "![https://assets.leetcode.com/uploads/2019/01/31/1236_example_1.PNG](https://assets.leetcode.com/uploads/2019/01/31/1236_example_1.PNG)\n",
    "```\n",
    "Input: [3,9,20,null,null,15,7]\n",
    "Output: [[9],[3,15],[20],[7]]\n",
    "Explanation: \n",
    "Without loss of generality, we can assume the root node is at position (0, 0):\n",
    "Then, the node with value 9 occurs at position (-1, -1);\n",
    "The nodes with values 3 and 15 occur at positions (0, 0) and (0, -2);\n",
    "The node with value 20 occurs at position (1, -1);\n",
    "The node with value 7 occurs at position (2, -2).\n",
    "```\n",
    "**Example 2:**\n",
    "![https://assets.leetcode.com/uploads/2019/01/31/tree2.png](https://assets.leetcode.com/uploads/2019/01/31/tree2.png)\n",
    "```\n",
    "Input: [1,2,3,4,5,6,7]\n",
    "Output: [[4],[2],[1,5,6],[3],[7]]\n",
    "Explanation: \n",
    "The node with value 5 and the node with value 6 have the same position according to the given scheme.\n",
    "However, in the report \"[1,5,6]\", the node value of 5 comes first since 5 is smaller than 6.\n",
    "```\n",
    "\n",
    "**Note:**\n",
    "\n",
    "1. The tree will have between `1` and `1000` nodes.\n",
    "2. Each node's value will be between `0` and `1000`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        \n",
    "def constructtree(nodes, i, n):\n",
    "    root = None\n",
    "    if (i<n) and nodes[i] is not None:\n",
    "        root = TreeNode(nodes[i])\n",
    "        root.left = constructtree(nodes, 2*i+1, len(nodes))\n",
    "        root.right = constructtree(nodes, 2*i+2, len(nodes))\n",
    "    return root\n",
    "\n",
    "# still doesn't handle multiple levels of null in incomplete binary trees\n",
    "def printtree(root):\n",
    "    nodevals = []\n",
    "    q = [root]\n",
    "    level = []\n",
    "    while q:\n",
    "        level = q\n",
    "        q = []\n",
    "        while any(level): # also need to check if level is full of None\n",
    "            node = level.pop(0)\n",
    "            if node:\n",
    "                nodevals.append(node.val)\n",
    "                if node.left or node.right or level:\n",
    "                    q.append(node.left)\n",
    "                    q.append(node.right)\n",
    "            else:\n",
    "                nodevals.append('null') # insert word 'null' in place of empty node\n",
    "    return nodevals\n",
    "    \n",
    "\n",
    "tree1 = [3,9,20,None,None,15,7]\n",
    "root1 = constructtree(tree1,0,len(tree1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {},
   "outputs": [],
   "source": [
    "testtree = [3,9,20,None,None,15,7,None,None,None,None,None,None,5,9]\n",
    "# testroot = constructtree(testtree,0,len(testtree))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Study Notes:**\n",
    "* Use a dict (hash table) to store data regarding `X` and `Y` position for each node\n",
    "* Use dfs to fully explore tree\n",
    "* Return result using hash table, sorting the list of nodes at each `X` position by their `Y` position and value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 142,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:\n",
    "        n = (0,0,root)\n",
    "        q = [n]\n",
    "        nodes = defaultdict(list)\n",
    "        while q:\n",
    "            n = q.pop(0)\n",
    "            x = n[0]\n",
    "            y = n[1]\n",
    "            node = n[2]\n",
    "            nodes[x].append((y,node.val))\n",
    "            if node.left: q.append((x-1,y+1,node.left))\n",
    "            if node.right: q.append((x+1,y+1,node.right))\n",
    "            \n",
    "        # ugly double comprehension\n",
    "        result = [[j for i,j in sorted(nodes[k])] for k in sorted(nodes)]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 144,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[9], [3, 15], [20], [7]]"
      ]
     },
     "execution_count": 144,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "soln = Solution()\n",
    "soln.verticalTraversal(root1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 8: 8/8/20\n",
    "### 437. Path Sum III\n",
    "MEDIUM  \n",
    "https://leetcode.com/problems/path-sum-iii/  \n",
    "https://leetcode.com/explore/challenge/card/august-leetcoding-challenge/550/week-2-august-8th-august-14th/3417/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You are given a binary tree in which each node contains an integer value.\n",
    "\n",
    "Find the number of paths that sum to a given value.\n",
    "\n",
    "The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).\n",
    "\n",
    "The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.\n",
    "\n",
    "**Example:**\n",
    "```\n",
    "root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8\n",
    "\n",
    "      10\n",
    "     /  \\\n",
    "    5   -3\n",
    "   / \\    \\\n",
    "  3   2   11\n",
    " / \\   \\\n",
    "3  -2   1\n",
    "\n",
    "Return 3. The paths that sum to 8 are:\n",
    "\n",
    "1.  5 -> 3\n",
    "2.  5 -> 2 -> 1\n",
    "3. -3 -> 11\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        \n",
    "def constructtree(nodes, i, n):\n",
    "    root = None\n",
    "    if (i<n) and nodes[i] is not None:\n",
    "        root = TreeNode(nodes[i])\n",
    "        root.left = constructtree(nodes, 2*i+1, len(nodes))\n",
    "        root.right = constructtree(nodes, 2*i+2, len(nodes))\n",
    "    return root\n",
    "\n",
    "def printtree(root):\n",
    "    nodevals, level = [], []\n",
    "    q = [root]\n",
    "    while q:\n",
    "        level = q\n",
    "        q = []\n",
    "        while any(level):\n",
    "            node = level.pop(0)\n",
    "            if node:\n",
    "                nodevals.append(node.val)\n",
    "                if node.left or node.right or level:\n",
    "                    q.append(node.left)\n",
    "                    q.append(node.right)\n",
    "            else:\n",
    "                nodevals.append('null')\n",
    "    return nodevals\n",
    "\n",
    "tree1 = [10,5,-3,3,2,None,11,3,-2,None,1]\n",
    "root1 = constructtree(tree1, 0, len(tree1))\n",
    "sum1 = 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        \n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "soln = Solution()\n",
    "soln.pathSum(root1, sum1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 9: 8/9/20\n",
    "### 994. Rotting Oranges\n",
    "MEDIUM  \n",
    "https://leetcode.com/problems/rotting-oranges/  \n",
    "https://leetcode.com/explore/challenge/card/august-leetcoding-challenge/550/week-2-august-8th-august-14th/3418/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In a given grid, each cell can have one of three values:\n",
    "\n",
    "* the value `0` representing an empty cell;\n",
    "* the value `1` representing a fresh orange;\n",
    "* the value `2` representing a rotten orange.\n",
    "Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten.\n",
    "\n",
    "Return the minimum number of minutes that must elapse until no cell has a fresh orange.  If this is impossible, return `-1` instead.\n",
    "\n",
    "**Example 1:**\n",
    "![https://assets.leetcode.com/uploads/2019/02/16/oranges.png](https://assets.leetcode.com/uploads/2019/02/16/oranges.png)\n",
    "```\n",
    "Input: [[2,1,1],[1,1,0],[0,1,1]]\n",
    "Output: 4\n",
    "```\n",
    "**Example 2:**\n",
    "```\n",
    "Input: [[2,1,1],[0,1,1],[1,0,1]]\n",
    "Output: -1\n",
    "Explanation:  The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.\n",
    "```\n",
    "**Example 3:**\n",
    "```\n",
    "Input: [[0,2]]\n",
    "Output: 0\n",
    "Explanation:  Since there are already no fresh oranges at minute 0, the answer is just 0.\n",
    "```\n",
    "\n",
    "**Note:**\n",
    "\n",
    "1. `1 <= grid.length <= 10`\n",
    "2. `1 <= grid[0].length <= 10`\n",
    "3. `grid[i][j]` is only `0`, `1`, or `2`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "grid1 = [[2,1,1],[1,1,0],[0,1,1]]\n",
    "grid2 = [[2,1,1],[0,1,1],[1,0,1]]\n",
    "grid3 = [[0,2]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def orangesRotting(self, grid: List[List[int]]) -> int:\n",
    "        \n",
    "        def bfs(grid, x, y):\n",
    "            if y > len(grid) or x > len(grid[0]):\n",
    "                return \n",
    "            orange = grid[y][x]\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "soln = Solution()\n",
    "soln.orangesRotting(grid1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 10: 8/10/20\n",
    "### 171. Excel Sheet Column Number\n",
    "EASY  \n",
    "https://leetcode.com/problems/excel-sheet-column-number/  \n",
    "https://leetcode.com/explore/challenge/card/august-leetcoding-challenge/550/week-2-august-8th-august-14th/3419/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a column title as appear in an Excel sheet, return its corresponding column number.\n",
    "\n",
    "For example:\n",
    "```\n",
    "    A -> 1\n",
    "    B -> 2\n",
    "    C -> 3\n",
    "    ...\n",
    "    Z -> 26\n",
    "    AA -> 27\n",
    "    AB -> 28 \n",
    "    ...\n",
    "```\n",
    "**Example 1:**\n",
    "```\n",
    "Input: \"A\"\n",
    "Output: 1\n",
    "```\n",
    "**Example 2:**\n",
    "```\n",
    "Input: \"AB\"\n",
    "Output: 28\n",
    "```\n",
    "**Example 3:**\n",
    "```\n",
    "Input: \"ZY\"\n",
    "Output: 701\n",
    "```\n",
    "\n",
    "**Constraints:**\n",
    "\n",
    "* `1 <= s.length <= 7`\n",
    "* `s` consists only of uppercase English letters.\n",
    "* `s` is between \"A\" and \"FXSHRXW\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [],
   "source": [
    "s1 = 'A'\n",
    "s2 = 'AB'\n",
    "s3 = 'ZY' # 701\n",
    "s4 = 'AZY'# 1377?\n",
    "s5 = 'AAA'# 703"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [],
   "source": [
    "# basic pattern\n",
    "# 'ZZ' = 26*26+26\n",
    "# 'AA' = 26*1+1\n",
    "# 'AAA' = (26**2)*1+(26**1)*1+1\n",
    "# 'ZZZ' = (26**2)*26+(26**1)*26+26"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def titleToNumber(self, s: str) -> int:\n",
    "        ords = [ord(c)-64 for c in s]\n",
    "        ords = list(reversed(ords))\n",
    "        col = 0\n",
    "        for i in range(len(ords)):\n",
    "            col += (26**i)*ords[i]\n",
    "        return col"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "28"
      ]
     },
     "execution_count": 81,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "soln = Solution()\n",
    "soln.titleToNumber(s2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 11: 8/11/20\n",
    "### 274. H-Index\n",
    "MEDIUM  \n",
    "https://leetcode.com/problems/h-index/  \n",
    "https://leetcode.com/explore/challenge/card/august-leetcoding-challenge/550/week-2-august-8th-august-14th/3420/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.\n",
    "\n",
    "According to the [definition of h-index on Wikipedia](https://en.wikipedia.org/wiki/H-index): \"A scientist has index $h$ if $h$ of his/her $N$ papers have **at least** $h$ citations each, and the other $N$ − $h$ papers have no more than $h$ citations each.\"\n",
    "\n",
    "Example:\n",
    "```\n",
    "Input: citations = [3,0,6,1,5]\n",
    "Output: 3 \n",
    "Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had \n",
    "             received 3, 0, 6, 1, 5 citations respectively. \n",
    "             Since the researcher has 3 papers with at least 3 citations each and the remaining \n",
    "             two with no more than 3 citations each, her h-index is 3.\n",
    "```\n",
    "**Note:** If there are several possible values for $h$, the maximum one is taken as the h-index."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "citations1 = [3,0,6,1,5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "citations1 = [0,1,3,5,6] # 3\n",
    "citations2 = [0, 0, 1, 2, 7, 9] # 2\n",
    "citations3 = [3, 4, 5, 8, 10] # 4\n",
    "citations4 = [3, 3, 5, 8, 25] # 3\n",
    "citations5 = [0, 0, 1, 5, 7, 9] # 3\n",
    "citations6 = [0] # 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "# using sort\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        h = 0\n",
    "        citations = sorted(citations,reverse=True)\n",
    "        for i,c in enumerate(citations):\n",
    "            if c >= (i+1):\n",
    "                h = i+1\n",
    "        return h"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "# without sort, using hash table\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        counts = {}\n",
    "        maxc = max(citations)\n",
    "        \n",
    "        for c in citations:\n",
    "            if c in counts:\n",
    "                counts[c] += 1\n",
    "            else:\n",
    "                counts[c] = 1\n",
    "        total = 0\n",
    "        h = 0\n",
    "        for i in reversed(range(1,maxc+1)):\n",
    "            if i in counts:\n",
    "                total += counts[c]\n",
    "            if total >= i:\n",
    "                h = i\n",
    "                break\n",
    "                \n",
    "            \n",
    "        return h"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "soln = Solution()\n",
    "soln.hIndex(citations5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 13: 8/12/20\n",
    "### Pascal's Triangle II\n",
    "EASY  \n",
    "https://leetcode.com/problems/pascals-triangle-ii/  \n",
    "https://leetcode.com/explore/challenge/card/august-leetcoding-challenge/550/week-2-august-8th-august-14th/3421/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a non-negative index k where k ≤ 33, return the $k^{th}$ index row of the Pascal's triangle.\n",
    "\n",
    "Note that the row index starts from 0.\n",
    "![https://upload.wikimedia.org/wikipedia/commons/0/0d/PascalTriangleAnimated2.gif](https://upload.wikimedia.org/wikipedia/commons/0/0d/PascalTriangleAnimated2.gif)\n",
    "In Pascal's triangle, each number is the sum of the two numbers directly above it.\n",
    "\n",
    "**Example:**\n",
    "```\n",
    "Input: 3\n",
    "Output: [1,3,3,1]\n",
    "```\n",
    "**Follow up:**\n",
    "\n",
    "Could you optimize your algorithm to use only O(k) extra space?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "rowIndex1 = 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "# iterative solution\n",
    "class Solution:\n",
    "    def getRow(self, rowIndex: int) -> List[int]:\n",
    "        if rowIndex == 0:\n",
    "            row = [1]\n",
    "        elif rowIndex == 1:\n",
    "            row = [1,1]\n",
    "        else:  \n",
    "            ri = 1\n",
    "            oldrow = [1,1]\n",
    "            while ri < rowIndex:\n",
    "                ri += 1\n",
    "                row = [1]*(ri+1)\n",
    "                for i in range(1,len(oldrow)):\n",
    "                    row[i]=oldrow[i]+oldrow[i-1]\n",
    "                oldrow = row\n",
    "        return row"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "# iterative with O(k) space\n",
    "class Solution:\n",
    "    def getRow(self, rowIndex: int) -> List[int]:\n",
    "        row = [1]*(rowIndex+1)\n",
    "        ri = 0\n",
    "        while ri < rowIndex:\n",
    "            ri += 1\n",
    "            l = row[0]\n",
    "            for i in range(1,ri):\n",
    "                r = row[i]\n",
    "                row[i] = l+r\n",
    "                l = r\n",
    "        return row"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "# concise leetcode solution, maybe O(k) space?\n",
    "class Solution:\n",
    "    def getRow(self, rowIndex: int) -> List[int]:\n",
    "        row = [1]\n",
    "        for _ in range(rowIndex):\n",
    "            row = [x + y for x, y in zip([0]+row, row+[0])]\n",
    "        return row"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Study Notes:**\n",
    "* Pascal's triangle row is often expressed as $(n, k)$ with $n$ = row and $k$ = element\n",
    "* Each value also represents combinations of $k$ from $n$ items (n choose k)\n",
    "* Thus formula for n choose k can also represent the $k^{th}$ element in Pascal's triangle of row $n$:\n",
    "    * $\\dfrac{n!}{k!(n-k)!}$\n",
    "    * (formula also follows 0-indexing rule, where first row is n = 0 and first element is k = 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [],
   "source": [
    "# math solution\n",
    "import math\n",
    "class Solution:\n",
    "    def getRow(self, rowIndex: int) -> List[int]:\n",
    "        n = rowIndex\n",
    "        row = [1]*(n+1)\n",
    "        for k in range(rowIndex):\n",
    "            row[k] = int(math.factorial(n)/(math.factorial(k)*math.factorial(n-k)))\n",
    "        return row"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1]"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "soln = Solution()\n",
    "soln.getRow(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 13: 8/13/20\n",
    "### 1286. Iterator for Combination\n",
    "MEDIUM  \n",
    "https://leetcode.com/problems/iterator-for-combination/  \n",
    "https://leetcode.com/explore/challenge/card/august-leetcoding-challenge/550/week-2-august-8th-august-14th/3422/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Design an Iterator class, which has:\n",
    "\n",
    "* A constructor that takes a string `characters` of **sorted distinct** lowercase English letters and a number `combinationLength` as arguments.\n",
    "* A function *next()* that returns the next combination of length `combinationLength` in **lexicographical order**.\n",
    "* A function *hasNext()* that returns `True` if and only if there exists a next combination.\n",
    " \n",
    "\n",
    "**Example:**\n",
    "```\n",
    "CombinationIterator iterator = new CombinationIterator(\"abc\", 2); // creates the iterator.\n",
    "\n",
    "iterator.next(); // returns \"ab\"\n",
    "iterator.hasNext(); // returns true\n",
    "iterator.next(); // returns \"ac\"\n",
    "iterator.hasNext(); // returns true\n",
    "iterator.next(); // returns \"bc\"\n",
    "iterator.hasNext(); // returns false\n",
    "```\n",
    "\n",
    "**Constraints:**\n",
    "\n",
    "* `1 <= combinationLength <= characters.length <= 15`\n",
    "* There will be at most `10^4` function calls per test.\n",
    "* It's guaranteed that all calls of the function `next` are valid."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Study Notes:**\n",
    "* This is exactly what `combinations.itertools` does in the python builtin library\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {},
   "outputs": [],
   "source": [
    "# using python builtin\n",
    "from itertools import combinations\n",
    "class CombinationIterator:\n",
    "    def __init__(self, characters: str, combinationLength: int):\n",
    "        self.combs = combinations(characters,combinationLength)\n",
    "        self.buffer = next(self.combs,None) # returns next value in combinations iterator\n",
    "\n",
    "    def next(self) -> str:\n",
    "        if self.buffer:\n",
    "            res = ''.join(self.buffer)\n",
    "        else:\n",
    "            res = None\n",
    "        self.buffer = next(self.combs,None)\n",
    "        return res\n",
    "\n",
    "    def hasNext(self) -> bool:\n",
    "        return True if self.buffer else False\n",
    "\n",
    "\n",
    "# Your CombinationIterator object will be instantiated and called as such:\n",
    "# obj = CombinationIterator(characters, combinationLength)\n",
    "# param_1 = obj.next()\n",
    "# param_2 = obj.hasNext()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {},
   "outputs": [],
   "source": [
    "iterator = CombinationIterator(\"abc\", 2) # creates the iterator.\n",
    "\n",
    "iterator.next(); # returns \"ab\"\n",
    "iterator.hasNext(); # returns true\n",
    "iterator.next(); # returns \"ac\"\n",
    "iterator.hasNext(); # returns true\n",
    "iterator.next(); # returns \"bc\"\n",
    "iterator.hasNext(); # returns false"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 14: 8/14/20\n",
    "### 409. Longest Palindrome\n",
    "EASY  \n",
    "https://leetcode.com/problems/longest-palindrome/  \n",
    "https://leetcode.com/explore/challenge/card/august-leetcoding-challenge/550/week-2-august-8th-august-14th/3423/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.\n",
    "\n",
    "This is case sensitive, for example `\"Aa\"` is not considered a palindrome here.\n",
    "\n",
    "**Note:**  \n",
    "Assume the length of given string will not exceed 1,010.\n",
    "\n",
    "**Example:**\n",
    "```\n",
    "Input:\n",
    "\"abccccdd\"\n",
    "\n",
    "Output:\n",
    "7\n",
    "\n",
    "Explanation:\n",
    "One longest palindrome that can be built is \"dccaccd\", whose length is 7.\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [],
   "source": [
    "s1 = \"abccccdd\"\n",
    "s2 = 'abbacadabbra'\n",
    "s3 = 'abbabababbraa'\n",
    "s4 = \"civilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth\"\n",
    "s5 = \"abccccdd\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [],
   "source": [
    "# using only python primitive data structures\n",
    "class Solution:\n",
    "    def longestPalindrome(self, s: str) -> int:\n",
    "        letters = {}\n",
    "        for c in s:\n",
    "            if c in letters:\n",
    "                letters[c] += 1\n",
    "            else:\n",
    "                letters[c] = 1\n",
    "                \n",
    "        counts = sorted(letters.items(),key=lambda x: x[1],reverse=True)\n",
    "        length = 0\n",
    "        hasodd = False\n",
    "        for tup in counts:\n",
    "            count = tup[1]\n",
    "            if count%2==0:\n",
    "                length += count\n",
    "            elif count%2==1:\n",
    "                length += count-1\n",
    "                hasodd = True\n",
    "        \n",
    "        \n",
    "        return length+1 if hasodd else length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "soln = Solution()\n",
    "soln.longestPalindrome(s5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 15: 8/15/20\n",
    "### 435. Non-overlapping Intervals\n",
    "MEDIUM  \n",
    "https://leetcode.com/problems/non-overlapping-intervals/  \n",
    "https://leetcode.com/explore/challenge/card/august-leetcoding-challenge/551/week-3-august-15th-august-21st/3425/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.\n",
    "\n",
    "\n",
    "\n",
    "**Example 1:**\n",
    "```\n",
    "Input: [[1,2],[2,3],[3,4],[1,3]]\n",
    "Output: 1\n",
    "Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.\n",
    "```\n",
    "**Example 2:**\n",
    "```\n",
    "Input: [[1,2],[1,2],[1,2]]\n",
    "Output: 2\n",
    "Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.\n",
    "```\n",
    "**Example 3:**\n",
    "```\n",
    "Input: [[1,2],[2,3]]\n",
    "Output: 0\n",
    "Explanation: You don't need to remove any of the intervals since they're already non-overlapping.\n",
    "```\n",
    "\n",
    "**Note:**\n",
    "\n",
    "* You may assume the interval's end point is always bigger than its start point.\n",
    "* Intervals like [1,2] and [2,3] have borders \"touching\" but they don't overlap each other."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [],
   "source": [
    "intervals1 = [[1,2],[2,3],[3,4],[1,3]]\n",
    "intervals2 = [[1,2],[1,2],[1,2]]\n",
    "intervals3 = [[1,2],[2,3]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals = sorted(intervals, key=lambda x: x[0])\n",
    "        n = 0\n",
    "        if len(intervals)>1:\n",
    "            previ = intervals[0]\n",
    "            for i in intervals[1:]:\n",
    "                # check if intervals overlap\n",
    "                if previ[1]>i[0]:\n",
    "                    n += 1\n",
    "                    # choose which interval to keep as comparison\n",
    "                    if i[1] < previ[1]:\n",
    "                        previ = i # keep new interval only if it ends before previous interval\n",
    "                else:\n",
    "                    previ = i\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 76,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "soln = Solution()\n",
    "soln.eraseOverlapIntervals(intervals3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 16: 8/16/20\n",
    "### 123. Best Time to Buy and Sell Stock III\n",
    "HARD  \n",
    "https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/  \n",
    "https://leetcode.com/explore/challenge/card/august-leetcoding-challenge/551/week-3-august-15th-august-21st/3426/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Say you have an array for which the $i^{th}$ element is the price of a given stock on day $i$.\n",
    "\n",
    "Design an algorithm to find the maximum profit. You may complete at most *two* transactions.\n",
    "\n",
    "Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).\n",
    "\n",
    "**Example 1:**\n",
    "```\n",
    "Input: [3,3,5,0,0,3,1,4]\n",
    "Output: 6\n",
    "Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.\n",
    "             Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.\n",
    "```\n",
    "**Example 2:**\n",
    "```\n",
    "Input: [1,2,3,4,5]\n",
    "Output: 4\n",
    "Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.\n",
    "             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are\n",
    "             engaging multiple transactions at the same time. You must sell before buying again.\n",
    "```\n",
    "**Example 3:**\n",
    "```\n",
    "Input: [7,6,4,3,1]\n",
    "Output: 0\n",
    "Explanation: In this case, no transaction is done, i.e. max profit = 0.\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [],
   "source": [
    "prices1 = [3,3,5,0,0,3,1,4]\n",
    "prices2 = [1,2,3,4,5]\n",
    "prices3 = [7,6,4,3,1]\n",
    "prices4 = [2,5,7,1,4,3,1,3]\n",
    "prices5 = [1,2]\n",
    "prices6 = [106,373,495,46,359,919,906,440,783,583,784,73,238,701,972,308,165,774,990,675,737,990,713,157,211,880,961,132,980,136,285,239,628,221,948,939,28,541,414,180,171,640,297,873,59,814,832,611,868,633,101,67,396,264,445,548,257,656,624,71,607,67,836,14,373,205,434,203,661,793,45,623,140,67,177,885,155,764,363,269,599,32,228,111,102,565,918,592,604,244,982,533,781,604,115,429,33,894,778,885,145,888,577,275,644,824,277,302,182,94,479,563,52,771,544,794,964,827,744,366,548,761,477,434,999,86,1000,5,99,311,346,609,778,937,372,793,754,191,592,860,748,297,610,386,146,220,7,113,657,438,482,700,158,884,877,964,777,139,809,489,383,92,581,970,899,947,864,443,490,825,674,906,402,270,416,611,949,476,775,899,837,796,227,232,226,11,266,889,215,6,182,430,5,706,994,128,359,841,439,263,491,689,638,485,763,695,135,800,763,54,569,387,112,316,193,675,546,531,954,571,208,282,557,892,469,875,765,592,374,276,892,843,625,180,249,292,477,882,837,112,46,667,187,93,418,790,903,12,978,510,647,446,597,958,678,897,420,907,256,170,669,920,711,635,995,259,994,634,583,175,380,435,942,739,921,132,455,986,567,464,301,10,579,84,745,717,588,414,375,319,770,310,510,521,88,445,59,460,120,765,480,441,169,374,180,947,179,346,490,417,149,140,577,624,427,238,341,686,623,228,672,859,372,938,567,141,133,671,255,997,272,591,115,340,692,531,235,123,677,980,31,774,135,194,956,723,779,375,546,59,695,616,416,362,38,145,782,184,418,806,444,177,360,485,941,998,85,840,740,545,49,570,17,824,845,749,177,727,238,656,787,425,473,323,683,578,442,436,444,595,367,44,467,93,507,949,598,579,471,1,347,982,232,878,217,845,777,284,527,529,100,482,456,814,457,251,494,419,922,139,706,384,954,365,680,70,810,764,820,992,622,29,697,294,553,655,63,934,827,157,680,812,729,486,403,151,988,926,460,193,294,423,774,715,906,957,598,929,339,119,686,88,228,803,806,743,430,315,224,712,724,69,606,411,271,700,520,179,916,490,652,319,69,245,827,185,200,911,363,335,50,353,551,737,15,429,966,766,307,829,379,184,779,239,254,904,262,719,321,380,253,564,348,878,570,470,313,752,563,164,301,239,856,491,154,795,640,199,940,420,201,254,400,865,886,819,424,292,257,572,112,590,984,421,639,705,707,779,660,4,817,265,465,737,56,564,797,178,552,988,621,98,665,379,607,300,439,269,196,94,860,540,830,756,294,806,321,930,623,206,440,730,829,566,420,488,49,438,447,294,548,804,514,45,383,431,373,424,11,377,868,559,316,831,464,211,710,803,680,665,39,523,951,219,293,909,838,708,663,627,220,100,565,269,982,236,185,194,697,556,767,541,360,103,497,271,919,19,206,73,393,50,421,466,970,329,105,618,17,687,578,260,759,366,334,686,613,616,893,351,847,861,452,454,454,88,135,357,194,220,504,36,916,246,718,172,395,292,613,533,662,983,701,877,842,445,263,529,679,526,31,385,918,898,584,846,474,648,67,331,890,174,766,274,476,414,701,835,537,531,578,7,479,906,93,667,735,435,899,49,953,854,843,326,322,13,865,791,828,686,760,957,655,601,406,185,738,788,519,874,630,440,839,511,149,715,566,988,0,354,498,81,193,335,196,157,515,590,768,366,287,386,502,143,547,659,616,822,479,813,497,222,285,6,453,363,906,388,733,804,624,963,634,319,817,674,754,378,999,373,793,419,246,274,960,1,130,186,576,382,204,227,607,435,299,790,603,196,236,955,654,812,214,297,926,721,977,568,339,913,297,621,783,242,257,483,325,998,164,586,782,597,210,522,369,676,339,626,650,634,477,793,85,12,695,655,53,287,730,0,689,225,805,593,430,610,963,172,148,740,579,16,523,570,802,627,220,664,945,788,500,90,410,916,481,454,538,622,161,373,523,757,446,855,958,390,333,927,253,814,442,77,325,14,655,502,200,791,58,714,951,370,557,261,859,199,46,775,249,369,233,321,733,310,503,539,618,839,272,315,999,229,390,359,528,334,878,342,977,869,704,564,506,867,77,248,674,557,258,710,126,617,531,969,289,578,947,103,581,599,918,686,143,253,56,393,58,144,211,806,285,635,203,194,884,687,653,856,688,623,568,394,749,302,534,631,894,167,111,227,296,41,854,81,147,656,319,748,530,457,340,223,896,77,166,974,659,36,338,177,496,483,690,569,504,211,554,758,732,660,61,62,669,273,0,616,899,789,380,386,357,403,251,926,636,419,148,820,774,485,497,370,907,973,255,277,341,466,254,333,219,819,521,974,213,590,981,697,927,904,717,726,574,94,625,991,378,249,388,786,355,69,318,357,467,695,825,585,940,323,993,549,485,564,833,530,398,789,608,59,541,915,81,681,544,460,318,954,764,879,708,258,276,259,505,649,529,824,914,660,490,666,676,618,339,712,981,802,239,605,270,29,491,41,243,361,644,327,472,460,725,864,129,142,610,782,935,929,63,865,287,316,740,212,152,567,620,591,394,805,586,177,918,516,911,944,427,128,778,930,965,27,633,534,567,575,247,691,571,775,456,622,219,698,772,305,27,810,690,555,222,877,985,493,202,84,180,133,129,539,151,275,234,999,676,629,715,839,6,789,663,467,435,275,580,296,8,73,849,456,681,794,954,543,602,615,4,131,593,778,175,587,670,88,648,79,703,99,457,261,722,357,966,724,523,612,610,376,575,174,2,53,637,478,850,250,238,344,381,543,686,761,582,598,804,12,128,928,133,998,188,598,590,507,898,402,771,703,912,744,317,300,852,631,767,157,278,520,452,721,560,112,206,69,317,498,942,942,963,347,61,186,390,128,946,462,230,551,956,195,960,143,225,654,255,370,778,770,487,192,479,180,505,509,508,717,976,826,346,521,472,148,965,965,971,421,402,233,76,543,533,815,281,986,638,936,139,754,728,779,551,425,17,546,516,862,963,648,127,510,453,311,759,654,550,755,654,567,129,34,927,900,421,961,923,117,766,71,132,680,917,460,609,874,179,336,496,287,61,846,228,871,590,858,404,646,449,770,724,245,634,900,496,157,864,407,632,998,596,451,482,921,102,624,148,346,282,624,150,523,598,492,267,54,889,872,979,38,1,282,513,877,798,994,400,254,435,487,707,459,575,275,297,165,104,468,80,820,571,215,869,381,107,209,762,455,415,810,137,674,304,692,639,304,534,348,938,575,432,471,74,631,291,405,622,352,58,549,832,655,458,688,468,827,447,946,181,908,585,53,905,733,363,210,536,960,577,815,462,193,31,731,8,538,695,936,795,139,782,357,52,492,610,512,544,323,276,649,940,54,749,723,544,365,500,441,284,17,660,748,871,701,591,356,64,34,422,713,978,96,218,756,833,177,832,61,91,764,510,188,415,622,473,549,944,716,998,528,61,829,953,280,284,706,323,981,405,91,887,568,874,725,236,933,41,895,940,375,468,314,667,694,609,631,621,655,640,835,513,461,854,419,455,860,912,572,769,963,213,818,158,840,699,414,969,430,59,855,997,997,884,349,723,837,488,430,671,743,943,310,399,884,423,486,587,491,106,716,0,768,704,483,663,827,587,915,904,742,976,6,455,221,849,920,548,156,35,101,270,684,123,549,649,977,711,965,492,525,130,744,697,910,699,301,285,696,313,117,122,777,163,789,924,543,446,60,214,102,97,45,670,960,23,522,680,178,757,792,633,244,327,129,188,357,733,419,496,774,408,90,615,663,321,526,946,990,273,135,373,719,870,810,798,826,64,971,156,233,587,253,712,384,964,173,511,116,291,639,450,947,623,656,548,605,498,709,143,895,739,663,160,442,820,802,380,413,356,742,744,764,421,355,499,614,678,336,850,1000,463,794,388,478,188,576,822,164,209,465,901,116,729,891,952,611,15,798,731,711,6,459,587,278,996,220,642,563,363,271,16,379,959,332,315,414,659,602,786,571,78,450,544,393,404,953,480,215,771,419,8,738,36,191,138,204,146,923,413,908,998,46,928,678,425,584,372,689,245,721,177,833,44,784,121,164,16,714,680,974,685,340,810,101,301,791,716,697,768,33,901,994,417,353,248,559,807,64,450,724,896,889,880,818,89,495,848,915,450,409,958,413,149,743,782,64,687,196,737,769,311,429,598,585,690,919,331,94,211,633,888,856,844,870,931,934,66,407,121,902,417,522,423,821,196,625,855,830,673,463,181,857,775,374,490,971,751,835,823,770,79,916,80,829,810,856,674,524,352,251,548,899,363,465,0,989,322,51,86,740,542,920,310,365,677,287,688,373,225,774,331,430,482,630,46,567,236,370,502,347,191,137,646,218,634,399,278,423,540,26,612,700,43,508,176,268,525,267,676,257,651,88,349,556,6,463,29,410,753,224,693,535,747,40,854,155,376,192,434,12,342,98,718,639,951,205,923,354,564,988,960,676,965,29,104,898,535,915,868,768,269,294,944,523,145,895,382,53,935,671,518,338,623,524,204,146,900,161,258,739,417,119,825,336,182,123,749,355,188,109,740,945,826,921,123,65,69,682,461,259,661,247,523,796,153,142,851,411,536,190,478,417,296,113,158,263,754,532,368,748,42,890,129,643,717,564,525,5,348,204,383,427,696,861,684,902,591,609,467,837,104,565,168,828,916,645,232,153,794,384,642,753,550,176,142,132,141,192,635,14,634,329,403,790,460,29,512,443,15,74,114,456,487,303,13,822,429,136,113,637,283,542,519,411,564,220,346,907,389,780,479,480,179,385,285,445,393,508,885,697,168,542,357,553,149,710,126,508,271,845,689,231,217,984,848,905,87,168,1000,169,336,672,595,501,411,81,707,708,634,150,722,379,77,762,737,585,419,428,37,869,509,222,335,192,980,209,883,864,215,497,992,155,408,652,927,990,708,439,857,934,838,69,140,713,573,939,338,628,685,412,147,530,643,471,545,58,111,132,665,572,38,176,460,555,997,61,602,471,901,620,830,577,436,495,685,619,600,549,270,77,512,249,697,466,864,336,981,901,573,702,694,937,299,565,436,613,187,377,364,473,405,384,280,658,561,85,987,302,856,107,191,486,464,165,514,948,227,310,133,799,363,481,289,153,990,445,246,454,729,887,980,546,730,528,817,521,437,376,238,965,511,995,432,227,883,550,904,818,556,295,413,786,861,248,113,660,982,445,292,562,722,433,621,783,375,53,236,856,275,898,532,915,804,362,545,373,397,740,453,726,983,665,715,379,176,408,3,911,573,883,195,254,469,758,844,355,409,562,307,752,274,105,227,635,121,335,338,46,993,243,567,765,589,806,405,558,25,246,526,490,306,295,112,847,792,759,881,500,398,791,266,33,372,546,217,286,898,596,955,720,70,9,458,698,367,936,134,95,887,300,975,72,235,77,870,943,511,883,923,619,812,904,990,643,871,346,588,807,957,681,581,195,82,448,146,807,559,21,412,950,536,681,541,856,631,378,258,736,116,580,20,606,748,537,343,681,22,711,628,536,395,422,874,135,519,294,876,185,583,392,253,220,80,341,203,970,825,762,558,942,797,651,290,8,414,375,913,167,977,94,706,970,286,278,349,909,422,887,921,492,467,550,538,555,841,446,199,312,816,562,296,609,39,393,240,763,222,828,802,944,714,325,334,936,995,950,487,433,195,370,498,926,109,543,885,463,687,171,703,985,292,123,314,174,183,588,487,857,63,736,126,156,172,367,313,672,494,56,202,470,821,735,72,812,282,570,756,633,82,52,920,300,199,927,534,214,354,764,84,419,462,5,246,787,305,788,852,58,698,241,184,904,533,333,857,215,531,81,862,567,56,773,741,169,982,965,302,724,145,342,731,184,914,977,933,727,918,420,438,491,300,104,107,730,506,214,214,968,351,66,844,965,758,845,503,495,503,208,281,622,905,49,751,660,268,420,360,354,971,441,565,513,711,283,695,109,432,127,399,177,640,67,77,364,327,943,1000,979,278,526,222,929,120,753,580,743,456,241,148,339,599,919,11,473,101,365,789,465,819,778,134,278,89,598,801,904,681,695,599,43,897,763,193,257,719,410,610,58,72,912,598,793,347,640,725,855,390,754,785,70,449,24,962,843,735,729,893,797,512,390,57,474,336,855,970,389,722,735,464,28,894,664,645,96,357,255,117,795,479,151,790,432,748,780,940,255,204,607,999,989,48,139,945,783,736,826,640,597,171,423,457,972,424,419,140,706,333,648,557,155,707,547,337,66,338,818,829,972,13,500,310,961,668,991,407,386,893,589,308,129,739,689,452,361,822,418,606,961,981,385,132,7,938,102,942,534,154,133,921,51,257,205,281,771,215,508,816,466,744,85,141,163,418,894,386,779,142,137,825,556,764,647,414,792,605,945,36,427,173,907,356,893,875,449,621,181,963,801,14,502,234,495,437,86,635,846,182,182,540,340,648,772,195,93,539,716,573,431,342,989,156,745,436,709,22,532,100,504,0,985,838,461,725,555,219,710,568,914,736,791,507,615,442,494,977,546,519,389,614,78,172,991,255,154,243,495,876,267,948,657,692,46,107,864,168,785,965,740,16,878,713,79,517,68,208,621,13,362,99,379,109,823,960,645,440,944,342,710,267,656,646,639,453,155,867,456,606,328,444,136,89,104,650,36,240,320,31,352,522,520,260,510,981,591,655,668,23,544,320,541,707,133,708,809,972,196,59,383,642,153,993,837,98,300,751,564,399,848,325,903,534,662,201,690,300,404,115,104,600,236,752,651,640,244,254,40,549,304,86,600,755,59,662,106,290,368,725,138,705,28,550,955,277,959,346,721,759,569,420,424,59,989,438,867,725,544,178,575,137,21,536,72,617,194,421,226,378,483,880,688,791,930,97,831,113,711,445,308,813,967,120,769,329,718,899,364,638,308,644,25,138,88,732,922,721,850,835,367,831,292,651,966,268,628,925,205,824,429,917,534,323,887,3,302,134,904,300,678,929,491,229,671,817,442,678,879,373,664,990,53,395,738,570,497,113,322,557,341,641,331,932,830,433,590,738,780,50,446,504,743,311,980,88,224,732,316,664,742,69,146,801,334,41,198,629,690,869,598,612,662,385,637,769,984,316,741,980,2,794,814,730,297,503,734,836,604,674,376,692,277,727,455,975,703,115,25,552,404,460,543,738,86,488,356,929,668,835,222,413,172,221,1000,30,888,350,514,908,870,323,991,201,738,335,189,437,604,316,514,575,531,514,318,43,592,594,9,773,609,952,708,868,291,962,572,772,291,214,992,238,275,36,882,631,376,150,838,376,862,996,258,545,331,907,958,925,503,1,745,559,147,617,487,185,623,287,658,340,84,835,563,168,845,401,395,928,277,136,890,276,45,806,121,264,416,417,596,208,106,738,352,995,746,731,72,258,112,885,445,165,74,847,633,343,721,237,20,91,575,410,765,274,233,738,893,999,283,104,414,981,448,761,47,48,725,459,265,318,564,353,260,896,874,563,492,710,336,952,80,195,326,311,716,167,561,556,234,680,631,112,573,248,422,130,219,134,75,722,188,221,238,193,689,63,787,657,956,214,895,657,169,349,575,577,869,64,325,187,471,535,572,39,872,966,22,232,427,501,855,239,487,263,335,645,461,973,447,923,922,788,286,610,55,708,827,250,355,481,379,322,926,796,815,2,952,268,257,61,795,364,999,535,494,664,619,711,228,411,587,292,345,671,640,231,384,859,88,640,838,904,27,235,605,766,887,23,438,816,764,91,12,324,709,411,659,405,927,769,505,259,383,714,333,652,648,663,604,596,231,114,320,955,689,626,495,758,96,848,43,189,848,656,114,475,349,148,995,467,94,519,141,125,598,738,822,701,194,46,936,332,370,764,944,711,889,568,508,186,981,48,400,69,182,698,25,526,808,272,963,451,335,883,718,199,185,437,81,987,4,274,482,263,509,584,767,141,53,365,14,657,712,837,161,378,525,313,685,183,869,202,382,339,351,686,15,667,636,756,553,848,57,740,862,962,838,410,722,409,589,891,370,520,790,880,276,478,26,459,671,728,301,296,75,194,173,116,938,933,977,812,863,868,286,973,984,265,631,456,436,683,28,126,319,285,62,247,88,60,824,710,26,602,897,765,998,610,138,773,555,153,114,932,21,111,171,282,246,909,419,647,781,166,966,200,521,188,808,295,685,1000,890,353,301,983,862,527,974,241,705,437,523,213,704,421,225,428,310,255,719,243,962,757,27,476,181,138,95,309,122,500,846,627,371,470,759,255,373,520,748,856,459,71,431,782,307,524,644,130,120,56,406,387,435,201,7,392,922,503,578,331,827,954,21,351,869,65,300,697,908,505,315,198,744,892,510,307,985,129,634,773,343,640,702,748,973,594,271,151,254,513,339,843,425,153,19,309,489,333,944,442,904,447,239,487,6,230,988,656,716,488,779,362,738,663,516,432,964,142,823,353,175,797,645,613,553,26,41,946,47,479,181,964,901,251,843,715,211,366,335,16,103,547,171,276,29,165,993,424,274,334,754,982,63,963,904,150,342,301,238,152,314,892,498,958,192,806,208,681,703,970,688,5,809,705,182,230,658,531,793,303,475,825,924,538,488,100,655,524,569,655,430,808,820,402,852,760,691,751,779,868,247,688,545,780,350,400,550,307,577,803,527,302,916,984,829,257,172,392,41,233,241,587,159,176,904,926,540,324,918,177,817,585,722,89,987,476,637,210,980,905,911,547,762,490,197,718,774,982,484,781,675,152,144,412,255,800,480,901,892,309,382,873,469,662,375,499,646,436,410,866,440,708,613,842,663,604,555,133,77,458,66,660,504,635,896,621,126,995,506,7,283,11,610,11,727,667,101,589,309,240,508,368,830,805,4,259,936,39,510,645,772,993,530,932,393,19,82,915,994,853,683,183,797,61,292,942,434,846,265,316,991,751,579,182,162,454,5,194,97,451,906,177,761,988,314,425,5,63,127,565,427,774,66,195,627,731,750,586,874,599,878,759,807,192,9,971,279,127,424,357,671,573,451,104,51,105,699,375,99,775,421,490,968,442,965,492,974,639,584,647,676,186,586,730,345,617,337,256,477,985,847,681,689,696,893,198,631,509,662,813,33,137,808,412,165,97,698,309,276,670,364,939,595,125,663,384,582,775,262,978,256,928,783,275,651,657,240,759,522,354,609,400,487,57,269,251,927,953,700,591,186,287,873,511,768,269,880,767,487,518,812,434,154,299,203,664,316,14,688,350,15,51,383,550,736,903,420,727,313,789,110,300,675,435,334,243,887,503,30,878,322,859,670,77,219,972,156,539,775,234,469,887,441,444,108,688,856,805,358,634,699,855,741,949,119,996,103,676,289,382,722,337,307,301,389,213,663,131,987,573,748,151,655,117,637,566,802,226,888,672,259,740,769,627,880,709,877,995,264,379,310,485,133,73,511,50,326,239,931,187,502,459,661,263,446,370,911,260,153,89,285,254,563,293,981,218,507,304,102,702,294,335,147,242,529,158,677,617,58,590,835,734,453,292,41,285,357,161,98,166,378,338,436,469,760,448,582,266,242,356,140,222,711,879,285,435,724,631,509,379,685,757,534,787,682,755,786,978,351,339,27,282,436,302,403,396,817,66,792,371,916,858,742,611,426,123,992,761,936,206,946,974,615,158,117,314,343,277,748,545,584,39,913,319,444,927,787,880,293,108,962,706,679,884,728,783,920,994,763,540,768,545,6,561,369,608,335,695,791,271,768,686,844,982,606,23,379,259,943,956,459,358,434,606,794,985,424,939,116,508,998,48,582,927,150,310,402,764,913,749,304,446,755,928,236,572,566,600,451,659,660,651,224,959,70,449,191,883,984,396,904,837,763,475,53,344,703,86,707,528,715,853,327,447,163,389,379,497,385,673,915,407,756,630,921,700,423,546,224,170,23,595,113,854,445,397,466,885,24,854,765,259,951,139,897,629,226,938,182,963,168,198,428,613,925,103,516,491,580,857,539,19,21,426,147,417,299,785,375,198,984,480,131,358,31,925,764,75,963,140,725,681,501,154,204,626,822,775,378,396,988,756,60,598,965,738,617,492,566,264,640,912,4,554,474,524,371,730,638,452,679,776,353,799,381,188,603,328,528,120,24,835,350,737,572,759,220,329,813,93,896,502,44,351,862,825,914,868,575,911,25,414,956,566,247,761,921,901,317,93,466,719,251,9,434,26,735,754,602,402,956,702,295,144,833,564,459,664,447,791,731,325,945,904,787,704,265,91,790,587,120,514,521,325,215,985,859,861,190,721,969,16,641,638,713,274,495,272,701,20,319,933,979,19,824,753,323,924,162,534,786,18,834,269,626,800,490,944,571,782,842,578,225,264,345,481,369,636,158,390,92,777,622,662,115,939,515,692,95,398,696,146,606,554,214,637,776,996,241,730,755,596,247,258,112,703,643,142,663,729,27,962,737,930,222,199,595,188,184,287,120,135,352,625,486,684,465,261,246,574,744,212,28,266,491,651,843,652,80,796,412,545,912,311,913,447,180,540,108,578,742,216,140,881,679,767,528,987,233,241,376,285,845,722,381,319,139,118,779,727,741,388,284,677,163,81,453,612,495,479,408,493,159,545,956,806,802,269,140,748,110,734,621,334,614,395,74,972,840,118,613,48,962,460,318,278,637,334,787,766,373,417,672,430,490,232,626,745,721,219,133,958,181,875,209,199,637,886,908,495,311,547,365,141,292,233,453,292,941,703,38,487,63,408,394,876,460,582,270,553,169,63,789,753,4,601,828,591,627,886,411,354,863,758,18,173,92,147,170,572,951,727,252,97,207,742,185,906,713,324,706,129,744,400,897,201,801,913,225,937,981,526,925,655,611,901,582,302,329,98,365,887,926,829,332,425,887,188,809,222,293,552,553,604,554,399,95,442,941,82,95,250,602,282,932,953,400,245,997,456,789,783,856,172,739,323,440,928,961,161,926,700,281,28,767,740,981,798,836,655,431,98,862,28,624,110,417,446,11,17,784,757,160,124,40,655,17,411,162,933,425,890,27,529,739,398,385,449,827,688,959,723,148,916,814,638,642,560,361,134,115,659,204,376,260,337,184,413,354,510,704,325,241,538,588,977,31,936,805,486,237,546,70,458,947,150,683,990,673,57,47,803,208,508,452,396,169,838,492,706,532,878,685,200,111,261,564,403,340,31,526,779,326,329,640,990,863,334,506,28,521,489,981,515,451,803,742,486,248,716,967,622,774,938,378,180,195,853,663,699,865,589,856,27,971,687,483,230,517,845,279,882,535,166,937,43,648,756,40,12,76,338,501,714,287,973,766,47,489,633,56,248,718,430,431,237,620,725,567,648,253,51,63,382,146,28,830,409,286,628,657,828,129,256,902,249,738,84,90,128,979,864,839,582,57,611,278,534,844,977,819,98,840,203,169,461,564,299,270,282,327,721,748,759,164,883,885,924,772,622,997,944,627,821,277,224,890,680,494,313,298,990,583,790,842,455,352,966,878,878,741,765,742,951,593,828,662,150,702,359,61,394,428,368,939,948,528,890,262,432,982,898,160,822,68,27,853,9,964,208,382,881,257,653,189,701,20,861,693,560,945,225,907,94,899,489,605,788,545,621,532,222,478,551,376,16,984,907,426,548,386,249,418,298,399,60,309,578,637,443,233,619,135,415,465,664,560,42,674,463,306,573,153,593,558,32,708,910,124,890,52,296,514,823,172,459,821,833,409,460,363,745,658,290,50,607,912,127,595,563,193,802,238,439,23,741,729,793,402,325,671,766,669,517,374,318,468,489,639,136,553,31,448,740,834,114,313,879,721,16,778,503,716,55,806,14,876,429,380,223,646,487,160,922,653,159,379,18,970,68,840,383,505,776,912,461,251,707,634,803,821,47,650,865,851,311,206,449,48,859,192,337,634,991,515,78,331,190,747,210,320,469,45,299,376,491,449,948,194,579,824,470,543,632,131,807,535,824,696,266,106,65,701,90,457,502,929,745,660,592,319,280,45,218,977,853,365,562,864,890,551,788,27,849,295,29,670,872,554,77,80,105,524,11,123,707,376,269,883,316,263,650,80,590,767,793,943,948,396,753,786,227,1,973,53,984,116,795,551,273,141,288,836,450,501,459,574,536,730,398,660,213,211,501,94,336,272,100,582,356,874,51,921,745,853,980,714,360,102,479,26,988,68,701,965,635,641,95,812,727,253,464,155,784,911,997,746,652,431,402,104,12,417,401,796,71,459,64,214,834,525,319,160,718,188,228,270,309,910,630,389,826,759,680,506,928,749,58,670,933,918,84,329,421,410,860,280,238,986,873,928,120,486,257,310,579,436,950,164,143,393,535,280,187,122,713,703,345,560,913,568,529,197,172,358,6,140,781,0,525,275,755,504,429,58,8,460,444,883,151,971,992,694,707,595,745,236,470,925,527,427,331,163,903,739,455,430,485,485,60,552,743,3,771,335,448,863,675,107,99,255,105,397,702,317,171,863,497,653,313,158,668,975,425,417,981,188,172,141,946,688,276,389,969,86,198,893,771,547,153,875,203,963,463,553,92,160,348,37,401,599,370,394,537,698,676,38,927,755,3,333,814,361,763,583,974,778,342,473,277,690,34,84,393,612,178,414,342,576,628,863,321,1000,378,977,572,12,255,161,126,970,691,822,941,999,934,815,939,409,676,379,976,664,357,328,115,350,745,739,189,326,283,90,916,940,976,41,607,264,599,341,12,999,716,72,406,984,839,254,721,150,741,496,9,626,759,467,262,595,415,828,620,47,305,446,496,786,106,564,969,969,286,174,276,377,300,512,139,574,734,804,69,459,831,598,68,453,912,666,984,571,945,465,693,582,153,185,72,503,496,170,8,370,413,10,746,329,530,89,192,495,376,251,337,875,37,460,630,410,247,609,947,623,261,768,348,278,655,432,913,349,384,482,170,822,938,255,869,310,593,869,202,695,240,232,981,168,398,911,601,230,95,156,335,229,678,724,986,277,451,274,237,509,889,652,752,543,106,438,690,574,568,897,508,188,434,800,623,830,113,774,49,730,556,763,637,956,784,341,744,114,232,479,731,320,636,648,813,48,280,288,883,867,789,871,36,972,245,485,150,102,884,700,142,58,890,757,894,400,989,679,433,57,368,209,968,672,852,892,655,442,620,435,759,202,529,890,892,989,26,88,336,728,67,510,40,898,10,172,954,10,472,11,668,23,482,177,936,469,360,393,564,611,695,912,42,708,198,149,34,90,556,450,550,101,879,52,978,134,458,634,843,385,803,263,404,704,462,529,145,448,929,363,412,803,86,212,556,997,517,230,619,258,33,528,549,653,500,361,300,393,784,955,986,970,966,672,371,87,75,271,876,487,65,870,401,149,476,5,683,164,439,761,124,779,918,788,479,720,491,246,334,623,774,811,330,14,965,164,216,565,468,659,149,395,151,766,152,527,28,486,565,889,0,119,259,690,144,771,354,86,212,428,5,942,773,957,799,631,168,678,553,468,555,53,522,859,222,672,27,379,690,335,371,10,527,430,439,693,611,210,116,97,202,174,193,747,245,135,391,341,117,508,336,97,839,232,310,796,400,350,293,489,583,668,506,910,391,64,287,341,515,467,481,296,438,694,81,748,716,978,805,299,921,789,225,85,628,118,417,838,771,475,620,589,751,203,634,815,228,692,133,689,235,626,339,569,976,272,408,184,376,610,17,808,842,480,754,545,455,520,477,889,751,806,719,651,457,568,970,541,475,635,221,169,987,345,987,817,829,371,743,218,282,244,788,857,170,297,747,378,345,220,190,127,114,152,285,221,98,236,388,421,410,390,251,43,288,125,64,586,811,313,687,528,579,916,110,187,44,88,552,46,423,152,964,872,7,999,644,477,883,319,734,558,737,835,405,291,597,739,342,150,583,736,638,836,918,799,482,417,202,258,176,562,33,24,585,458,477,407,842,764,309,606,440,182,999,375,112,987,26,825,771,185,660,882,66,907,883,450,383,501,567,223,17,227,724,152,387,368,645,803,327,294,620,861,421,848,826,119,146,878,751,928,434,589,220,356,710,33,278,754,447,365,674,5,848,424,888,916,881,186,678,614,129,207,721,385,422,313,403,970,264,80,324,456,486,117,430,308,993,366,617,104,903,365,926,281,22,902,593,685,710,923,818,379,421,3,734,187,120,22,236,11,420,366,515,199,486,310,927,261,678,630,786,954,29,246,241,502,89,811,581,459,864,193,629,442,105,78,837,153,345,377,13,804,803,596,94,814,115,31,82,51,486,510,420,352,544,951,842,479,71,234,917,70,70,790,177,921,44,553,176,270,675,797,859,331,463,94,30,275,794,440,552,752,527,8,305,491,296,667,310,272,292,43,169,987,695,589,50,219,537,567,732,716,320,952,711,542,572,813,698,317,43,315,151,347,164,691,157,12,590,728,424,366,41,904,814,161,340,273,512,131,507,538,963,866,417,397,703,767,643,345,265,378,103,828,352,127,937,764,701,148,572,279,208,206,569,861,899,171,97,462,733,490,728,65,554,23,763,221,995,32,974,280,242,410,533,852,433,745,939,914,480,81,601,370,446,808,724,321,410,514,45,987,189,240,195,886,308,431,207,73,463,650,382,607,835,633,465,325,294,794,519,379,262,290,722,982,498,149,87,467,168,390,537,896,577,917,68,319,525,89,429,329,176,759,741,797,320,871,325,957,366,39,449,776,44,974,161,920,650,400,671,46,76,422,333,134,125,664,722,837,455,983,466,326,468,999,129,749,902,688,393,639,748,127,666,853,874,779,988,337,876,384,468,549,381,29,671,417,558,292,471,454,201,671,200,208,464,88,28,761,625,161,906,865,209,827,319,428,977,993,411,625,907,85,482,405,620,495,584,292,136,726,305,574,802,588,58,382,153,170,388,210,479,522,182,1000,323,952,97,972,164,874,963,536,375,331,216,756,526,513,110,34,247,824,356,90,908,389,217,684,1000,320,882,926,695,634,347,123,508,893,157,795,215,147,416,944,964,157,139,509,76,117,378,990,817,695,798,235,258,81,765,357,109,780,335,30,486,435,543,841,677,918,771,744,775,522,787,17,839,837,931,148,71,36,422,45,275,877,22,218,630,204,612,972,811,891,788,556,448,793,923,179,162,814,355,266,113,763,482,997,668,739,151,761,379,636,61,188,87,774,687,380,276,128,57,640,464,335,751,34,540,115,588,412,783,487,957,634,443,750,477,774,127,779,1,204,301,909,696,330,411,733,264,278,648,243,603,889,163,913,280,498,365,287,232,127,565,84,820,853,407,1,199,178,875,841,882,865,605,969,47,339,405,263,336,295,594,113,134,446,371,28,213,248,129,309,452,472,53,740,556,573,257,205,142,1000,101,251,150,368,632,16,289,557,759,948,280,993,146,980,149,348,592,932,953,621,191,710,311,940,325,556,338,773,1,188,310,706,325,708,639,77,959,434,474,698,980,658,144,199,316,191,800,325,389,927,587,292,678,624,401,237,974,465,105,34,643,685,260,317,320,891,541,557,661,365,152,693,160,171,386,564,986,191,915,119,3,505,5,132,432,420,49,31,858,365,670,429,149,350,208,885,819,95,676,465,625,103,394,326,645,502,289,350,454,925,870,427,510,668,552,978,551,343,5,259,687,779,447,158,170,65,50,835,826,988,93,36,14,495,904,516,523,672,154,992,884,907,912,380,354,81,595,133,120,45,486,916,884,403,46,173,663,947,359,221,871,956,51,227,65,546,878,273,904,279,655,500,660,284,75,525,921,257,384,367,504,17,62,742,92,459,861,798,242,60,984,172,235,97,528,720,537,676,942,326,654,61,782,562,418,609,259,745,983,726,457,347,957,440,112,152,888,360,141,555,423,432,845,827,140,593,80,870,95,10,400,104,861,470,405,403,971,538,972,918,892,467,173,712,471,578,408,559,723,952,857,798,987,476,418,240,959,496,802,795,835,607,701,158,816,180,567,975,496,542,876,54,722,646,418,78,49,858,191,935,42,127,222,574,37,636,47,557,535,294,202,679,930,575,415,602,71,425,645,132,421,363,889,719,32,23,415,477,107,357,495,552,3,501,986,766,985,556,353,963,464,867,728,669,637,309,575,500,666,967,842,135,270,176,831,683,283,700,897,127,927,116,61,934,874,403,405,483,73,662,365,997,114,160,859,537,687,23,685,329,589,483,318,602,420,265,589,406,899,881,201,931,848,144,524,345,61,102,216,928,832,269,387,549,866,552,803,367,676,877,175,304,701,395,918,886,909,949,593,497,689,619,830,868,599,559,564,597,944,19,810,773,370,932,84,755,342,814,840,569,273,685,129,685,756,305,709,506,679,724,783,47,607,197,869,318,43,409,41,773,153,560,589,655,184,764,936,976,259,545,660,597,302,294,582,791,1000,806,497,999,575,88,506,401,996,488,108,530,515,661,426,280,626,591,1000,531,884,620,523,566,74,775,871,167,163,275,385,451,407,511,2,471,628,265,757,523,77,532,731,671,61,821,17,491,292,279,326,678,275,413,647,156,935,554,465,442,692,469,645,175,48,852,694,283,997,400,282,574,381,149,471,196,701,730,339,767,459,779,997,641,691,908,255,268,880,788,89,467,840,571,424,373,75,930,435,20,331,833,118,540,434,452,297,129,384,852,946,265,362,459,240,658,438,608,856,448,540,587,973,91,675,44,132,297,721,545,351,298,605,801,127,31,178,872,51,65,867,981,723,823,374,506,948,759,795,328,803,416,98,91,498,224,528,402,48,413,461,391,71,518,595,658,846,123,7,979,848,69,797,425,12,183,778,493,364,479,35,132,513,938,554,802,765,181,644,336,484,932,264,940,42,484,661,348,354,410,191,219,7,639,487,68,725,822,565,297,221,699,572,339,366,540,576,147,622,554,274,281,544,774,762,538,270,61,690,274,582,637,885,721,864,239,646,386,746,276,473,777,658,881,97,529,975,736,29,897,620,151,564,384,344,371,823,470,494,751,488,591,762,606,731,985,398,16,855,271,860,26,458,986,542,621,585,752,599,725,516,206,64,235,48,374,357,551,17,159,708,275,340,845,519,743,84,385,587,623,7,148,157,361,65,435,47,49,118,254,536,274,92,800,185,873,920,979,436,549,807,85,346,637,183,259,962,941,948,211,710,275,448,947,796,604,578,596,547,296,272,665,90,933,157,663,839,189,919,613,605,868,10,913,449,85,534,924,28,883,427,979,100,948,282,1,368,988,716,136,406,746,766,122,899,135,782,778,884,323,18,480,627,789,366,141,180,440,44,907,53,975,260,997,393,621,405,112,14,423,152,582,324,708,42,362,395,106,923,37,494,551,73,726,471,941,796,507,8,117,293,489,880,177,48,760,994,875,844,469,653,101,814,544,58,771,890,781,298,745,119,798,952,152,12,174,907,113,191,12,305,233,753,778,439,724,119,719,554,870,189,510,121,173,539,788,609,261,199,187,725,91,867,561,914,95,488,924,179,898,262,117,866,265,213,903,444,754,657,173,144,262,642,523,927,632,121,68,128,717,107,37,922,667,579,347,313,586,485,410,7,130,754,755,22,605,787,11,193,701,15,114,580,86,88,417,826,461,915,321,974,421,521,285,957,786,802,66,28,117,904,258,996,337,441,717,188,318,127,480,280,953,953,889,541,288,109,809,181,926,888,111,303,414,263,94,326,642,416,987,742,24,35,950,888,55,165,903,169,690,986,175,938,623,734,212,824,108,597,181,168,858,471,745,226,467,427,226,143,552,62,255,350,280,554,158,335,685,588,827,484,882,196,170,318,264,212,687,369,548,550,112,895,599,676,605,105,862,934,688,729,949,843,806,341,523,168,576,455,204,709,648,999,78,662,712,712,969,206,43,559,636,705,699,761,571,703,823,377,359,429,161,498,18,933,990,450,653,771,510,146,88,90,859,657,525,78,886,852,610,353,586,207,898,140,823,470,63,458,747,221,585,169,879,699,794,592,529,495,370,857,419,796,913,416,360,535,170,726,743,195,912,971,937,649,880,766,301,481,484,868,163,194,790,345,210,30,342,556,714,512,398,297,912,121,856,832,858,19,454,532,531,672,438,366,500,234,672,977,417,629,87,171,512,53,968,782,517,99,352,475,128,6,439,115,388,535,815,547,188,982,179,761,778,58,296,623,692,563,820,481,410,581,147,784,315,774,857,549,828,659,959,798,956,888,345,736,630,433,611,853,828,726,614,942,988,184,289,494,36,37,790,470,896,842,800,803,648,180,944,906,867,696,47,948,647,40,842,555,676,38,651,389,659,518,655,12,278,980,380,694,930,619,867,854,710,279,113,768,557,827,914,317,301,53,832,665,222,229,672,182,514,586,938,177,608,287,243,281,236,956,86,247,744,416,387,871,909,594,673,377,366,765,839,244,588,502,724,930,280,185,743,64,648,527,15,116,517,876,370,246,347,441,546,283,95,304,849,574,125,116,13,295,198,546,460,335,680,616,670,53,551,978,806,775,565,169,719,291,64,31,780,706,702,164,397,330,426,708,773,583,465,258,673,958,681,389,986,863,823,435,406,961,454,107,799,615,318,884,52,705,65,845,484,579,246,363,46,286,217,190,262,138,260,181,307,733,469,754,12,417,854,315,268,171,145,837,667,600,83,222,537,913,962,817,419,184,537,611,972,972,886,593,791,253,239,377,37,967,301,661,608,122,177,33,368,577,543,221,319,624,673,919,879,27,609,618,742,860,682,702,115,589,642,140,102,869,522,440,927,440,284,942,307,631,294,771,234,913,447,708,603,68,601,683,842,210,292,711,322,647,246,749,159,799,385,393,857,630,36,542,523,992,421,406,5,835,396,535,708,659,816,943,760,773,162,587,913,957,383,972,138,929,644,348,63,708,596,142,277,395,361,524,876,647,413,717,241,527,287,338,662,441,546,274,39,404,806,598,23,638,180,725,497,462,180,332,444,998,205,108,6,898,203,226,832,93,478,142,152,747,476,374,783,239,123,888,553,40,158,940,720,676,855,520,415,188,91,91,242,573,292,372,9,441,790,605,39,505,476,657,836,252,504,397,303,731,723,115,181,903,802,657,746,821,40,982,549,898,859,459,573,772,165,436,196,958,706,860,201,371,428,331,220,117,765,753,271,84,544,226,700,22,926,180,96,829,515,315,706,547,243,46,396,315,652,776,895,989,65,582,901,282,684,676,915,882,653,539,969,693,1,651,244,500,65,49,830,988,250,974,352,904,422,182,530,568,152,345,657,777,920,927,18,672,974,273,923,181,171,673,35,62,648,169,691,409,283,508,554,764,408,478,200,623,241,940,113,579,284,854,493,231,779,435,237,194,692,444,538,726,728,511,108,115,869,922,98,294,311,703,723,800,286,970,994,434,973,980,704,746,283,824,26,780,463,446,407,761,178,887,375,256,290,624,243,327,398,390,482,227,660,482,816,254,951,82,235,860,5,545,121,882,766,513,399,79,675,433,738,924,149,68,878,71,597,680,648,664,390,736,979,834,45,465,724,851,567,732,182,958,530,302,435,102,944,989,366,832,632,76,93,252,2,244,945,522,336,751,230,415,331,855,506,726,496,663,662,862,447,417,272,486,63,280,618,686,713,468,723,512,78,119,338,665,278,634,186,506,896,345,281,124,826,217,494,652,982,418,825,918,714,299,308,800,260,793,365,989,873,396,110,576,533,690,734,635,235,743,356,792,508,313,866,512,888,827,127,727,805,711,826,134,64,729,623,79,313,776,245,896,43,669,143,935,450,463,967,337,242,169,849,755,262,790,661,165,863,744,797,979,86,432,67,202,813,244,112,54,844,327,106,708,892,535,667,870,740,150,695,329,987,39,168,54,553,192,581,478,324,569,145,536,911,549,880,884,994,367,997,138,606,236,547,452,250,683,23,596,172,598,865,972,528,243,442,560,342,840,643,221,174,282,746,779,686,709,657,623,258,770,793,364,770,9,456,459,623,739,524,209,997,974,386,635,547,790,849,703,489,493,132,132,389,869,727,405,182,25,887,361,447,483,483,226,94,408,938,89,546,296,497,551,704,152,816,955,674,856,594,598,711,766,336,852,258,653,849,322,209,895,596,684,286,12,547,392,263,60,548,772,562,391,772,757,994,656,468,520,667,329,600,612,222,528,601,721,832,954,918,33,381,9,27,95,328,623,163,783,854,313,635,943,25,619,121,676,993,115,614,651,76,157,744,834,190,298,127,66,733,949,616,750,598,313,968,784,884,653,111,108,833,995,981,661,856,506,276,519,345,801,822,818,17,921,691,225,688,952,915,50,532,401,412,258,193,752,757,890,714,156,157,20,371,43,723,426,976,725,54,212,132,251,288,33,237,944,945,451,105,595,937,120,896,372,367,300,251,760,366,907,390,977,518,527,724,749,593,984,450,206,31,70,734,543,986,944,965,180,8,933,148,936,84,441,557,167,689,412,378,642,29,179,324,209,9,955,750,486,719,784,147,200,791,484,292,337,925,882,179,347,694,656,5,420,135,23,825,627,884,943,627,41,412,664,32,190,150,89,914,961,952,906,453,568,348,840,296,632,672,164,209,77,743,994,965,787,616,288,58,722,459,400,361,800,210,680,885,707,361,966,843,703,679,469,883,627,927,391,66,896,668,569,675,151,706,446,194,11,562,85,621,335,170,548,438,455,821,363,861,466,673,560,430,737,216,403,401,895,559,589,434,561,188,313,846,36,956,119,161,90,353,594,530,204,544,652,433,625,270,886,802,207,437,438,918,406,710,308,463,68,856,560,26,399,238,302,324,405,794,488,194,737,711,409,451,920,599,184,693,165,153,76,501,139,583,646,845,347,262,72,246,645,541,135,385,251,632,983,474,342,188,500,155,927,21,743,268,354,694,904,992,520,175,697,363,647,2,692,308,355,721,161,590,104,497,305,177,493,531,486,918,634,821,46,952,313,843,915,376,478,325,19,399,541,425,561,381,885,836,143,582,174,868,406,608,813,951,122,812,269,816,88,220,847,94,754,265,169,413,12,728,327,118,832,499,369,285,944,246,953,182,205,357,463,884,142,220,32,639,84,902,275,827,389,828,982,913,554,105,849,226,45,154,239,856,526,359,730,180,344,541,478,354,990,991,636,1000,519,390,130,399,857,223,111,231,449,707,945,820,721,222,690,9,712,962,7,940,962,679,121,15,787,398,329,960,501,26,539,288,187,900,200,414,338,399,513,602,661,459,460,198,815,53,161,891,264,412,989,646,248,704,383,646,88,199,297,443,32,100,66,689,463,958,325,788,981,247,172,96,477,456,142,92,288,231,429,325,73,422,977,807,504,572,285,719,977,54,806,118,455,532,479,50,343,871,333,561,472,995,197,609,314,936,440,102,815,853,911,716,260,679,740,384,46,226,590,383,100,283,935,104,876,896,507,901,281,807,679,963,877,198,234,655,474,723,975,265,540,729,108,685,404,460,635,237,788,488,344,665,704,644,65,56,989,131,115,769,350,738,982,580,641,883,545,328,290,290,684,313,413,198,73,395,656,428,692,236,919,983,649,429,875,319,819,740,680,816,781,60,569,509,938,566,614,551,560,881,716,601,5,540,826,78,86,635,438,124,0,867,59,561,837,870,420,326,948,748,592,168,967,894,753,148,202,689,21,336,350,726,804,301,699,898,111,817,229,549,873,362,475,518,579,529,4,800,763,489,929,936,300,759,981,145,290,324,352,0,498,350,215,592,806,963,299,400,422,642,672,211,561,20,945,398,715,23,6,548,121,851,326,292,180,648,400,120,386,473,53,213,835,469,70,610,300,625,632,771,312,379,599,837,653,422,888,155,387,620,235,426,840,760,162,136,793,509,562,562,62,409,857,559,746,922,936,553,41,396,609,681,5,680,984,128,257,335,160,271,105,767,258,609,425,699,505,274,640,293,841,297,849,31,12,462,395,712,117,341,326,390,887,921,421,513,230,554,834,307,436,611,204,580,794,222,733,734,145,102,861,776,131,214,440,755,515,671,590,305,768,118,670,884,506,12,597,170,960,657,353,188,19,638,432,674,414,880,353,395,37,722,830,919,808,117,390,316,178,840,489,268,377,479,933,246,547,887,73,729,54,686,818,386,662,683,91,223,274,28,880,526,329,762,212,886,121,510,857,965,653,932,632,799,486,898,516,349,846,733,28,629,776,776,173,817,127,672,875,930,330,236,912,137,97,771,824,657,477,835,988,136,408,835,174,705,726,296,70,720,403,321,360,170,200,808,642,993,322,299,238,549,868,954,664,765,590,715,221,628,538,631,572,40,950,284,275,528,828,11,426,155,730,847,18,267,831,243,602,947,559,853,391,308,603,446,792,620,877,9,720,668,818,91,459,390,812,777,410,64,92,251,613,654,164,688,400,776,189,694,700,553,853,988,708,776,214,590,293,320,597,515,358,893,822,704,254,281,802,351,209,933,407,299,739,474,142,76,206,55,270,457,522,355,542,418,321,283,234,893,479,337,806,686,597,623,421,360,373,45,834,885,6,253,684,794,942,51,613,176,488,830,902,400,704,427,271,335,840,838,933,528,623,278,882,584,794,51]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Study Notes**\n",
    "* \"buy\" variables can be conceptually thought of as \"net buy\" cost\n",
    "    * `secondbuy` is more accurately the cost of buying stock on day *i* factoring in profits from `firstprofit`\n",
    "    * can be negative when cost of re-acquiaring stock is less than the profit earned from a previous sale"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "# non-dp solution for exactly two transactions by tracking first and second buy/profit vars\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        firstbuy, secondbuy = 9999, 9999 # arbitrarily high value\n",
    "        firstprofit, secondprofit = 0, 0\n",
    "        for p in prices:\n",
    "            firstbuy = min(firstbuy,p)\n",
    "            firstprofit = max(firstprofit,p-firstbuy)\n",
    "            secondbuy = min(secondbuy,p-firstprofit)\n",
    "            secondprofit = max(secondprofit,p-secondbuy)\n",
    "        return secondprofit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Study Notes:**\n",
    "* extending previous solution into a dp bottom up problem \n",
    "* dp array structure: `dp[i][2*k]`\n",
    "    * i = \"day\" of transaction (*note:* is len(prices)+1!!)\n",
    "    * k = # of transactions\n",
    "    * k = 0: \"first buy\"\n",
    "    * k>0 and k%2==0 \"Xth buy\", where x >= 1\n",
    "    * k>0 and k%2==1 \"Xth profit\", where x >= 1\n",
    "* concept: turn \"firstbuy\", \"firstprofit\", \"secondbuy\", \"secondprofit\", etc. into columns of dp array and iterate"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        maxi = len(prices)+1\n",
    "        maxk = 2*k\n",
    "        if (maxk == 0) or (len(prices)<2):\n",
    "            return 0\n",
    "        # special case if 2k>len(prices), just calculate solution assuming unlimited transactions\n",
    "        if (maxk >= len(prices)):\n",
    "            maxprofit = 0\n",
    "            prevp = prices[0]\n",
    "            for p in prices[1:]:\n",
    "                profit = p-prevp\n",
    "                if profit > 0:\n",
    "                    maxprofit += profit\n",
    "                prevp = p\n",
    "            return maxprofit\n",
    "            \n",
    "        \n",
    "        # make dp array\n",
    "        dp = [[0]*(maxk) for i in range(maxi)]\n",
    "        \n",
    "        # initialize buy/profit values\n",
    "        for k in range(maxk):\n",
    "            if k%2==0:\n",
    "                dp[0][k]=99 # arbitrary high value\n",
    "        \n",
    "        # iterate through days, calculating profits\n",
    "        # NOTE: prices[i] corresponds with dp[i-1]\n",
    "        for i in range(1,maxi):\n",
    "            for k in range(maxk):\n",
    "                if k == 0: # first buy\n",
    "                    dp[i][k] = min(dp[i-1][k], prices[i-1]) # first buy\n",
    "                elif k%2==0: # non-first buy\n",
    "                    dp[i][k] = min(dp[i-1][k], prices[i-1]-dp[i][k-1])\n",
    "                elif k%2==1: # profit\n",
    "                    dp[i][k] = max(dp[i-1][k], prices[i-1]-dp[i][k-1])\n",
    "        \n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 78,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "soln = Solution()\n",
    "soln.maxProfit(9,prices4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Study Notes:**\n",
    "* solution from leetcode\n",
    "* dp array structure: `dp[i][j]`\n",
    "    * $i$ = # of transactions\n",
    "    * $j$ = # of days\n",
    "    * max of two choices: sell or not\n",
    "        * not sell = `dp[i][j-1]` # simply the value of the dp array from previous day\n",
    "        * sell = `prices[j]-prices[m] + dp[i-1][m]` # second quantity is the total profit from the previous sale\n",
    "        * m = some previous day from `0...j-1` that results in the max profit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "# generalized dp solution for max of k transactions\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int], k: int) -> int:\n",
    "        dp = []\n",
    "        \n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "soln = Solution()\n",
    "soln.maxProfit(prices5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 17: 8/17/20\n",
    "### 1103. Distribute Candies to People\n",
    "EASY  \n",
    "https://leetcode.com/problems/distribute-candies-to-people/  \n",
    "https://leetcode.com/explore/challenge/card/august-leetcoding-challenge/551/week-3-august-15th-august-21st/3427/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We distribute some number of `candies`, to a row of `n = num_people` people in the following way:\n",
    "\n",
    "We then give 1 candy to the first person, 2 candies to the second person, and so on until we give n candies to the last person.\n",
    "\n",
    "Then, we go back to the start of the row, giving `n + 1` candies to the first person, `n + 2` candies to the second person, and so on until we give `2 * n` candies to the last person.\n",
    "\n",
    "This process repeats (with us giving one more candy each time, and moving to the start of the row after we reach the end) until we run out of candies.  The last person will receive all of our remaining candies (not necessarily one more than the previous gift).\n",
    "\n",
    "Return an array (of length `num_people` and sum `candies`) that represents the final distribution of candies.\n",
    "\n",
    " \n",
    "\n",
    "**Example 1:**\n",
    "```\n",
    "Input: candies = 7, num_people = 4\n",
    "Output: [1,2,3,1]\n",
    "Explanation:\n",
    "On the first turn, ans[0] += 1, and the array is [1,0,0,0].\n",
    "On the second turn, ans[1] += 2, and the array is [1,2,0,0].\n",
    "On the third turn, ans[2] += 3, and the array is [1,2,3,0].\n",
    "On the fourth turn, ans[3] += 1 (because there is only one candy left), and the final array is [1,2,3,1].\n",
    "```\n",
    "**Example 2:**\n",
    "```\n",
    "Input: candies = 10, num_people = 3\n",
    "Output: [5,2,3]\n",
    "Explanation: \n",
    "On the first turn, ans[0] += 1, and the array is [1,0,0].\n",
    "On the second turn, ans[1] += 2, and the array is [1,2,0].\n",
    "On the third turn, ans[2] += 3, and the array is [1,2,3].\n",
    "On the fourth turn, ans[0] += 4, and the final array is [5,2,3].\n",
    "```\n",
    "\n",
    "**Constraints:**\n",
    "\n",
    "* 1 <= candies <= 10^9\n",
    "* 1 <= num_people <= 1000"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "candies1,num_people1 = 7, 4\n",
    "candies2,num_people2 = 10, 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def distributeCandies(self, candies: int, num_people: int) -> List[int]:\n",
    "        gift,n = 0, 0\n",
    "        res = [0]*num_people\n",
    "        while candies > 0:\n",
    "            gift += 1\n",
    "            # distribute candy\n",
    "            if gift <= candies:\n",
    "                candies -= gift\n",
    "                res[n] += gift\n",
    "            else:\n",
    "                res[n] += candies\n",
    "                candies = 0\n",
    "            \n",
    "            # increment index\n",
    "            n = n+1 if n<(num_people-1) else 0\n",
    "                \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[5, 2, 3]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "soln = Solution()\n",
    "soln.distributeCandies(10,3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 18: 8/19/20\n",
    "### 824. Goat Latin\n",
    "EASY    \n",
    "https://leetcode.com/problems/goat-latin/  \n",
    "https://leetcode.com/explore/challenge/card/august-leetcoding-challenge/551/week-3-august-15th-august-21st/3429/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A sentence `S` is given, composed of words separated by spaces. Each word consists of lowercase and uppercase letters only.\n",
    "\n",
    "We would like to convert the sentence to \"*Goat Latin*\" (a made-up language similar to Pig Latin.)\n",
    "\n",
    "The rules of Goat Latin are as follows:\n",
    "\n",
    "* If a word begins with a vowel (a, e, i, o, or u), append `\"ma\"` to the end of the word.\n",
    "For example, the word 'apple' becomes 'applema'.\n",
    " \n",
    "* If a word begins with a consonant (i.e. not a vowel), remove the first letter and append it to the end, then add `\"ma\"`.  \n",
    "For example, the word `\"goat\"` becomes `\"oatgma\"`.\n",
    " \n",
    "* Add one letter `'a'` to the end of each word per its word index in the sentence, starting with 1.\n",
    "For example, the first word gets `\"a\"` added to the end, the second word gets `\"aa\"` added to the end and so on.\n",
    "\n",
    "Return the final sentence representing the conversion from S to Goat Latin. \n",
    "\n",
    " \n",
    "\n",
    "**Example 1:**\n",
    "```\n",
    "Input: \"I speak Goat Latin\"\n",
    "Output: \"Imaa peaksmaaa oatGmaaaa atinLmaaaaa\"\n",
    "```\n",
    "**Example 2:**\n",
    "```\n",
    "Input: \"The quick brown fox jumped over the lazy dog\"\n",
    "Output: \"heTmaa uickqmaaa rownbmaaaa oxfmaaaaa umpedjmaaaaaa overmaaaaaaa hetmaaaaaaaa azylmaaaaaaaaa ogdmaaaaaaaaaa\"\n",
    "```\n",
    "\n",
    "**Notes:**\n",
    "\n",
    "* `S` contains only uppercase, lowercase and spaces. Exactly one space between each word.\n",
    "* `1 <= S.length <= 150`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "S1 = \"I speak Goat Latin\" # \"Imaa peaksmaaa oatGmaaaa atinLmaaaaa\"\n",
    "S2 = \"The quick brown fox jumped over the lazy dog\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def toGoatLatin(self, S: str) -> str:\n",
    "        if not S:\n",
    "            return ''\n",
    "        \n",
    "        vowels = {'a','e','i','o','u'}\n",
    "        words = S.split()\n",
    "        result = ''\n",
    "        a = 'a'\n",
    "        for w in words:\n",
    "            if w[0].lower() in vowels:\n",
    "                tw = w+'ma'+a\n",
    "            else:\n",
    "                tw = w[1:]+w[0]+'ma'+a\n",
    "            a+='a'\n",
    "            result += tw+' '\n",
    "        return result.strip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'heTmaa uickqmaaa rownbmaaaa oxfmaaaaa umpedjmaaaaaa overmaaaaaaa hetmaaaaaaaa azylmaaaaaaaaa ogdmaaaaaaaaaa'"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "soln = Solution()\n",
    "soln.toGoatLatin(S2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 20: 8/20/20\n",
    "### 143. Reorder List\n",
    "MEDIUM  \n",
    "https://leetcode.com/problems/reorder-list/  \n",
    "https://leetcode.com/explore/challenge/card/august-leetcoding-challenge/551/week-3-august-15th-august-21st/3430/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a singly linked list L: $L_0$→$L_1$→…→$L_{n-1}$→$L_n$,\n",
    "reorder it to: $L_0$→$L_n$→$L_1$→$L_{n-1}$→$L_2$→$L_{n-2}$→…\n",
    "\n",
    "You may **not** modify the values in the list's nodes, only nodes itself may be changed.\n",
    "\n",
    "**Example 1:**\n",
    "```\n",
    "Given 1->2->3->4, reorder it to 1->4->2->3.\n",
    "```\n",
    "**Example 2:**\n",
    "```\n",
    "Given 1->2->3->4->5, reorder it to 1->5->2->4->3.\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class ListNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.next = None\n",
    "\n",
    "# nodes\n",
    "n0 = ListNode(1)\n",
    "n1 = ListNode(2)\n",
    "n2 = ListNode(3)\n",
    "n3 = ListNode(4)\n",
    "n5 = ListNode(1)\n",
    "n6 = ListNode(2)\n",
    "n7 = ListNode(3)\n",
    "n8 = ListNode(4)\n",
    "n9 = ListNode(5)\n",
    "n10 = ListNode(1)\n",
    "\n",
    "# list 1\n",
    "n0.next = n1\n",
    "n1.next = n2\n",
    "n2.next = n3\n",
    "\n",
    "# list 2\n",
    "n5.next = n6\n",
    "n6.next = n7\n",
    "n7.next = n8\n",
    "n8.next = n9\n",
    "\n",
    "\n",
    "head1 = n0\n",
    "head2 = n5\n",
    "head3 = n10\n",
    "head4 = None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# two pass solution, ending when iterating halfway through nodes list\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        # first pass to add nodes to array\n",
    "        nodes = []\n",
    "        curnode = head\n",
    "        while curnode:\n",
    "            nodes.append(curnode)\n",
    "            curnode = curnode.next\n",
    "            \n",
    "        # second pass to reorder list based on index\n",
    "        for i in range(0,len(nodes)):\n",
    "            # assign pointers to nodes to reassign\n",
    "            curnode = nodes[i]\n",
    "            nextnode = curnode.next\n",
    "            reversenode = nodes[len(nodes)-1-i]\n",
    "            # reorder nodes\n",
    "            curnode.next = reversenode\n",
    "            reversenode.next = nextnode\n",
    "            # move pointers if end criteria not met\n",
    "            if i+1 >= len(nodes)//2: # end loop if it reaches endingnode\n",
    "                if nextnode:\n",
    "                    nextnode.next = None\n",
    "                break\n",
    "            else:\n",
    "                curnode = nodes[i+1]\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# two pass solution, using nodes list as a queue\n",
    "# optimization: use collections.deque instead of list for queue\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def reorderList(self, head: ListNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        \"\"\"\n",
    "        # first pass to add nodes to array\n",
    "        nodes = deque()\n",
    "        curnode = head\n",
    "        while curnode:\n",
    "            nodes.append(curnode)\n",
    "            curnode = curnode.next\n",
    "            \n",
    "        # second pass using nodes as queue to reorder linked list\n",
    "        while nodes:\n",
    "            # assign pointers to nodes to reassign\n",
    "            curnode = nodes.popleft() # nodes.pop(0) for list\n",
    "            nextnode = curnode.next\n",
    "            reversenode = None\n",
    "            if nodes:\n",
    "                reversenode = nodes.pop() # nodes.pop(-1) to be explicit\n",
    "                # reorder nodes\n",
    "                curnode.next = reversenode\n",
    "                reversenode.next = nextnode\n",
    "            # check for end conditions\n",
    "            if reversenode is None: # if node count is odd\n",
    "                curnode.next = None\n",
    "            elif reversenode == nextnode: # if node count is even\n",
    "                reversenode.next = None\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "3\n",
      "5\n",
      "4\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "inputnode = head2\n",
    "soln = Solution()\n",
    "soln.reorderList(inputnode)\n",
    "\n",
    "ans = inputnode\n",
    "while ans:\n",
    "    print(ans.val)\n",
    "    ans = ans.next"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 21: 8/21/20\n",
    "### 905. Sort Array By Parity\n",
    "EASY  \n",
    "https://leetcode.com/problems/sort-array-by-parity/  \n",
    "https://leetcode.com/explore/challenge/card/august-leetcoding-challenge/551/week-3-august-15th-august-21st/3431/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given an array `A` of non-negative integers, return an array consisting of all the even elements of `A`, followed by all the odd elements of `A`.\n",
    "\n",
    "You may return any answer array that satisfies this condition.\n",
    "\n",
    " \n",
    "\n",
    "**Example 1:**\n",
    "```\n",
    "Input: [3,1,2,4]\n",
    "Output: [2,4,3,1]\n",
    "The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.\n",
    "```\n",
    " \n",
    "\n",
    "**Note:**\n",
    "\n",
    "* `1 <= A.length <= 5000`\n",
    "* `0 <= A[i] <= 5000`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [],
   "source": [
    "A1 = [3,1,2,4]\n",
    "A2 = [0,1]\n",
    "A3 = [2,5,7,8,9]\n",
    "A4 = [2,4,5,9,6]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def sortArrayByParity(self, A: List[int]) -> List[int]:\n",
    "        result = []\n",
    "        for n in A:\n",
    "            if n%2==0:\n",
    "                result.insert(0,n)\n",
    "            else:\n",
    "                result.append(n)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "# faster in-place using pointers\n",
    "class Solution:\n",
    "    def sortArrayByParity(self, A: List[int]) -> List[int]:\n",
    "        firstodd = 0\n",
    "        for i in range(len(A)):\n",
    "            if A[i] % 2 == 0:\n",
    "                A[firstodd], A[i] = A[i], A[firstodd]\n",
    "                firstodd += 1\n",
    "        return A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 4, 6, 9, 5]"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "soln = Solution()\n",
    "soln.sortArrayByParity(A4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 22: 8/22/20\n",
    "### 497. Random Point in Non-overlapping Rectangles\n",
    "MEDIUM  \n",
    "https://leetcode.com/problems/random-point-in-non-overlapping-rectangles/  \n",
    "https://leetcode.com/explore/challenge/card/august-leetcoding-challenge/552/week-4-august-22nd-august-28th/3433/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a list of **non-overlapping** axis-aligned rectangles `rects`, write a function pick which randomly and uniformily picks an **integer point** in the space covered by the rectangles.\n",
    "\n",
    "**Note:**\n",
    "\n",
    "1. An **integer point** is a point that has integer coordinates. \n",
    "2. A point on the perimeter of a rectangle is included in the space covered by the rectangles. \n",
    "3. `i`th rectangle = `rects[i] = [x1,y1,x2,y2]`, where `[x1, y1]` are the integer coordinates of the bottom-left corner, and `[x2, y2]` are the integer coordinates of the top-right corner.\n",
    "4. length and width of each rectangle does not exceed `2000`.\n",
    "5. `1 <= rects.length <= 100`\n",
    "6. `pick` return a point as an array of integer coordinates `[p_x, p_y]`\n",
    "7. `pick` is called at most `10000` times.\n",
    "\n",
    "**Example 1:**\n",
    "```\n",
    "Input: \n",
    "[\"Solution\",\"pick\",\"pick\",\"pick\"]\n",
    "[[[[1,1,5,5]]],[],[],[]]\n",
    "Output: \n",
    "[null,[4,1],[4,1],[3,3]]\n",
    "```\n",
    "**Example 2:**\n",
    "```\n",
    "Input: \n",
    "[\"Solution\",\"pick\",\"pick\",\"pick\",\"pick\",\"pick\"]\n",
    "[[[[-2,-2,-1,-1],[1,0,3,0]]],[],[],[],[],[]]\n",
    "Output: \n",
    "[null,[-1,-2],[2,0],[-2,-1],[3,0],[-2,-2]]\n",
    "```\n",
    "**Explanation of Input Syntax:**\n",
    "\n",
    "The input is two lists: the subroutines called and their arguments. `Solution`'s constructor has one argument, the array of rectangles `rects`. `pick` has no arguments. Arguments are always wrapped with a list, even if there aren't any."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "input1 = [[[[1,1,5,5]]],[],[],[]]\n",
    "input2 = [[[[-2,-2,-1,-1],[1,0,3,0]]],[],[],[],[],[]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "\n",
    "    def __init__(self, rects: List[List[int]]):\n",
    "        \n",
    "        return None\n",
    "\n",
    "    def pick(self) -> List[int]:\n",
    "        \n",
    "        return None\n",
    "# Your Solution object will be instantiated and called as such:\n",
    "# obj = Solution(rects)\n",
    "# param_1 = obj.pick()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "soln = Solution(input1[0])\n",
    "for _ in input1[1:]:\n",
    "    soln.pick()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 23: 8/23/20\n",
    "### 1032. Stream of Characters\n",
    "HARD  \n",
    "https://leetcode.com/problems/stream-of-characters/  \n",
    "https://leetcode.com/explore/challenge/card/august-leetcoding-challenge/552/week-4-august-22nd-august-28th/3434/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Implement the `StreamChecker` class as follows:\n",
    "\n",
    "* `StreamChecker(words)`: Constructor, init the data structure with the given words.\n",
    "* `query(letter)`: returns true if and only if for some `k >= 1`, the last `k` characters queried (in order from oldest to newest, including this letter just queried) spell one of the words in the given list.\n",
    " \n",
    "\n",
    "**Example:**\n",
    "```\n",
    "StreamChecker streamChecker = new StreamChecker([\"cd\",\"f\",\"kl\"]); // init the dictionary.\n",
    "streamChecker.query('a');          // return false\n",
    "streamChecker.query('b');          // return false\n",
    "streamChecker.query('c');          // return false\n",
    "streamChecker.query('d');          // return true, because 'cd' is in the wordlist\n",
    "streamChecker.query('e');          // return false\n",
    "streamChecker.query('f');          // return true, because 'f' is in the wordlist\n",
    "streamChecker.query('g');          // return false\n",
    "streamChecker.query('h');          // return false\n",
    "streamChecker.query('i');          // return false\n",
    "streamChecker.query('j');          // return false\n",
    "streamChecker.query('k');          // return false\n",
    "streamChecker.query('l');          // return true, because 'kl' is in the wordlist\n",
    "```\n",
    "\n",
    "**Note:**\n",
    "\n",
    "* `1 <= words.length <= 2000`\n",
    "* `1 <= words[i].length <= 2000`\n",
    "* Words will only consist of lowercase English letters.\n",
    "* Queries will only consist of lowercase English letters.\n",
    "* The number of queries is at most 40000."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Study Notes:**\n",
    "* Solution from leetcode: [https://leetcode.com/problems/stream-of-characters/discuss/807616/Python-Trie-(Simple-to-understand-with-question-and-explanation)](https://leetcode.com/problems/stream-of-characters/discuss/807616/Python-Trie-(Simple-to-understand-with-question-and-explanation))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "input1 = [\"cd\",\"f\",\"kl\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "# leetcode solution\n",
    "class Trie:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.children = {}\n",
    "        self.endshere = False\n",
    "        \n",
    "class StreamChecker:\n",
    "\n",
    "    def __init__(self, words: List[str]):\n",
    "        self.root = Trie('-1')\n",
    "        self.letters = []\n",
    "        self.insert(words)\n",
    "    \n",
    "    def insert(self, words):\n",
    "        for word in words:\n",
    "            curr_node = self.root\n",
    "            for i in range(len(word)-1, -1, -1):\n",
    "                if word[i] not in curr_node.children:\n",
    "                    curr_node.children[word[i]] = Trie(word[i])\n",
    "                curr_node = curr_node.children[word[i]]\n",
    "            curr_node.endshere = True\n",
    "        return None\n",
    "\n",
    "    def query(self, letter: str) -> bool:\n",
    "        self.letters.append(letter)\n",
    "        curr_node = self.root\n",
    "        for i in range(len(self.letters)-1, -1, -1):\n",
    "            if curr_node.endshere:\n",
    "                return True\n",
    "            if self.letters[i] in curr_node.children:\n",
    "                curr_node = curr_node.children[self.letters[i]]\n",
    "            else:\n",
    "                return False\n",
    "        return curr_node.endshere"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "# implement leetcode solution\n",
    "class Trie:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.children = {}\n",
    "        self.ends = False\n",
    "\n",
    "class StreamChecker:\n",
    "\n",
    "    def __init__(self, words: List[str]):\n",
    "        self.root = Trie('-1') # root node with dummy value\n",
    "        self.letters = [] # queue/stack for processing query calls\n",
    "        self.insert(words)\n",
    "    \n",
    "    # extra insert function\n",
    "    def insert(self, words):\n",
    "        for w in words:\n",
    "            curnode = self.root\n",
    "            for i in range(len(w)-1, -1, -1): # iterate backwards through each character of word\n",
    "                if w[i] not in curnode.children:\n",
    "                    curnode.children[w[i]] = Trie(w[i]) # add Trie object as dict value at key w[i]\n",
    "                curnode = curnode.children[w[i]] # iterate current node to the child node at key w[i]\n",
    "            curnode.ends = True # mark ending Trie node for the final character\n",
    "        return None\n",
    "                    \n",
    "    \n",
    "    def query(self, letter: str) -> bool:\n",
    "        self.letters.append(letter)\n",
    "        curnode = self.root\n",
    "        for i in range(len(self.letters)-1,-1,-1):\n",
    "            if curnode.ends:\n",
    "                return True\n",
    "            elif self.letters[i] in curnode.children:\n",
    "                curnode = curnode.children[self.letters[i]]\n",
    "            else:\n",
    "                return False\n",
    "        return curnode.ends\n",
    "\n",
    "\n",
    "# Your StreamChecker object will be instantiated and called as such:\n",
    "# obj = StreamChecker(words)\n",
    "# param_1 = obj.query(letter)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n",
      "False\n",
      "False\n",
      "True\n",
      "False\n",
      "True\n",
      "False\n",
      "False\n",
      "False\n",
      "False\n",
      "False\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "streamChecker = StreamChecker([\"cd\",\"f\",\"kl\"]); # init the dictionary.\n",
    "print(streamChecker.query('a'))          # return false\n",
    "print(streamChecker.query('b'))          # return false\n",
    "print(streamChecker.query('c'))          # return false\n",
    "print(streamChecker.query('d'))          # return true, because 'cd' is in the wordlist\n",
    "print(streamChecker.query('e'))          # return false\n",
    "print(streamChecker.query('f'))          # return true, because 'f' is in the wordlist\n",
    "print(streamChecker.query('g'))          # return false\n",
    "print(streamChecker.query('h'))          # return false\n",
    "print(streamChecker.query('i'))          # return false\n",
    "print(streamChecker.query('j'))          # return false\n",
    "print(streamChecker.query('k'))          # return false\n",
    "print(streamChecker.query('l'))          # return true, because 'kl' is in the wordlist"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 24: 8/24/20\n",
    "### 404. Sum of Left Leaves\n",
    "EASY  \n",
    "https://leetcode.com/problems/sum-of-left-leaves/  \n",
    "https://leetcode.com/explore/challenge/card/august-leetcoding-challenge/552/week-4-august-22nd-august-28th/3435/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Find the sum of all left leaves in a given binary tree.\n",
    "\n",
    "**Example:**\n",
    "```\n",
    "    3\n",
    "   / \\\n",
    "  9  20\n",
    "    /  \\\n",
    "   15   7\n",
    "\n",
    "There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        \n",
    "def constructtree(nodes, i, n):\n",
    "    node = None\n",
    "    if (i < n) and nodes[i] is not None:\n",
    "        node = TreeNode(nodes[i])\n",
    "        node.left = constructtree(nodes, 2*i+1, len(nodes))\n",
    "        node.right = constructtree(nodes, 2*i+2, len(nodes))\n",
    "    return node\n",
    "\n",
    "def printtree(root):\n",
    "    q = [root]\n",
    "    nodes = []\n",
    "    while q:\n",
    "        node = q.pop(0)\n",
    "        if node:\n",
    "            nodes.append(node.val)\n",
    "            if node.left or node.right or any(q):\n",
    "                q.append(node.left)\n",
    "                q.append(node.right)\n",
    "        elif any(q):\n",
    "            nodes.append('null')\n",
    "    return nodes\n",
    "\n",
    "nodes1 = [3,9,20,None,None,15,7]\n",
    "root1 = constructtree(nodes1,0,len(nodes1))\n",
    "nodes2 = [1,2,3,4,5]\n",
    "root2 = constructtree(nodes2,0,len(nodes2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: TreeNode) -> int:        \n",
    "        q = [root]\n",
    "        total = 0\n",
    "        while q:\n",
    "            node = q.pop()\n",
    "            if node and node.left:\n",
    "                q.append(node.left)\n",
    "                if not (node.left.left or node.left.right):\n",
    "                    total += node.left.val\n",
    "            if node and node.right:\n",
    "                q.append(node.right)\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 71,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "soln = Solution()\n",
    "soln.sumOfLeftLeaves(root2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 25: 8/25/20\n",
    "### 983. Minimum Cost For Tickets\n",
    "MEDIUM  \n",
    "https://leetcode.com/problems/minimum-cost-for-tickets/  \n",
    "https://leetcode.com/explore/challenge/card/august-leetcoding-challenge/552/week-4-august-22nd-august-28th/3436/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In a country popular for train travel, you have planned some train travelling one year in advance.  The days of the year that you will travel is given as an array `days`.  Each day is an integer from `1` to `365`.\n",
    "\n",
    "Train tickets are sold in 3 different ways:\n",
    "\n",
    "* a 1-day pass is sold for `costs[0]` dollars;\n",
    "* a 7-day pass is sold for `costs[1]` dollars;\n",
    "* a 30-day pass is sold for `costs[2]` dollars.\n",
    "The passes allow that many days of consecutive travel.  For example, if we get a 7-day pass on day 2, then we can travel for 7 days: day 2, 3, 4, 5, 6, 7, and 8.\n",
    "\n",
    "Return the minimum number of dollars you need to travel every day in the given list of `days`.\n",
    "\n",
    " \n",
    "\n",
    "**Example 1:**\n",
    "```\n",
    "Input: days = [1,4,6,7,8,20], costs = [2,7,15]\n",
    "Output: 11\n",
    "Explanation: \n",
    "For example, here is one way to buy passes that lets you travel your travel plan:\n",
    "On day 1, you bought a 1-day pass for costs[0] = $2, which covered day 1.\n",
    "On day 3, you bought a 7-day pass for costs[1] = $7, which covered days 3, 4, ..., 9.\n",
    "On day 20, you bought a 1-day pass for costs[0] = $2, which covered day 20.\n",
    "In total you spent $11 and covered all the days of your travel.\n",
    "```\n",
    "**Example 2:**\n",
    "```\n",
    "Input: days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]\n",
    "Output: 17\n",
    "Explanation: \n",
    "For example, here is one way to buy passes that lets you travel your travel plan:\n",
    "On day 1, you bought a 30-day pass for costs[2] = $15 which covered days 1, 2, ..., 30.\n",
    "On day 31, you bought a 1-day pass for costs[0] = $2 which covered day 31.\n",
    "In total you spent $17 and covered all the days of your travel.\n",
    "```\n",
    "\n",
    "**Note:**\n",
    "\n",
    "1. `1 <= days.length <= 365`\n",
    "2. `1 <= days[i] <= 365`\n",
    "3. `days` is in strictly increasing order.\n",
    "4. `costs.length == 3`\n",
    "5. `1 <= costs[i] <= 1000`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Study Notes:**\n",
    "* 3 possibilities:\n",
    "    1. Buy one-day pass for today = prev_day_cost + cost[0]\n",
    "    2. Buy 7-day pass to cover today = cost_from_today-7_days_ago + cost[1]\n",
    "    3. Buy 30-day pass to cover today = cost_from_today-30_days_ago + cost[3]\n",
    "* final cost is the minimum of these three\n",
    "* two approaches to handling the fact that `days` can be discontinuous:\n",
    "    1. Make `dp` array be daily and only change value when `dp[i]` is a traveling day\n",
    "    2. Make `dp` array be of same length as days but either search `days` for the index `i` that meets the previous traveling day criteria (for looking up previous costs in `dp`) or use pointers and/or hash tables to track index values for 7 and 30 days prior\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "days1,costs1 = [1,4,6,7,8,20], [2,7,15]\n",
    "days2,costs2 = [1,2,3,4,5,6,7,8,9,10,30,31], [2,7,15]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "# simpler iterate through all days up to days[-1]\n",
    "class Solution:\n",
    "    def mincostTickets(self, days: List[int], costs: List[int]) -> int:\n",
    "        traveldays = {}\n",
    "        for day in days:\n",
    "            traveldays[day] = 1\n",
    "        \n",
    "        \n",
    "        dp = [0]*(days[-1]+1)\n",
    "        for i in range(1,len(dp)):\n",
    "            if i in traveldays:\n",
    "                onedaypass = dp[i-1] + costs[0]\n",
    "                sevendaypass = dp[max(i-7,0)] + costs[1] # max(i-7,0) will limit indexing to >= 0\n",
    "                thirtydaypass = dp[max(i-30,0)] + costs[2]\n",
    "                dp[i] = min(onedaypass,sevendaypass,thirtydaypass)\n",
    "            else:\n",
    "                dp[i] = dp[i-1]\n",
    "            \n",
    "            \n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "17"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "soln = Solution()\n",
    "soln.mincostTickets(days2,costs2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 26: 8/26/20\n",
    "### 412. Fizz Buzz\n",
    "EASY!  \n",
    "https://leetcode.com/problems/fizz-buzz/  \n",
    "https://leetcode.com/explore/challenge/card/august-leetcoding-challenge/552/week-4-august-22nd-august-28th/3437/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Write a program that outputs the string representation of numbers from 1 to n.\n",
    "\n",
    "But for multiples of three it should output “Fizz” instead of the number and for the multiples of five output “Buzz”. For numbers which are multiples of both three and five output “FizzBuzz”.\n",
    "\n",
    "**Example:**\n",
    "```\n",
    "n = 15,\n",
    "\n",
    "Return:\n",
    "[\n",
    "    \"1\",\n",
    "    \"2\",\n",
    "    \"Fizz\",\n",
    "    \"4\",\n",
    "    \"Buzz\",\n",
    "    \"Fizz\",\n",
    "    \"7\",\n",
    "    \"8\",\n",
    "    \"Fizz\",\n",
    "    \"Buzz\",\n",
    "    \"11\",\n",
    "    \"Fizz\",\n",
    "    \"13\",\n",
    "    \"14\",\n",
    "    \"FizzBuzz\"\n",
    "]\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "n1 = 15"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def fizzBuzz(self, n: int) -> List[str]:\n",
    "        output = []\n",
    "        for i in range(1,n+1):\n",
    "            if (i % 3 == 0) and (i % 5 == 0):\n",
    "                output.append('FizzBuzz')\n",
    "            elif i % 3 == 0:\n",
    "                output.append('Fizz')\n",
    "            elif i % 5 == 0:\n",
    "                output.append('Buzz')\n",
    "            else:\n",
    "                output.append(str(i))\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "# using dict (note: as of python 3.7 dicts preserve insertion order, otherwise use OrderedDict) and string concat\n",
    "class Solution:\n",
    "    def fizzBuzz(self, n: int) -> List[str]:\n",
    "        replace = {\n",
    "            3: 'Fizz'\n",
    "            ,5: 'Buzz'\n",
    "#             ,7: 'Jazz' # fizzbuzz problem extension\n",
    "        }\n",
    "        \n",
    "        output = []\n",
    "        for i in range(1,n+1):\n",
    "            s = ''\n",
    "            for keyn in replace:\n",
    "                if i % keyn == 0:\n",
    "                    s += replace[keyn]\n",
    "            \n",
    "            # add str(i) if no divisible found\n",
    "            if s == '':\n",
    "                s += str(i)\n",
    "            \n",
    "            output.append(s)\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['1',\n",
       " '2',\n",
       " 'Fizz',\n",
       " '4',\n",
       " 'Buzz',\n",
       " 'Fizz',\n",
       " '7',\n",
       " '8',\n",
       " 'Fizz',\n",
       " 'Buzz',\n",
       " '11',\n",
       " 'Fizz',\n",
       " '13',\n",
       " '14',\n",
       " 'FizzBuzz',\n",
       " '16',\n",
       " '17',\n",
       " 'Fizz',\n",
       " '19',\n",
       " 'Buzz',\n",
       " 'Fizz']"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "soln = Solution()\n",
    "soln.fizzBuzz(21)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 27: 8/27/20\n",
    "### 436. Find Right Interval\n",
    "MEDIUM  \n",
    "https://leetcode.com/problems/find-right-interval/  \n",
    "https://leetcode.com/explore/challenge/card/august-leetcoding-challenge/552/week-4-august-22nd-august-28th/3438/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a set of intervals, for each of the interval i, check if there exists an interval j whose start point is bigger than or equal to the end point of the interval i, which can be called that j is on the \"right\" of i.\n",
    "\n",
    "For any interval i, you need to store the minimum interval j's index, which means that the interval j has the minimum start point to build the \"right\" relationship for interval i. If the interval j doesn't exist, store -1 for the interval i. Finally, you need output the stored value of each interval as an array.\n",
    "\n",
    "**Note:**\n",
    "\n",
    "1. You may assume the interval's end point is always bigger than its start point.\n",
    "2. You may assume none of these intervals have the same start point.\n",
    " \n",
    "\n",
    "**Example 1:**\n",
    "```\n",
    "Input: [ [1,2] ]\n",
    "\n",
    "Output: [-1]\n",
    "\n",
    "Explanation: There is only one interval in the collection, so it outputs -1.\n",
    "```\n",
    "\n",
    "**Example 2:**\n",
    "```\n",
    "Input: [ [3,4], [2,3], [1,2] ]\n",
    "\n",
    "Output: [-1, 0, 1]\n",
    "\n",
    "Explanation: There is no satisfied \"right\" interval for [3,4].\n",
    "For [2,3], the interval [3,4] has minimum-\"right\" start point;\n",
    "For [1,2], the interval [2,3] has minimum-\"right\" start point.\n",
    "```\n",
    "\n",
    "**Example 3:**\n",
    "```\n",
    "Input: [ [1,4], [2,3], [3,4] ]\n",
    "\n",
    "Output: [-1, 2, -1]\n",
    "\n",
    "Explanation: There is no satisfied \"right\" interval for [1,4] and [3,4].\n",
    "For [2,3], the interval [3,4] has minimum-\"right\" start point.\n",
    "```\n",
    "**NOTE:** input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Study Notes:**\n",
    "* leetcode post on binary search: [https://leetcode.com/problems/binary-search/discuss/423162/Binary-Search-101-The-Ultimate-Binary-Search-Handbook](https://leetcode.com/problems/binary-search/discuss/423162/Binary-Search-101-The-Ultimate-Binary-Search-Handbook)\n",
    "* using `mid = (lo + hi)//2` can overflow if values are too big\n",
    "* `mid = lo + ((hi-lo)//2)` is better"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "intervals1 = [ [1,2] ]\n",
    "intervals2 = [ [3,4], [2,3], [1,2] ]\n",
    "intervals3 = [ [1,4], [2,3], [3,4] ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "metadata": {},
   "outputs": [],
   "source": [
    "# naive solution: sorting + searching\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        # helper function search \n",
    "        def binsearch(ordered,targetint):\n",
    "            lo = 0\n",
    "            hi = len(ordered)-1\n",
    "            target = targetint[1]\n",
    "            if target > ordered[hi][0]:\n",
    "                return [-1,-1]\n",
    "            \n",
    "            mid = 0\n",
    "            while lo < hi:\n",
    "                mid = (lo + hi)//2\n",
    "                val = ordered[mid][0]\n",
    "                if target > val:\n",
    "                    lo = mid + 1\n",
    "                else:\n",
    "                    hi = mid\n",
    "            return ordered[lo]\n",
    "        \n",
    "        indexes = {(-1,-1):-1} # default val for invalid\n",
    "        for i,ivl in enumerate(intervals):\n",
    "            indexes[tuple(ivl)] = i\n",
    "        \n",
    "        ordered = sorted(intervals, key=lambda x: x[0])\n",
    "        result = [0]*len(intervals)\n",
    "        for ivl in ordered:\n",
    "            # search ordered intervals\n",
    "            rivl = binsearch(ordered,ivl)\n",
    "            ridx = indexes[tuple(rivl)]\n",
    "            idx = indexes[tuple(ivl)]\n",
    "            result[idx] = ridx\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {},
   "outputs": [],
   "source": [
    "# def binsearch(ordered,targetint):\n",
    "#     lo = 0\n",
    "#     hi = len(ordered)-1\n",
    "#     target = targetint[1]\n",
    "#     print('target:',target)\n",
    "#     if target > ordered[hi][0]:\n",
    "#         return [-1,-1]\n",
    "\n",
    "#     mid = 0\n",
    "#     while lo < hi:\n",
    "#         mid = (lo + hi)//2\n",
    "#         val = ordered[mid][0]\n",
    "#         print('mid:',mid,'midval:',val)\n",
    "#         if target > val:\n",
    "#             lo = mid + 1\n",
    "#         else:\n",
    "#             hi = mid\n",
    "#     return ordered[lo]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[-1]"
      ]
     },
     "execution_count": 111,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "soln = Solution()\n",
    "soln.findRightInterval(intervals1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 28: 8/28/20\n",
    "### 470. Implement Rand10() Using Rand7()\n",
    "MEDIUM  \n",
    "https://leetcode.com/problems/implement-rand10-using-rand7/  \n",
    "https://leetcode.com/explore/challenge/card/august-leetcoding-challenge/552/week-4-august-22nd-august-28th/3439/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a function `rand7` which generates a uniform random integer in the range 1 to 7, write a function `rand10` which generates a uniform random integer in the range 1 to 10.\n",
    "\n",
    "Do NOT use system's Math.random().\n",
    "\n",
    "**Example 1:**\n",
    "```\n",
    "Input: 1\n",
    "Output: [7]\n",
    "```\n",
    "**Example 2:**\n",
    "```\n",
    "Input: 2\n",
    "Output: [8,4]\n",
    "```\n",
    "**Example 3:**\n",
    "```\n",
    "Input: 3\n",
    "Output: [8,1,10]\n",
    "```\n",
    "\n",
    "**Note:**\n",
    "\n",
    "1. `rand7` is predefined.\n",
    "2. Each testcase has one argument: `n`, the number of times that `rand10` is called.\n",
    " \n",
    "\n",
    "**Follow up:**\n",
    "\n",
    "1. What is the `expected value` for the number of calls to `rand7()` function?\n",
    "2. Could you minimize the number of calls to `rand7()`?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Study Notes:**\n",
    "* See [rejection sampling](https://en.wikipedia.org/wiki/Rejection_sampling)\n",
    "    * Also: [https://towardsdatascience.com/simulate-any-distribution-with-rejection-sampling-ebe4e66cc068](https://towardsdatascience.com/simulate-any-distribution-with-rejection-sampling-ebe4e66cc068)\n",
    "* Core idea:\n",
    "    * generate two random numbers in range `[1,7]` (call `rand7()` twice)\n",
    "    * transform them uniformly on to the range `[1,49]`\n",
    "    * if transformed value is in `[1,40]` then just return modulo 10 for the value, otherwise sample again"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "def rand7():\n",
    "    return random.randint(1,7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [],
   "source": [
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        r = rand7()\n",
    "        c = rand7()\n",
    "        n = (r-1)*7 + c # transform r & c into range [1,49]\n",
    "        return (n % 10)+1 if n <= 40 else self.rand10()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "soln = Solution()\n",
    "soln.rand10()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 29: 8/29/20\n",
    "### 969. Pancake Sorting\n",
    "MEDIUM  \n",
    "https://leetcode.com/problems/pancake-sorting/  \n",
    "https://leetcode.com/explore/challenge/card/august-leetcoding-challenge/553/week-5-august-29th-august-31st/3441/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given an array of integers `A`, We need to sort the array performing a series of **pancake flips**.\n",
    "\n",
    "In one pancake flip we do the following steps:\n",
    "\n",
    "* Choose an integer `k` where `0 <= k < A.length`.\n",
    "* Reverse the sub-array `A[0...k]`.\n",
    "\n",
    "For example, if `A = [3,2,1,4]` and we performed a pancake flip choosing `k = 2`, we reverse the sub-array `[3,2,1]`, so `A = [1,2,3,4]` after the pancake flip at `k = 2`.\n",
    "\n",
    "Return *an array of the k-values of the pancake flips* that should be performed in order to sort `A`. Any valid answer that sorts the array within `10 * A.length` flips will be judged as correct.\n",
    "\n",
    " \n",
    "\n",
    "**Example 1:**\n",
    "```\n",
    "Input: A = [3,2,4,1]\n",
    "Output: [4,2,4,3]\n",
    "Explanation: \n",
    "We perform 4 pancake flips, with k values 4, 2, 4, and 3.\n",
    "Starting state: A = [3, 2, 4, 1]\n",
    "After 1st flip (k = 4): A = [1, 4, 2, 3]\n",
    "After 2nd flip (k = 2): A = [4, 1, 2, 3]\n",
    "After 3rd flip (k = 4): A = [3, 2, 1, 4]\n",
    "After 4th flip (k = 3): A = [1, 2, 3, 4], which is sorted.\n",
    "Notice that we return an array of the chosen k values of the pancake flips.\n",
    "```\n",
    "**Example 2:**\n",
    "```\n",
    "Input: A = [1,2,3]\n",
    "Output: []\n",
    "Explanation: The input is already sorted, so there is no need to flip anything.\n",
    "Note that other answers, such as [3, 3], would also be accepted.\n",
    "```\n",
    "\n",
    "**Constraints:**\n",
    "\n",
    "* `1 <= A.length <= 100`\n",
    "* `1 <= A[i] <= A.length`\n",
    "* All integers in `A` are unique (i.e. `A` is a permutation of the integers from `1` to `A.length`)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Study Notes:**\n",
    "* leetcode solution: [https://leetcode.com/problems/pancake-sorting/discuss/817862/Python-O(n)-flipsO(n2)-time-explained](https://leetcode.com/problems/pancake-sorting/discuss/817862/Python-O(n)-flipsO(n2)-time-explained)\n",
    "* based on bubble sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "A1 = [3,2,4,1]\n",
    "A2 = [1,2,3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def pancakeSort(self, A: List[int]) -> List[int]:\n",
    "        \n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "soln = Solution()\n",
    "soln.pancakeSort(A1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 30: 8/31/20\n",
    "### 952. Largest Component Size by Common Factor\n",
    "HARD  \n",
    "https://leetcode.com/problems/largest-component-size-by-common-factor/  \n",
    "https://leetcode.com/explore/challenge/card/august-leetcoding-challenge/553/week-5-august-29th-august-31st/3442/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a non-empty array of unique positive integers `A`, consider the following graph:\n",
    "\n",
    "* There are `A.length` nodes, labelled `A[0]` to `A[A.length - 1]`;\n",
    "* There is an edge between `A[i]` and `A[j]` if and only if `A[i]` and `A[j]` share a common factor greater than 1.\n",
    "\n",
    "Return the size of the largest connected component in the graph.\n",
    "\n",
    "**Example 1:**\n",
    "```\n",
    "Input: [4,6,15,35]\n",
    "Output: 4\n",
    "```\n",
    "![https://assets.leetcode.com/uploads/2018/12/01/ex1.png](https://assets.leetcode.com/uploads/2018/12/01/ex1.png)\n",
    "\n",
    "**Example 2:**\n",
    "```\n",
    "Input: [20,50,9,63]\n",
    "Output: 2\n",
    "```\n",
    "![https://assets.leetcode.com/uploads/2018/12/01/ex2.png](https://assets.leetcode.com/uploads/2018/12/01/ex2.png)\n",
    "**Example 3:**\n",
    "```\n",
    "Input: [2,3,6,7,4,12,21,39]\n",
    "Output: 8\n",
    "```\n",
    "![https://assets.leetcode.com/uploads/2018/12/01/ex3.png](https://assets.leetcode.com/uploads/2018/12/01/ex3.png)\n",
    "\n",
    "**Note:**\n",
    "\n",
    "* `1 <= A.length <= 20000`\n",
    "* `1 <= A[i] <= 100000`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Study Notes:**\n",
    "* This question is HARD\n",
    "* Leetcode solution reference: [https://leetcode.com/problems/largest-component-size-by-common-factor/discuss/819919/Python-Union-find-solution-explained](https://leetcode.com/problems/largest-component-size-by-common-factor/discuss/819919/Python-Union-find-solution-explained)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "A1 = [4,6,15,35]\n",
    "A2 = [2,3,6,7,4,12,21,39]\n",
    "A3 = [2,3,6,7,4,12,21,39]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "# leetcode solution\n",
    "from collections import defaultdict, Counter\n",
    "import math\n",
    "class DSU:\n",
    "    def __init__(self, N):\n",
    "        self.p = list(range(N))\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.p[x] != x:\n",
    "            self.p[x] = self.find(self.p[x])\n",
    "        return self.p[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        xr, yr = self.find(x), self.find(y)\n",
    "        self.p[xr] = yr\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def primes_set(self,n):\n",
    "        for i in range(2, int(math.sqrt(n))+1):\n",
    "            if n % i == 0:\n",
    "                return self.primes_set(n//i) | set([i])\n",
    "        return set([n])\n",
    "\n",
    "    def largestComponentSize(self, A: List[int]) -> int:\n",
    "        n = len(A)\n",
    "        UF = DSU(n)\n",
    "        primes = defaultdict(list)\n",
    "        for i, num in enumerate(A):\n",
    "            pr_set = self.primes_set(num)\n",
    "            for q in pr_set: primes[q].append(i)\n",
    "\n",
    "        for _, indexes in primes.items():\n",
    "            for i in range(len(indexes)-1):\n",
    "                UF.union(indexes[i], indexes[i+1])\n",
    "\n",
    "        return max(Counter([UF.find(i) for i in range(n)]).values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "soln = Solution()\n",
    "soln.largestComponentSize(A1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution2:\n",
    "    def get_primeset(self, n):\n",
    "        for i in range(2, int(math.sqrt(n))+1):\n",
    "            if n % i == 0:\n",
    "                return set([i]) | self.get_primeset(n//i)\n",
    "        return set([n])\n",
    "    \n",
    "    def largestComponentSize(self, A: List[int]) -> int:\n",
    "        n = len(A)\n",
    "#         UF = DSU(n)\n",
    "        primes = defaultdict(list)\n",
    "        # calculate set of primes for each element in A, add index values to primes defaultdict\n",
    "        for i,val in enumerate(A):\n",
    "            primeset = self.get_primeset(val)\n",
    "            for p in primeset:\n",
    "                primes[p].append(i)\n",
    "\n",
    "        return primes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 113,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defaultdict(list, {2: [0, 2, 4, 5], 3: [1, 2, 5, 6, 7], 7: [3, 6], 13: [7]})"
      ]
     },
     "execution_count": 113,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "soln2 = Solution2()\n",
    "soln2.largestComponentSize(A3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defaultdict(list, {2: [0, 1], 3: [1, 2], 5: [2, 3], 7: [3]})"
      ]
     },
     "execution_count": 81,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "primes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 31: 8/31/20\n",
    "### 450. Delete Node in a BST\n",
    "MEDIUM  \n",
    "https://leetcode.com/problems/delete-node-in-a-bst/  \n",
    "https://leetcode.com/explore/challenge/card/august-leetcoding-challenge/553/week-5-august-29th-august-31st/3443/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.\n",
    "\n",
    "Basically, the deletion can be divided into two stages:\n",
    "\n",
    "1. Search for a node to remove.\n",
    "2. If the node is found, delete the node.\n",
    "\n",
    "**Note:** Time complexity should be O(height of tree).\n",
    "\n",
    "**Example:**\n",
    "```\n",
    "root = [5,3,6,2,4,null,7]\n",
    "key = 3\n",
    "\n",
    "    5\n",
    "   / \\\n",
    "  3   6\n",
    " / \\   \\\n",
    "2   4   7\n",
    "\n",
    "Given key to delete is 3. So we find the node with value 3 and delete it.\n",
    "\n",
    "One valid answer is [5,4,6,2,null,null,7], shown in the following BST.\n",
    "\n",
    "    5\n",
    "   / \\\n",
    "  4   6\n",
    " /     \\\n",
    "2       7\n",
    "\n",
    "Another valid answer is [5,2,6,null,4,null,7].\n",
    "\n",
    "    5\n",
    "   / \\\n",
    "  2   6\n",
    "   \\   \\\n",
    "    4   7\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Study Notes:**\n",
    "* Leetcode solution: [https://leetcode.com/problems/delete-node-in-a-bst/discuss/821420/Python-O(h)-solution-explained](https://leetcode.com/problems/delete-node-in-a-bst/discuss/821420/Python-O(h)-solution-explained)\n",
    "* key steps:\n",
    "    * recursively traverse BST until root.val == key\n",
    "    *  Case 1: Node to delete has no children. Remove node.\n",
    "    *  Case 2: Node to delete only has left children. Remove node and connect left child to parent as new left child.\n",
    "    *  Case 3: Node to delete only has right children. Remove node and connect right child to parent as new right child.\n",
    "    *  Case 4: Node to delete has both children. **Find successor node by finding the left-most child in the right child branch**. Traverse to right child then find deepest left child with no left child."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 155,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "# assumes no missing nodes, every node must be explicitly defined in the level order array, can't handle multiple \"levels\" of None\n",
    "def constructtree(nodes, i, n):\n",
    "    root = None\n",
    "    if (i < n) and nodes[i] is not None:\n",
    "        root = TreeNode(nodes[i])\n",
    "        root.left = constructtree(nodes, 2*i+1, len(nodes))\n",
    "        root.right = constructtree(nodes, 2*i+2, len(nodes))\n",
    "    return root\n",
    "\n",
    "def printtree(root):\n",
    "    q = [root]\n",
    "    nodes = []\n",
    "    while q:\n",
    "        node = q.pop(0)\n",
    "        if node:\n",
    "            nodes.append(node.val)\n",
    "            if node.left or node.right or any(q):\n",
    "                q.append(node.left)\n",
    "                q.append(node.right)\n",
    "        elif any(q):\n",
    "            nodes.append('null')\n",
    "    return nodes\n",
    "\n",
    "nodes1,key1 = [5,3,6,2,4,None,7], 3\n",
    "root1 = constructtree(nodes1,0,len(nodes1))\n",
    "nodes2,key2 = [12, 6, 15, 3, 7, 13, 17, 1, None, 6, 9, None, 14, None, 20], 13\n",
    "root2 = constructtree(nodes2,0, len(nodes2))\n",
    "nodes3,key3 = [1,None,2], 2\n",
    "root3 = constructtree(nodes3,0,len(nodes3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 189,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def deleteNode(self, root: TreeNode, key: int) -> TreeNode:\n",
    "        if root is None:\n",
    "            return None\n",
    "        \n",
    "        # if root is the node to delete, return one of it's children to caller\n",
    "        # should result in setting whatever returns here as the child of the parent node calling this instance\n",
    "        if key == root.val:\n",
    "            # case 2: left child only\n",
    "            if root.right is None:\n",
    "                return root.left\n",
    "            # case 3: right child only\n",
    "            if root.left is None:\n",
    "                return root.right\n",
    "            # case 4: has both children\n",
    "            if root.left and root.right:\n",
    "                tmp = root.right\n",
    "                while tmp.left:\n",
    "                    tmp = tmp.left\n",
    "                # delete node\n",
    "                root.val = tmp.val\n",
    "                root.right = self.deleteNode(root.right, root.val) # delete that old node with root.val == key\n",
    "        \n",
    "        # traverse tree\n",
    "        elif key > root.val:\n",
    "            root.right = self.deleteNode(root.right, key) # traverse right branch\n",
    "        else:\n",
    "            root.left = self.deleteNode(root.left, key) # traverse left branch\n",
    "            \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 183,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def deleteNode(self, root, key):\n",
    "        if not root: return None\n",
    "        \n",
    "        if key == root.val:\n",
    "            if root.right is None: \n",
    "                return root.left\n",
    "            \n",
    "            if root.left is None: \n",
    "                return root.right\n",
    "            \n",
    "            if root.left and root.right:\n",
    "                tmp = root.right\n",
    "                while tmp.left: \n",
    "                    tmp = tmp.left\n",
    "                root.val = tmp.val\n",
    "                root.right = self.deleteNode(root.right, root.val)\n",
    "\n",
    "        elif root.val > key:\n",
    "            root.left = self.deleteNode(root.left, key)\n",
    "        else:\n",
    "            root.right = self.deleteNode(root.right, key)\n",
    "            \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 190,
   "metadata": {},
   "outputs": [],
   "source": [
    "nodes3,key3 = [1,None,2], 2\n",
    "root3 = constructtree(nodes3,0,len(nodes3))\n",
    "soln = Solution()\n",
    "ans = soln.deleteNode(root3,key3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 191,
   "metadata": {},
   "outputs": [],
   "source": [
    "ans.right"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "base (Python 3.7.7)",
   "language": "python",
   "name": "base"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}