easy_tasks.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Valid palindrome"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://leetcode.com/problems/valid-palindrome/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a string s, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.\n",
    "\n",
    "Input: s = \"A man, a plan, a canal: Panama\"  \n",
    "Output: true  \n",
    "Explanation: \"amanaplanacanalpanama\" is a palindrome.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def isPalindrome(s: str) -> bool:\n",
    "    s_prep = list(''.join([i for i in s.lower() if i.isalnum()]))\n",
    "    len_s = len(s_prep)\n",
    "    end_ind = -1\n",
    "    for i in range(len_s//2):\n",
    "        if s_prep[i] != s_prep[end_ind]:\n",
    "            return False\n",
    "            break         \n",
    "        else:\n",
    "            end_ind-=1\n",
    "            pass\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"race a car\"\n",
    "isPalindrome(s=s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#  Move Zeroes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://leetcode.com/problems/move-zeroes/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.\n",
    "\n",
    "Note that you must do this in-place without making a copy of the array.\n",
    "\n",
    "Input: nums = [0,1,0,3,12]  \n",
    "Output: [1,3,12,0,0]  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def moveZeroes(nums: list) -> None:\n",
    "    len_nums = len(nums)\n",
    "    to_pop = []\n",
    "    decrease_to_pop = 0\n",
    "    for i in range(len_nums):\n",
    "        if nums[i]==0:\n",
    "            to_pop.append(i-decrease_to_pop)\n",
    "            nums.append(0)\n",
    "            decrease_to_pop+=1\n",
    "    for i in to_pop:\n",
    "        del(nums[i])\n",
    "    \n",
    "    return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[7, 7, 9, 4, 9, 0]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = [7, 7, 0, 9, 4, 9]\n",
    "moveZeroes(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Two Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://leetcode.com/problems/two-sum/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.\n",
    "\n",
    "You may assume that each input would have exactly one solution, and you may not use the same element twice.\n",
    "\n",
    "You can return the answer in any order.\n",
    "\n",
    "Input: nums = [2,7,11,15], target = 9  \n",
    "Output: [0,1]  \n",
    "Output: Because nums[0] + nums[1] == 9, we return [0, 1]."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [],
   "source": [
    "# nums = [2,7,11,15]\n",
    "# target = 9\n",
    "nums = [3,2,4]\n",
    "target = 6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [],
   "source": [
    "def twoSum(nums: list, target: int) -> list:\n",
    "    res = []\n",
    "    for i in range(len(nums)):\n",
    "        res.append(target-nums[i])\n",
    "        if (nums[i] in res):\n",
    "            if i!=res.index(nums[i]):\n",
    "                return [i, res.index(nums[i])]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 1]"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "twoSum(nums, target)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Reverse Integer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Not interesting at all. Lesson: be more attentive"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://leetcode.com/problems/reverse-integer/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-231, 231 - 1], then return 0.  \n",
    "\n",
    "Assume the environment does not allow you to store 64-bit integers (signed or unsigned).  \n",
    "Input: x = 123  \n",
    "Output: 321  \n",
    "\n",
    "Input: x = -123  \n",
    "Output: -321"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {},
   "outputs": [],
   "source": [
    "def reverse(x: int) -> int:      \n",
    "    x_list = [i for i in str(x)]\n",
    "    if x_list[0] == '-':\n",
    "        x_list = x_list[1:][::-1]\n",
    "        reverse_int = -int(''.join(x_list))\n",
    "        if (reverse_int <= (-2)**31) :\n",
    "            return 0\n",
    "        else:\n",
    "            return reverse_int\n",
    "    else:\n",
    "        x_list = x_list[::-1]\n",
    "        reverse_int = int(''.join(x_list))\n",
    "        if (reverse_int  >= (2**31-1)):\n",
    "            return 0\n",
    "        else:\n",
    "            return reverse_int"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-654"
      ]
     },
     "execution_count": 96,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "reverse(-456)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Valid Parentheses"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://leetcode.com/problems/valid-parentheses/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.  \n",
    "\n",
    "An input string is valid if:   \n",
    "\n",
    "Open brackets must be closed by the same type of brackets.  \n",
    "Open brackets must be closed in the correct order.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Input: s = \"()\"  \n",
    "Output: true  \n",
    "\n",
    "Input: s = \"([)]\"  \n",
    "Output: false"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 186,
   "metadata": {},
   "outputs": [],
   "source": [
    "def isValid(s: str) -> bool:\n",
    "    open_closed = {'(':')',\n",
    "                  '[':']',\n",
    "                  '{':'}',}\n",
    "    open_p = ['(', '[', '{']\n",
    "    opened_p = []\n",
    "    count_open = 0\n",
    "    count_close =0\n",
    "    for i in s:\n",
    "        if i in open_p:\n",
    "            opened_p.append(i)\n",
    "            count_open+=1\n",
    "        else:\n",
    "           # print(i)\n",
    "           # print(opened_p)\n",
    "            if opened_p == []:\n",
    "                return False\n",
    "            elif i!=open_closed[opened_p[-1]]:\n",
    "                return False\n",
    "            else:\n",
    "                opened_p.pop(-1)\n",
    "                count_close+=1\n",
    "    if count_close!=count_open:\n",
    "        return False\n",
    "    else:\n",
    "        return True        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 189,
   "metadata": {},
   "outputs": [],
   "source": [
    "s = \"()[]{}\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 190,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 190,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isValid(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Jewels and Stones"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://leetcode.com/problems/jewels-and-stones/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You're given strings jewels representing the types of stones that are jewels, and stones representing the stones you have. Each character in stones is a type of stone you have. You want to know how many of the stones you have are also jewels.  \n",
    "\n",
    "Letters are case sensitive, so \"a\" is considered a different type of stone from \"A\".  \n",
    "\n",
    "Input: jewels = \"aA\", stones = \"aAAbbbb\"  \n",
    "Output: 3  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 199,
   "metadata": {},
   "outputs": [],
   "source": [
    "def numJewelsInStones(jewels: str, stones: str):\n",
    "    jewel_list = [i for i in jewels]\n",
    "    jewel_count = 0\n",
    "    for st in stones:\n",
    "        if st in jewel_list:\n",
    "            jewel_count+=1\n",
    "    return jewel_count "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 204,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 204,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "jewels = \"z\"\n",
    "stones = \"ZZ\"\n",
    "numJewelsInStones(jewels, stones)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Next Greater Element I"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://leetcode.com/problems/next-greater-element-i/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.  \n",
    "\n",
    "You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.  \n",
    "\n",
    "For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1.\n",
    "\n",
    "Return an array ans of length nums1.length such that ans[i] is the next greater element as described above."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_element(out_list,num1, ind_nums2, nums2):\n",
    "        for possible_max in nums2[ind_nums2:]:\n",
    "            if num1 < possible_max:\n",
    "                out_list.append(possible_max)\n",
    "                return out_list\n",
    "\n",
    "        out_list.append(-1)\n",
    "        \n",
    "        return out_list\n",
    "    \n",
    "def nextGreaterElement(nums1, nums2):\n",
    "    out_list = []\n",
    "    for num1 in nums1:\n",
    "        ind_nums2 = nums2.index(num1)\n",
    "        if ind_nums2>=len(nums2)-1:\n",
    "            out_list.append(-1)\n",
    "        else:\n",
    "            out_list = find_element(out_list, num1, ind_nums2, nums2)\n",
    "\n",
    "    return out_list\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, -1]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nextGreaterElement(nums1 = [2,4], nums2 = [1,2,3,4])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "#using stack and hash table - cool solution\n",
    "def nextGreaterElement(nums1, nums2):\n",
    "    d = {}\n",
    "    st = []\n",
    "    ans = []\n",
    "\n",
    "    for x in nums2:\n",
    "        while len(st) and st[-1] < x:\n",
    "            d[st.pop()] = x\n",
    "        st.append(x)\n",
    "\n",
    "    for x in nums1:\n",
    "        ans.append(d.get(x, -1))\n",
    "\n",
    "    return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, -1]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nextGreaterElement(nums1 = [2,4], nums2 = [1,2,3,4])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# mergeTwoLists"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [],
   "source": [
    "def mergeTwoLists(l1, l2):\n",
    "    dummy = l3 = ListNode([0])\n",
    "\n",
    "    while l1 and l2:\n",
    "        if l1.val < l2.val:\n",
    "            l3.next = l1\n",
    "            l1 = l1.next\n",
    "        else:\n",
    "            l3.next = l2\n",
    "            l2 = l2.next\n",
    "\n",
    "        l3 = l3.next\n",
    "\n",
    "    l3.next = l1 or l2\n",
    "\n",
    "    return dummy.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<__main__.ListNode at 0x10bf3fb80>"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l1 = ListNode([1,2,4])\n",
    "l2 = ListNode([1,3,4])\n",
    "mergeTwoLists(l1, l2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "# Climbing Stairs (DP)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "https://leetcode.com/problems/climbing-stairs/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "You are climbing a staircase. It takes n steps to reach the top.\n",
    "\n",
    "Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "Input: n = 2  \n",
    "Output: 2  \n",
    "Explanation: There are two ways to climb to the top.  \n",
    "1. 1 step + 1 step\n",
    "2. 2 steps"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "## Bottom-up (Tabulation)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "def climbingBottomUp(n):\n",
    "    if n <= 2:\n",
    "        return n\n",
    "    \n",
    "    dp = [-1]*(n+1)\n",
    "    dp[1] = 1\n",
    "    dp[2] = 2\n",
    "    \n",
    "    for i in range(3, n+1):\n",
    "        dp[i] = dp[i-1] + dp[i-2]\n",
    "        \n",
    "    return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "hidden": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "610"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "climbingBottomUp(14)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "## Top-down (Memoization) - uses recursion"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": [
    "def climbingTopDown(n, memo):\n",
    "    if n <= 2:\n",
    "        return n\n",
    "    \n",
    "    if n not in memo:\n",
    "        memo[n] = climbingTopDown(n-1, memo) + climbingTopDown(n-2, memo)\n",
    "        \n",
    "    return memo[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "hidden": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "610"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "climbingTopDown(14, {})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "# Min Cost Climbing Stairs (DP)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "https://leetcode.com/problems/min-cost-climbing-stairs/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "Input: cost = [10,15,20]  \n",
    "Output: 15  \n",
    "Explanation: You will start at index 1.\n",
    "- Pay 15 and climb two steps to reach the top.\n",
    "\n",
    "The total cost is 15.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "Input: cost = [1,100,1,1,1,100,1,1,100,1]\n",
    "    \n",
    "Output: 6\n",
    "    \n",
    "Explanation: You will start at index 0.\n",
    "- Pay 1 and climb two steps to reach index 2.\n",
    "- Pay 1 and climb two steps to reach index 4.\n",
    "- Pay 1 and climb two steps to reach index 6.\n",
    "- Pay 1 and climb one step to reach index 7.\n",
    "- Pay 1 and climb two steps to reach index 9.\n",
    "- Pay 1 and climb one step to reach the top.\n",
    "\n",
    "The total cost is 6."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {
    "hidden": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(6, [1, 100, 2, 3, 3, 103, 4, 5, 104, 6])"
      ]
     },
     "execution_count": 87,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def minCostBU(cost):\n",
    "    memo = [-1] * len(cost)\n",
    "\n",
    "    if len(cost)==1:\n",
    "        return cost[0]\n",
    "\n",
    "    if len(cost)==2:\n",
    "        return min(cost[0], cost[1])\n",
    "\n",
    "    if len(cost)==3:\n",
    "        return  min(cost[0]+cost[2], cost[1])\n",
    "\n",
    "    memo[0] = cost[0]\n",
    "    memo[1] = cost[1]\n",
    "    #memo[2] = min(cost[0]+cost[2], cost[1])\n",
    "\n",
    "    for i in range(2, len(cost)):\n",
    "        memo[i] = min(memo[i-2]+cost[i], memo[i-1]+cost[i])\n",
    "\n",
    "    return min(memo[len(cost)-1], memo[len(cost)-2]), memo\n",
    "\n",
    "\n",
    "minCostBU( [1,100,1,1,1,100,1,1,100,1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {
    "hidden": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "15"
      ]
     },
     "execution_count": 97,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def minCostTD(cost):\n",
    "        \n",
    "    def dp(i):\n",
    "        \n",
    "        if i==0:\n",
    "            return cost[0]\n",
    "\n",
    "        if i==1:\n",
    "            return cost[1]\n",
    "        \n",
    "        if i not in memo:\n",
    "            memo[i] = min(dp(i-2)+cost[i], dp(i-1)+cost[i])\n",
    "            \n",
    "        return memo[i]\n",
    "               \n",
    "    memo = {}\n",
    "    \n",
    "    return min(dp(len(cost)-1), dp(len(cost)-2))\n",
    "\n",
    "minCostTD([10, 15, 20])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# N-th Tribonacci Number (DP)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://leetcode.com/problems/n-th-tribonacci-number/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Input: n = 4\n",
    "    \n",
    "Output: 4\n",
    "    \n",
    "Explanation:\n",
    "    \n",
    "T_3 = 0 + 1 + 1 = 2  \n",
    "T_4 = 1 + 1 + 2 = 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {},
   "outputs": [],
   "source": [
    "def TribonacciTD(n):\n",
    "    def dp(i):\n",
    "        if i == 0:\n",
    "            return 0\n",
    "        \n",
    "        if i == 1:\n",
    "            return 1\n",
    "\n",
    "        if i == 2:\n",
    "            return 1\n",
    "        \n",
    "        if i not in memo:\n",
    "            memo[i] = dp(i-1) + dp(i-2) + dp(i-3)\n",
    "            \n",
    "        return memo[i]\n",
    "    \n",
    "    memo = {}\n",
    "    \n",
    "    return dp(n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1389537"
      ]
     },
     "execution_count": 103,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "TribonacciTD(25)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 138,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 138,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def TribonacciBU(n):\n",
    "    \n",
    "    memo = [-1]*(n+1)\n",
    "    if n == 0:\n",
    "        return 0\n",
    "\n",
    "    if n == 1:\n",
    "        return 1\n",
    "\n",
    "    if n == 2:\n",
    "        return 1\n",
    "    \n",
    "    memo[0] = 0\n",
    "    memo[1] = 1\n",
    "    memo[2] = 1\n",
    "\n",
    "    for i in range(3, n+1):\n",
    "        #print(i)\n",
    "        memo[i] = memo[i-1] + memo[i-2] + memo[i-3]\n",
    "        #print(memo)\n",
    "\n",
    "    return memo[n]\n",
    "\n",
    "TribonacciBU(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Knapsack problem 0/1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "capacity = 5\n",
    "weights = [2, 3, 4, 5]\n",
    "values = [3, 4, 5, 6]\n",
    "num_of_items = 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [],
   "source": [
    "def knapsackBU(weights, values, capacity, num_of_items):\n",
    "    memo = [[0]*(capacity+1) for i in range(num_of_items+1)]\n",
    "    \n",
    "    for i in range(0, num_of_items):\n",
    "        for j in range(1, capacity+1):\n",
    "            if j < weights[i]:\n",
    "                memo[i+1][j] = memo[i][j]\n",
    "            else:\n",
    "                memo[i+1][j] = max(memo[i][j], values[i]+memo[i][j-weights[i]])\n",
    "           # print(memo)    \n",
    "    return memo[num_of_items][capacity], memo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(7,\n",
       " [[0, 0, 0, 0, 0, 0],\n",
       "  [0, 0, 3, 3, 3, 3],\n",
       "  [0, 0, 3, 4, 4, 7],\n",
       "  [0, 0, 3, 4, 5, 7],\n",
       "  [0, 0, 3, 4, 5, 7]])"
      ]
     },
     "execution_count": 68,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "knapsackBU(weights, values, capacity, num_of_items)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(9,\n",
       " [[0, 0, 0, 0, 0, 0, 0, 0],\n",
       "  [0, 1, 1, 1, 1, 1, 1, 1],\n",
       "  [0, 1, 1, 4, 5, 5, 5, 5],\n",
       "  [0, 1, 1, 4, 5, 6, 6, 9],\n",
       "  [0, 1, 1, 4, 5, 7, 8, 9]])"
      ]
     },
     "execution_count": 69,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "knapsackBU([1, 3, 4, 5], [1, 4, 5, 7], 7, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {},
   "outputs": [],
   "source": [
    "def knapsackTD(weights, values, capacity, num_of_items):\n",
    "    def dp(memo, i, j):\n",
    "        #print(memo, i, j)\n",
    "        if i == 0:\n",
    "            return 0\n",
    "            \n",
    "        if j == 0:\n",
    "            return 0\n",
    "        \n",
    "        if memo[i][j] == -1:\n",
    "            if j >= weights[i-1]:\n",
    "                memo[i][j] = max(dp(memo, i-1, j), values[i-1] + dp(memo, i-1, j-weights[i-1]))\n",
    "            \n",
    "            else:\n",
    "                memo[i][j] = dp(memo, i-1, j)\n",
    "            \n",
    "        return memo[i][j]\n",
    "        \n",
    "    \n",
    "    memo = [[-1]*(capacity+1) for i in range(num_of_items+1)]\n",
    "    \n",
    "    return dp(memo, num_of_items, capacity)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "9"
      ]
     },
     "execution_count": 101,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "knapsackTD([1, 3, 4, 5], [1, 4, 5, 7], 7, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7"
      ]
     },
     "execution_count": 102,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "knapsackTD(weights, values, capacity, num_of_items)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Binary Search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://leetcode.com/problems/binary-search/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 166,
   "metadata": {},
   "outputs": [],
   "source": [
    "def search(nums, target):\n",
    "    left = 0\n",
    "    right = len(nums)-1\n",
    "\n",
    "    while left <=right:\n",
    "        mid = (right + left)//2\n",
    "        if target == nums[mid]:\n",
    "            return mid\n",
    "        elif target > nums[mid]:\n",
    "            left = mid+1\n",
    "        elif target < nums[mid]:\n",
    "            right = mid-1\n",
    "\n",
    "    return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 168,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-1"
      ]
     },
     "execution_count": 168,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "search([1, 2, 3, 4, 5, 6, ], 7)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Best Time to Buy and Sell Stock"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://leetcode.com/problems/best-time-to-buy-and-sell-stock/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 146,
   "metadata": {},
   "outputs": [],
   "source": [
    "def maxProfit(prices):\n",
    "    buy_sell_matrix =[[0] * len(prices) for x in range(len(prices))]\n",
    "    left = 0\n",
    "    right = 1\n",
    "    maximum_price = 0\n",
    "    \n",
    "    while left < right:\n",
    "        for it in range(left, len(prices)):\n",
    "            buy_sell_matrix[left][it] = prices[it] - prices[left]\n",
    "            if buy_sell_matrix[left][it] > maximum_price:\n",
    "                maximum_price = buy_sell_matrix[left][it] \n",
    "            right +=1\n",
    "\n",
    "        left+=1\n",
    "\n",
    "    return maximum_price"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 159,
   "metadata": {},
   "outputs": [],
   "source": [
    "def maxProfit(prices):\n",
    "    left = 0\n",
    "    right = 1\n",
    "    maximum_price = 0\n",
    "    \n",
    "    while left < right:\n",
    "        for it in range(left, len(prices)):\n",
    "            if prices[it] - prices[left] > maximum_price:\n",
    "                maximum_price = prices[it] - prices[left]\n",
    "            right +=1\n",
    "\n",
    "        left+=1\n",
    "\n",
    "    return maximum_price"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 163,
   "metadata": {},
   "outputs": [],
   "source": [
    "def maxProfit(prices):\n",
    "    left = 0\n",
    "    right = len(prices)-1\n",
    "    maximum_price = 0\n",
    "    \n",
    "    while left < right:\n",
    "        for it in range(left, len(prices)):\n",
    "            if prices[right] - min(prices[left:right+1]) > maximum_price:\n",
    "                maximum_price = prices[right] - min(prices[left:right+1])\n",
    "            right -=1\n",
    "\n",
    "        left+=1\n",
    "\n",
    "    return maximum_price"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 169,
   "metadata": {},
   "outputs": [],
   "source": [
    "def maxProfit(prices):\n",
    "    buy_min_price = prices[0]\n",
    "    sell_max_price = 0\n",
    "    \n",
    "    for i in range(1, len(prices)):\n",
    "        current_max_price = prices[i] - buy_min_price\n",
    "        \n",
    "        if current_max_price > sell_max_price:\n",
    "            sell_max_price = current_max_price\n",
    "            \n",
    "        if prices[i] < buy_min_price:\n",
    "            buy_min_price = prices[i]\n",
    "            \n",
    "        \n",
    "    return sell_max_price"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 170,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 170,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "maxProfit([7,1,5,3,6,4])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Valid Anagram"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://leetcode.com/problems/valid-anagram/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 171,
   "metadata": {},
   "outputs": [],
   "source": [
    "def isAnagram(s: str, t: str):\n",
    "#         s_dict = {}\n",
    "#         for l in s:\n",
    "#             if l in s_dict:\n",
    "#                 s_dict[l]+=1\n",
    "#             else:\n",
    "#                 s_dict[l]=1\n",
    "\n",
    "#         for k in t:\n",
    "#             if k not in s_dict:\n",
    "#                 return False\n",
    "#             else:\n",
    "#                  s_dict[k]-=1\n",
    "\n",
    "#         for val in s_dict.values():\n",
    "#             if val!=0:\n",
    "#                 return False\n",
    "\n",
    "#         return True\n",
    "\n",
    "    if sorted(s)!=sorted(t):\n",
    "        return False\n",
    "    else:\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 172,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 172,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isAnagram('eew', 'wee')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Search Insert Position"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.\n",
    "\n",
    "You must write an algorithm with O(log n) runtime complexity."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 173,
   "metadata": {},
   "outputs": [],
   "source": [
    "def searchInsert(nums, target) -> int:\n",
    "    left = 0\n",
    "    right = len(nums)-1\n",
    "\n",
    "    while left<=right:\n",
    "        med = (left+right)//2\n",
    "        if target == nums[med]:\n",
    "            return med\n",
    "        elif target > nums[med]:\n",
    "            if left == right:\n",
    "                return med+1\n",
    "            left = med+1\n",
    "        elif target < nums[med]:\n",
    "            if left == right:\n",
    "                return med\n",
    "            right = med"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Squares of a Sorted Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://leetcode.com/problems/squares-of-a-sorted-array/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Input: nums = [-4,-1,0,3,10]  \n",
    "Output: [0,1,9,16,100]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 9, 16, 100]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def sortedSquares(nums):\n",
    "    squared = [-1] * len(nums)\n",
    "    end = len(nums)-1\n",
    "    cnt = len(nums)-1\n",
    "    start = 0\n",
    "    while start<=end:\n",
    "        if abs(nums[start]) >= nums[end]:\n",
    "            squared[cnt] = nums[start] * nums[start]\n",
    "            start+=1\n",
    "            cnt-=1\n",
    "        else:\n",
    "            squared[cnt] = nums[end] * nums[end]\n",
    "            end-=1\n",
    "            cnt-=1\n",
    "    \n",
    "    return squared\n",
    "\n",
    "sortedSquares([-4,-1,0,3,10])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4, 9, 9, 49, 121]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sortedSquares([-7,-3,2,3,11])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Reverse Words in a String III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://leetcode.com/problems/reverse-words-in-a-string-iii/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Input: s = \"Let's take LeetCode contest\"  \n",
    "Output: \"s'teL ekat edoCteeL tsetnoc\"  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "s = \"Let's take LeetCode contest\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\"s'teL ekat edoCteeL tsetnoc\""
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def reverseWords(s):\n",
    "    ans = \" \".join([x[::-1] for x in s.split()])\n",
    "    return ans\n",
    "\n",
    "reverseWords(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Remove All Adjacent Duplicates In String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 125,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'sdas'"
      ]
     },
     "execution_count": 125,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def removeDuplicates(s):\n",
    "    st = ['']\n",
    "    for i in range(len(s)):\n",
    "        if s[i] != st[-1]:\n",
    "            st.append(s[i])\n",
    "        else:\n",
    "            st.pop(-1)\n",
    "\n",
    "    return \"\".join(st)\n",
    "\n",
    "\n",
    "removeDuplicates(\"sdasdd\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Flood Fill (not done)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://leetcode.com/problems/flood-fill/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, newColor = 2  \n",
    "Output: [[2,2,2],[2,2,0],[2,0,1]]  \n",
    "Explanation: From the center of the image with position (sr, sc) = (1, 1) (i.e., the red pixel), all pixels connected by a path of the same color as the starting pixel (i.e., the blue pixels) are colored with the new color.\n",
    "Note the bottom corner is not colored 2, because it is not 4-directionally connected to the starting pixel."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def floodFill(image, sr, sc, newColor):\n",
    "    "
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "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.8.6"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}