20_leetcode_revision.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "0e06142e",
   "metadata": {},
   "source": [
    "# 1. Two Sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "d18cb780",
   "metadata": {},
   "outputs": [],
   "source": [
    "def twoSum(nums, target):\n",
    "    index_map = {}\n",
    "    \n",
    "    for i in range(len(nums)):\n",
    "        ntf = target - nums[i]\n",
    "        if nums[i] not in index_map:\n",
    "            index_map[ntf] = i\n",
    "        else:\n",
    "            return [index_map[nums[i]], i]\n",
    "    return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "d70a9b31",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [2,4,3,7]\n",
    "target = 7\n",
    "\n",
    "twoSum(nums, target)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1ea16a9c",
   "metadata": {},
   "source": [
    "# 2. Three Sum to zero"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "70c77b39",
   "metadata": {},
   "outputs": [],
   "source": [
    "def threeSum(nums):\n",
    "    res = []\n",
    "    nums.sort()\n",
    "    \n",
    "    for i in range(len(nums)):\n",
    "        if nums[i] > 0:\n",
    "            break\n",
    "            \n",
    "        if i == 0 or nums[i] != nums[i-1]:\n",
    "            twoSum(nums, i, res)\n",
    "    \n",
    "    return res\n",
    "\n",
    "def twoSum(nums, i , res):\n",
    "    low = i + 1\n",
    "    high = len(nums) - 1\n",
    "    \n",
    "    while low < high:\n",
    "        sums = nums[i] + nums[low] + nums[high]\n",
    "        \n",
    "        if sums < 0:\n",
    "            low += 1\n",
    "        elif sums > 0:\n",
    "            high -= 1\n",
    "        else:\n",
    "            res.append([nums[i], nums[low], nums[high]])\n",
    "            low += 1\n",
    "            high -= 1\n",
    "            \n",
    "            while low < high and nums[low] == nums[low - 1]:\n",
    "                low += 1\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "9ae71fdb",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[-1, -1, 2], [-1, 0, 1]]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [-1,0,1,2,-1,-4]\n",
    "\n",
    "threeSum(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b4b06892",
   "metadata": {},
   "source": [
    "# 3. Palindrome number\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "80c22a8f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def palindromeNumber(x):\n",
    "    x = str(x)\n",
    "    \n",
    "    if '-' in x:\n",
    "        return False\n",
    "    \n",
    "    return x == x[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "358adc15",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "palindromeNumber(121)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2becf944",
   "metadata": {},
   "source": [
    "# 4. Roman to integer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "e3488417",
   "metadata": {},
   "outputs": [],
   "source": [
    "def romanToInt(s: str) -> int:\n",
    "    values = {\n",
    "    \"I\": 1,\n",
    "    \"V\": 5,\n",
    "    \"X\": 10,\n",
    "    \"L\": 50,\n",
    "    \"C\": 100,\n",
    "    \"D\": 500,\n",
    "    \"M\": 1000,\n",
    "}\n",
    "    left = 0\n",
    "    result = 0\n",
    "    \n",
    "    while left < len(s):\n",
    "        if left + 1 < len(s) and values[s[left + 1]] > values[s[left]]:\n",
    "            result += values[s[left + 1]] - values[s[left]]\n",
    "            left += 2\n",
    "        else:\n",
    "            result += values[s[left]]\n",
    "            left += 1\n",
    "    \n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "35008a93",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "58"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"LVIII\"\n",
    "\n",
    "romanToInt(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e5cdfaf9",
   "metadata": {},
   "source": [
    "# 5. Longest common prefix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "391b6f6e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def longestCommonPrefix(strs):\n",
    "    \n",
    "    result = []\n",
    "    \n",
    "    for i in zip(*strs):\n",
    "        if len(set(i)) == 1:\n",
    "            result.append(i[0])\n",
    "        else:\n",
    "            break\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "25fe40f6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['f', 'l']"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "strs = [\"flower\",\"flow\",\"flight\"]\n",
    "\n",
    "longestCommonPrefix(strs)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "654c57be",
   "metadata": {},
   "source": [
    "# 6. Valid parenthesis"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "e92faf39",
   "metadata": {},
   "outputs": [],
   "source": [
    "def isValid(s):\n",
    "    \n",
    "    parens = {\n",
    "        '(': ')',\n",
    "        '{': '}',\n",
    "        '[': ']'\n",
    "    }\n",
    "    \n",
    "    stack = []\n",
    "    \n",
    "    for c in s:\n",
    "        if c in parens.keys():\n",
    "            stack.append(c)\n",
    "        else:\n",
    "            if len(stack) > 0:\n",
    "                leftBracket = stack.pop()\n",
    "            else:\n",
    "                return False\n",
    "            correctBracket = parens[leftBracket]\n",
    "            if c != correctBracket:\n",
    "                return False\n",
    "            \n",
    "    return len(stack) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "837cd07a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"()[]{}\"\n",
    "\n",
    "isValid(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d15b2a8a",
   "metadata": {},
   "source": [
    "# 7. Merge two sorted lists"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "1662ac58",
   "metadata": {},
   "outputs": [],
   "source": [
    "def mergeTwoLists(list1, list2):\n",
    "    if list1 is None:\n",
    "        return list2\n",
    "    elif list2 is None:\n",
    "        return list1\n",
    "    elif list1.val < list2.val:\n",
    "        list1.next = mergeTwoLists(list1.next, list2)\n",
    "        return list1\n",
    "    else:\n",
    "        list2.next = mergeTwoLists(list1, list2.next)\n",
    "        return list2"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6fc6daa1",
   "metadata": {},
   "source": [
    "# 8. Remove duplicates from sorted array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "94931d8a",
   "metadata": {},
   "outputs": [],
   "source": [
    "def removeDuplicates(nums):\n",
    "    i = 0\n",
    "    \n",
    "    for j in range(len(nums)):\n",
    "        if nums[j] != nums[i]:\n",
    "            i += 1\n",
    "            nums[i] = nums[j]\n",
    "    return i + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "c974a1e4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [1,1,2]\n",
    "\n",
    "removeDuplicates(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "768a35ae",
   "metadata": {},
   "source": [
    "# 9. Remove element"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "5d2255e3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def removeElement(nums, val):\n",
    "    i = 0\n",
    "    \n",
    "    for j in range(len(nums)):\n",
    "        if nums[j] != val:\n",
    "            nums[i] = nums[j]\n",
    "            i += 1\n",
    "    return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "946e29ff",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [3,2,2,3,3]\n",
    "val = 3\n",
    "\n",
    "removeElement(nums, val)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3e771d7e",
   "metadata": {},
   "source": [
    "# 10. Search insert position"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "e979ca52",
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "def searchInsert(nums, target):\n",
    "    \n",
    "    left = 0\n",
    "    right = len(nums) - 1\n",
    "    \n",
    "    while left <= right:\n",
    "        mid = math.floor((left + right)/2)\n",
    "        if nums[mid] == target:\n",
    "            return mid\n",
    "        elif nums[mid] < target:\n",
    "            left = mid + 1\n",
    "        else:\n",
    "            right = mid - 1\n",
    "    return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "28066ae5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [1,3,5,6]\n",
    "target = 2\n",
    "\n",
    "searchInsert(nums, target)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6a50095a",
   "metadata": {},
   "source": [
    "# 11. Length of last word"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "18608418",
   "metadata": {},
   "outputs": [],
   "source": [
    "def lengthOfLastWord(s):\n",
    "    \n",
    "    right = len(s) - 1\n",
    "    \n",
    "    while right >= 0 and s[right] == ' ':\n",
    "        right -= 1\n",
    "    \n",
    "    length = 0\n",
    "    \n",
    "    while right >= 0 and s[right] != ' ':\n",
    "        length += 1\n",
    "        right -= 1\n",
    "    \n",
    "    return length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "a3776bd2",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"   fly me   to   the moon  \"\n",
    "lengthOfLastWord(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "21825cb1",
   "metadata": {},
   "source": [
    "# 12. Plus one"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "b7809b12",
   "metadata": {},
   "outputs": [],
   "source": [
    "def plusOne(digits):\n",
    "    \n",
    "    str_digits = [str(x) for x in digits]\n",
    "    str_number = \"\".join(str_digits)\n",
    "    int_number = int(str_number)\n",
    "    result = int_number + 1\n",
    "    str_result = str(result)\n",
    "    return [int(x) for x in str_result]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "02542c34",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 4]"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "digits = [1,2,3]\n",
    "\n",
    "plusOne(digits)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "50f40aa9",
   "metadata": {},
   "source": [
    "# 14. Add binary"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "ca9a5b5f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def addBinary(a, b):\n",
    "    return bin(int(a,2) + int(b,2)).replace('0b', '')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "233ae0f2",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'100'"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = \"11\"\n",
    "b = \"1\"\n",
    "\n",
    "addBinary(a, b)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e6ab0501",
   "metadata": {},
   "source": [
    "# 15. Sqrt X"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "e27bc7ef",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sqrt(x):\n",
    "    \n",
    "    left = 0\n",
    "    right = x // 2\n",
    "    \n",
    "    while left <= right:\n",
    "        mid = math.floor((left + right)/2)\n",
    "        if mid * mid == x:\n",
    "            return mid\n",
    "        elif mid * mid < x:\n",
    "            left = mid + 1\n",
    "        else:\n",
    "            right = mid - 1\n",
    "    return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "c0eeb1da",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sqrt(25)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fceef65a",
   "metadata": {},
   "source": [
    "# 16. Climbing stairs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "cf13df50",
   "metadata": {},
   "outputs": [],
   "source": [
    "def climbStairs(n):\n",
    "    \n",
    "    if n == 1:\n",
    "        return 1\n",
    "    \n",
    "    first = 1\n",
    "    second = 2\n",
    "    third = 0\n",
    "    \n",
    "    for _ in range(3, n+1):\n",
    "        third = first + second\n",
    "        first = second\n",
    "        second = third\n",
    "    \n",
    "    return second"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "2d440554",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "climbStairs(4)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "861ea7c4",
   "metadata": {},
   "source": [
    "# 17. Remove duplicates from sorted linked list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "f5dcb8fa",
   "metadata": {},
   "outputs": [],
   "source": [
    "def deleteDuplicates(head):\n",
    "    \n",
    "    curr = head\n",
    "    \n",
    "    while curr and curr.next:\n",
    "        if curr.val == curr.next.val:\n",
    "            curr.next = curr.next.next\n",
    "        else:\n",
    "            curr = curr.next\n",
    "    return head"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "734abbe1",
   "metadata": {},
   "source": [
    "# 18. Merge sorted array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "id": "416ef184",
   "metadata": {},
   "outputs": [],
   "source": [
    "def merge(nums1, m, nums2, n):\n",
    "    \n",
    "    nums1_copy = nums1[:m]\n",
    "    p1 = 0\n",
    "    p2 = 0\n",
    "    \n",
    "    for i in range(m + n):\n",
    "        if p2 >= n or (p1 < m and nums1_copy[p1] <= nums2[p2]):\n",
    "            nums1[i] = nums1_copy[p1]\n",
    "            p1 += 1\n",
    "        else:\n",
    "            nums1[i] = nums2[p2]\n",
    "            p2 += 1\n",
    "    return nums1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "id": "3530b848",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 2, 3, 5, 6]"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums1 = [1,2,3,0,0,0]\n",
    "m = 3\n",
    "nums2 = [2,5,6]\n",
    "n = 3\n",
    "\n",
    "merge(nums1, m, nums2, n)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1f7502e4",
   "metadata": {},
   "source": [
    "# 19. Binary tree in order traversal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "id": "a914182b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def inorderTraversal(root):\n",
    "    \n",
    "    if root is None:\n",
    "        return\n",
    "    \n",
    "    result = []\n",
    "    \n",
    "    def dfsInOrder(node, result):\n",
    "        if node.left is not None:\n",
    "            dfsInOrder(node.left, result)\n",
    "        \n",
    "        result.append(node.val)\n",
    "        \n",
    "        if node.right is not None:\n",
    "            dfsInOrder(node.right, result)\n",
    "    \n",
    "    dfsInOrder(root)\n",
    "    return result"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "20559373",
   "metadata": {},
   "source": [
    "# 20. Same tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "id": "bbfaaf4e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def isSameTree(p,q):\n",
    "    \n",
    "    if not p and not q:\n",
    "        return True\n",
    "    if not p or not q:\n",
    "        return False\n",
    "    if p.val != q.val:\n",
    "        return False\n",
    "    return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "821644e7",
   "metadata": {},
   "source": [
    "# 21. Symmetric tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "id": "5f6dd76c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def isSymmetricTree(p,q):\n",
    "    if not p and not q:\n",
    "        return True\n",
    "    if not p or not q:\n",
    "        return False\n",
    "    if p.val != q.val:\n",
    "        return False\n",
    "    return isSymmetricTree(p.left, q.right) and isSymmetricTree(p.right, q.left)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "29fb622b",
   "metadata": {},
   "source": [
    "# 22. Max depth"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "id": "b76b1438",
   "metadata": {},
   "outputs": [],
   "source": [
    "def maxDepth(root):\n",
    "    if not root:\n",
    "        return None\n",
    "    else:\n",
    "        leftHeight = maxDepth(root.left)\n",
    "        rightHeight = maxDepth(root.right)\n",
    "        return max(leftHeight, rightHeight) + 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2e178f91",
   "metadata": {},
   "source": [
    "# 23. Sorted array to binary search tre"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "id": "9ad486b5",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sortedArrayToBST(nums):\n",
    "    \n",
    "    left = 0\n",
    "    right = len(nums) - 1\n",
    "    \n",
    "    def helper(left, right):\n",
    "        if left > right:\n",
    "            return None\n",
    "        \n",
    "        mid = math.floor((left + right)/2)\n",
    "        \n",
    "        root = TreeNode(nums[mid])\n",
    "        root.left = helper(left, mid - 1)\n",
    "        root.right = helper(mid + 1, right)\n",
    "        return root\n",
    "    \n",
    "    return helper(left, right)\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9c1c1189",
   "metadata": {},
   "source": [
    "# 24. Balanced Binary tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "id": "8766757a",
   "metadata": {},
   "outputs": [],
   "source": [
    "def isBalanced(root):\n",
    "    \n",
    "    def getHeight(node):\n",
    "        if node is None:\n",
    "            return None\n",
    "        else:\n",
    "            return max(getHeight(node.left), getHeight(node.right)) + 1\n",
    "    \n",
    "    return abs(getHeight(root.left) - getHeight(root.right)) < 2 and isBalanced(root.left) and isBalanced(root.right)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "edb1247f",
   "metadata": {},
   "source": [
    "# 25. Minimum depth of binary tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "id": "ecdc40cb",
   "metadata": {},
   "outputs": [],
   "source": [
    "def minDepth(root):\n",
    "    if root is None:\n",
    "        return 0\n",
    "    \n",
    "    children = [root.left, root.right]\n",
    "    \n",
    "    if not any(children):\n",
    "        return 1\n",
    "    \n",
    "    min_depth = float('inf')\n",
    "    \n",
    "    for c in children:\n",
    "        if c is not None:\n",
    "            min_depth = min(min_depth, minDepth(c))\n",
    "    \n",
    "    return min_depth"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2be1d03f",
   "metadata": {},
   "source": [
    "# 26. Path Sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "id": "c38a2597",
   "metadata": {},
   "outputs": [],
   "source": [
    "def hasPathSum(root, targetSum):\n",
    "    \n",
    "    if root is None:\n",
    "        return False\n",
    "    \n",
    "    queue = []\n",
    "    \n",
    "    queue.append([root, targetSum - root.val])\n",
    "    \n",
    "    while queue:\n",
    "        currNode, currVal = queue.pop(0)\n",
    "        \n",
    "        if currVal == 0 and currNode.left is None and currNode.right is None:\n",
    "            return True\n",
    "        \n",
    "        if currNode.left is not None:\n",
    "            queue.append([currNode.left, currVal - currNode.left.val])\n",
    "        \n",
    "        if currNode.right is not None:\n",
    "            queue.append([currNode.right, currVal - currNode.right.val])\n",
    "    \n",
    "    return False"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0ccda5fe",
   "metadata": {},
   "source": [
    "# 27. Best time to buy and sell stock"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "id": "04a9f64a",
   "metadata": {},
   "outputs": [],
   "source": [
    "def maxProfit(prices):\n",
    "    min_price = float('inf')\n",
    "    max_profit = 0\n",
    "    \n",
    "    for price in prices:\n",
    "        if price < min_price:\n",
    "            min_price = price\n",
    "        elif price - min_price > max_profit:\n",
    "            max_profit = price - min_price\n",
    "    return max_profit"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b1f6ff40",
   "metadata": {},
   "source": [
    "# 28. Valid palindrome"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "id": "b5426764",
   "metadata": {},
   "outputs": [],
   "source": [
    "def isPalindrome(s):\n",
    "    \n",
    "    left = 0\n",
    "    right = len(s) - 1\n",
    "    \n",
    "    while left < right:\n",
    "        while left < right and not s[left].isalnum():\n",
    "            left += 1\n",
    "        while left < right and not s[right].isalnum():\n",
    "            right -= 1\n",
    "        \n",
    "        if s[left].lower() != s[right].lower():\n",
    "            return False\n",
    "        \n",
    "        left += 1\n",
    "        right -= 1\n",
    "    \n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "id": "ce500fa1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"A man, a plan, a canal: Panama\"\n",
    "\n",
    "isPalindrome(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ee58bfa2",
   "metadata": {},
   "source": [
    "# 29. Almost Palindrome"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "id": "d4ad589e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def almostPalindrome(s):\n",
    "    \n",
    "    def checkPalindrome(s, i, j):\n",
    "        while i < j:\n",
    "            if s[i] != s[j]:\n",
    "                return False\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        return True\n",
    "    \n",
    "    left = 0\n",
    "    right = len(s) - 1\n",
    "    \n",
    "    while left < right:\n",
    "        if s[left] != s[right]:\n",
    "            return checkPalindrome(s, left + 1, right) or checkPalindrome(s, left, right - 1)\n",
    "        left += 1\n",
    "        right -= 1\n",
    "    \n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "id": "a0d807f3",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"abade\"\n",
    "almostPalindrome(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "978fadb1",
   "metadata": {},
   "source": [
    "# 30. Typed out strings"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "id": "b6a96730",
   "metadata": {},
   "outputs": [],
   "source": [
    "def backspaceCompare(s, t):\n",
    "    \n",
    "    stack_s = []\n",
    "    stack_t = []\n",
    "    \n",
    "    for c in s:\n",
    "        if c != '#':\n",
    "            stack_s.append(c)\n",
    "        else:\n",
    "            if len(stack_s) > 0:\n",
    "                stack_s.pop()\n",
    "    \n",
    "    for c in t:\n",
    "        if c != '#':\n",
    "            stack_t.append(c)\n",
    "        else:\n",
    "            if len(stack_t) > 0:\n",
    "                stack_t.pop()\n",
    "    \n",
    "    return stack_s == stack_t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "id": "5bd185dd",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 74,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = 'ad##'\n",
    "t = 'bc##'\n",
    "\n",
    "backspaceCompare(s,t)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bd9b385e",
   "metadata": {},
   "source": [
    "# 31. Longest Substring without repeating characters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "id": "4bffcad5",
   "metadata": {},
   "outputs": [],
   "source": [
    "def lengthOfLongestSubstring(s):\n",
    "    seenChars = {}\n",
    "    longest = 0\n",
    "    left = 0\n",
    "    \n",
    "    for right in range(len(s)):\n",
    "        currentChar = s[right]\n",
    "        \n",
    "        prevSeenChar = -1\n",
    "        \n",
    "        if currentChar in seenChars:\n",
    "            prevSeenChar = seenChars[currentChar]\n",
    "        \n",
    "        if prevSeenChar >= left:\n",
    "            left = prevSeenChar + 1\n",
    "        \n",
    "        seenChars[currentChar] = right\n",
    "        longest = max(longest, right - left + 1)\n",
    "    \n",
    "    return longest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "id": "42079646",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 76,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"abcdeabcbb\"\n",
    "lengthOfLongestSubstring(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7a40a99c",
   "metadata": {},
   "source": [
    "# 32. Reverse a linked list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "id": "8cc2b9d2",
   "metadata": {},
   "outputs": [],
   "source": [
    "def reverseList(head):\n",
    "    \n",
    "    curr = head\n",
    "    prev = None\n",
    "    \n",
    "    while curr:\n",
    "        nextTmp = curr.next\n",
    "        curr.next = prev\n",
    "        prev = curr\n",
    "        curr = nextTmp\n",
    "    \n",
    "    return head"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6889e662",
   "metadata": {},
   "source": [
    "# 33. Min remove to make valid parenthesis"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "id": "fd414acd",
   "metadata": {},
   "outputs": [],
   "source": [
    "def minRemoveToMakeValid(s):\n",
    "    \n",
    "    stack = []\n",
    "    indexes_to_remove = set()\n",
    "    \n",
    "    for index, c in enumerate(s):\n",
    "        if c not in '()':\n",
    "            continue\n",
    "        elif c == '(':\n",
    "            stack.append(index)\n",
    "        elif not stack:\n",
    "            indexes_to_remove.add(index)\n",
    "        else:\n",
    "            stack.pop()\n",
    "    \n",
    "    indexes_to_remove = indexes_to_remove.union(set(stack))\n",
    "    \n",
    "    stringBuilder = []\n",
    "    \n",
    "    for i in range(len(s)):\n",
    "        if i not in indexes_to_remove:\n",
    "            stringBuilder.append(s[i])\n",
    "    \n",
    "    return \"\".join(stringBuilder)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "id": "8dc8e476",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'lee(t(c)o)de'"
      ]
     },
     "execution_count": 79,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "minRemoveToMakeValid('lee(t(c)o)de)')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "id": "90c092c8",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "''"
      ]
     },
     "execution_count": 80,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "minRemoveToMakeValid('))((')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ab8f10a8",
   "metadata": {},
   "source": [
    "# 34. Find Kth largest element"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "id": "65db485b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def findKthLargest(nums, k):\n",
    "    indexToFind = len(nums) - k\n",
    "    quickselect(nums, 0, len(nums) - 1, indexToFind)\n",
    "    return nums[-k]\n",
    "\n",
    "def quickselect(nums, left, right, targetIndex):\n",
    "    partitionIndex = partition(nums, left, right)\n",
    "    \n",
    "    if partitionIndex == targetIndex:\n",
    "        return nums[targetIndex]\n",
    "    elif partitionIndex < targetIndex:\n",
    "        return quickselect(nums, partitionIndex + 1, right, targetIndex)\n",
    "    else:\n",
    "        return quickselect(nums, left, partitionIndex - 1, targetIndex)\n",
    "\n",
    "def partition(nums, left, right):\n",
    "    partitionIndex = left\n",
    "    pivotElement = nums[right]\n",
    "    \n",
    "    for i in range(left, right):\n",
    "        if nums[i] <= pivotElement:\n",
    "            nums[i], nums[partitionIndex] = nums[partitionIndex], nums[i]\n",
    "            partitionIndex += 1\n",
    "    nums[partitionIndex], nums[right] = nums[right], nums[partitionIndex]\n",
    "    return partitionIndex"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "id": "1318cfa8",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 83,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [3,2,1,5,6,4]\n",
    "k = 2\n",
    "findKthLargest(nums, k)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1730ac2d",
   "metadata": {},
   "source": [
    "# 35. Find kth Smallest element"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "id": "720bc246",
   "metadata": {},
   "outputs": [],
   "source": [
    "def findKthSmallest(nums, k):\n",
    "    targetIndex = quickselect(nums, 0, len(nums) - 1, k - 1)\n",
    "    return nums[targetIndex]\n",
    "\n",
    "def quickselect(nums, left, right, targetIndex):\n",
    "    partitionIndex = partition(nums, left, right)\n",
    "    \n",
    "    if partitionIndex == targetIndex:\n",
    "        return targetIndex\n",
    "    elif partitionIndex > targetIndex:\n",
    "        return quickselect(nums, left, partitionIndex - 1, targetIndex)\n",
    "    else:\n",
    "        return quickselect(nums, partitionIndex + 1, right, targetIndex)\n",
    "\n",
    "def partition(nums, left, right):\n",
    "    partitionIndex = left\n",
    "    pivotElement = nums[right]\n",
    "    \n",
    "    for j in range(left, right):\n",
    "        if nums[j] <= pivotElement:\n",
    "            nums[j], nums[partitionIndex] = nums[partitionIndex], nums[j]\n",
    "            partitionIndex += 1\n",
    "    nums[partitionIndex], nums[right] = nums[right], nums[partitionIndex]\n",
    "    return partitionIndex"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "id": "5c384af8",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 85,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [3,2,1,5,6,4]\n",
    "k = 2\n",
    "findKthSmallest(nums, k)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "31aa76b9",
   "metadata": {},
   "source": [
    "# 36. Start and end of a target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "id": "d0d0b69f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def start_and_end(nums, target):\n",
    "    \n",
    "    if len(nums) == 0:\n",
    "        return [-1, -1]\n",
    "    \n",
    "    left = 0\n",
    "    right = len(nums) - 1\n",
    "    \n",
    "    firstPosition = binarySearch(nums, left, right, target)\n",
    "    \n",
    "    if firstPosition == -1:\n",
    "        return [-1, -1]\n",
    "    \n",
    "    temp1 = 0\n",
    "    temp2 = 0\n",
    "    startPosition = firstPosition\n",
    "    endPosition = firstPosition\n",
    "    \n",
    "    while startPosition != -1:\n",
    "        temp1 = startPosition\n",
    "        startPosition = binarySearch(nums, left, startPosition - 1, target)\n",
    "    startPosition = temp1\n",
    "    \n",
    "    while endPosition != -1:\n",
    "        temp2 = endPosition\n",
    "        endPosition = binarySearch(nums, endPosition + 1, right, target)\n",
    "    endPosition = temp2\n",
    "    \n",
    "    return [startPosition, endPosition]\n",
    "\n",
    "def binarySearch(nums, left, right, target):\n",
    "    \n",
    "    while left <= right:\n",
    "        mid = math.floor((left + right)/2)\n",
    "        if nums[mid] == target:\n",
    "            return mid\n",
    "        elif nums[mid] < target:\n",
    "            left = mid + 1\n",
    "        else:\n",
    "            right = mid - 1\n",
    "    return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "id": "19863672",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2]"
      ]
     },
     "execution_count": 87,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [5,7,7,8,8,10]\n",
    "\n",
    "start_and_end(nums, 7)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1267bff7",
   "metadata": {},
   "source": [
    "# 37. Level Order of binary tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "id": "122781e3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def levelOrder(root):\n",
    "    if root is None:\n",
    "        return None\n",
    "    \n",
    "    result = []\n",
    "    queue = [root]\n",
    "    \n",
    "    while queue:\n",
    "        queue_length = len(queue)\n",
    "        currentLevelValues = []\n",
    "        counter = 0\n",
    "        \n",
    "        while counter < queue_length:\n",
    "            currNode = queue.pop(0)\n",
    "            currentLevelValues.append(currNode.val)\n",
    "            \n",
    "            if currNode.left is not None:\n",
    "                queue.append(currNode.left)\n",
    "            \n",
    "            if currNode.right is not None:\n",
    "                queue.append(currNode.right)\n",
    "            counter += 1\n",
    "        result.append(currentLevelValues)\n",
    "    return result"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "088891a6",
   "metadata": {},
   "source": [
    "# 38. Number of Islands"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "id": "fa68999a",
   "metadata": {},
   "outputs": [],
   "source": [
    "directions = [[-1, 0], [0, 1], [1, 0], [0, -1]]\n",
    "\n",
    "def numIslands(grid):\n",
    "    if len(grid) == 0:\n",
    "        return 0\n",
    "    \n",
    "    rows, cols = len(grid), len(grid[0])\n",
    "    islandCount = 0\n",
    "    \n",
    "    for row in range(rows):\n",
    "        for col in range(cols):\n",
    "            if grid[row][col] == '1':\n",
    "                islandCount += 1\n",
    "                grid[row][col] = '0'\n",
    "                queue = []\n",
    "                queue.append([row, col])\n",
    "                while queue:\n",
    "                    currNode = queue.pop(0)\n",
    "                    currRow = currNode[0]\n",
    "                    currCol = currNode[1]\n",
    "                    \n",
    "                    for i in range(len(directions)):\n",
    "                        direction = directions[i]\n",
    "                        nextRow = currRow + direction[0]\n",
    "                        nextCol = currCol + direction[1]\n",
    "                        \n",
    "                        if nextRow < 0 or nextRow >= len(grid) or nextCol < 0 or nextCol >= len(grid[0]):\n",
    "                            continue\n",
    "                        \n",
    "                        if grid[nextRow][nextCol] == '1':\n",
    "                            grid[nextRow][nextCol] = '0'\n",
    "                            queue.append([nextRow, nextCol])\n",
    "    return islandCount"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "id": "05b6b8d3",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 90,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grid = [\n",
    "  [\"1\",\"1\",\"1\",\"1\",\"0\"],\n",
    "  [\"1\",\"1\",\"0\",\"0\",\"0\"],\n",
    "  [\"1\",\"1\",\"0\",\"1\",\"1\"],\n",
    "  [\"0\",\"0\",\"1\",\"0\",\"1\"]\n",
    "]\n",
    "\n",
    "numIslands(grid)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a09a6b61",
   "metadata": {},
   "source": [
    "# 39. Rotting Oranges"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "id": "000315a4",
   "metadata": {},
   "outputs": [],
   "source": [
    "def orangesRotting(grid):\n",
    "    rows, cols = len(grid), len(grid[0])\n",
    "    freshOranges = 0\n",
    "    queue = []\n",
    "    \n",
    "    for row in range(rows):\n",
    "        for col in range(cols):\n",
    "            if grid[row][col] == 1:\n",
    "                freshOranges += 1\n",
    "            elif grid[row][col] == 2:\n",
    "                queue.append([row, col])\n",
    "    \n",
    "    queue.append([-1, -1])\n",
    "    \n",
    "    minutesElapsed = -1\n",
    "    \n",
    "    directions = [[-1, 0], [0, 1], [1, 0], [0, -1]]\n",
    "    \n",
    "    while queue:\n",
    "        currNode = queue.pop(0)\n",
    "        currRow = currNode[0]\n",
    "        currCol = currNode[1]\n",
    "        \n",
    "        if currRow == -1:\n",
    "            minutesElapsed += 1\n",
    "            if len(queue) > 0:\n",
    "                queue.append([-1, -1])\n",
    "        else:\n",
    "            for i in range(len(directions)):\n",
    "                direction = directions[i]\n",
    "                nextRow = currRow + direction[0]\n",
    "                nextCol = currCol + direction[1]\n",
    "                \n",
    "                if nextRow < 0 or nextRow >= len(grid) or nextCol < 0 or nextCol >= len(grid[0]):\n",
    "                    continue\n",
    "                    \n",
    "                if grid[nextRow][nextCol] == 1:\n",
    "                    grid[nextRow][nextCol] = 2\n",
    "                    freshOranges -= 1\n",
    "                    queue.append([nextRow, nextCol])\n",
    "    return minutesElapsed if freshOranges == 0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "id": "1bbbe396",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 92,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grid = [[2,1,1],[1,1,0],[0,1,1]]\n",
    "\n",
    "orangesRotting(grid)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "81c686bf",
   "metadata": {},
   "source": [
    "# 40. Walls and gates"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "id": "5a516507",
   "metadata": {},
   "outputs": [],
   "source": [
    "directions = [[-1, 0], [0, 1], [1, 0], [0, -1]]\n",
    "\n",
    "def wallsAndGates(matrix):\n",
    "    WALL = -1\n",
    "    GATE = 0\n",
    "    EMPTY = 2147483647\n",
    "    \n",
    "    rows, cols = len(matrix), len(matrix[0])\n",
    "    \n",
    "    for row in range(rows):\n",
    "        for col in range(cols):\n",
    "            if matrix[row][col] == GATE:\n",
    "                dfs(matrix, row, col, 0)\n",
    "\n",
    "def dfs(matrix, row, col, currentStep):\n",
    "    directions = [[-1, 0], [0, 1], [1, 0], [0, -1]]\n",
    "    \n",
    "    if row < 0 or row >= len(matrix) or col < 0 or col >= len(matrix[0]) or matrix[row][col] < currentStep:\n",
    "        return None\n",
    "    \n",
    "    if matrix[row][col] == -1:\n",
    "        return\n",
    "    \n",
    "    matrix[row][col] = currentStep\n",
    "    \n",
    "    for i in range(len(directions)):\n",
    "        direction = directions[i]\n",
    "        nextRow = row + direction[0]\n",
    "        nextCol = col + direction[1]\n",
    "        \n",
    "        dfs(matrix, nextRow, nextCol, currentStep + 1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "id": "b617d5ce",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[3, -1, 0, 1], [2, 2, 1, -1], [1, -1, 2, -1], [0, -1, 3, 4]]"
      ]
     },
     "execution_count": 94,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rooms = [[2147483647,-1,0,2147483647],\n",
    "         [2147483647,2147483647,2147483647,-1],\n",
    "         [2147483647,-1,2147483647,-1],\n",
    "         [0,-1,2147483647,2147483647]]\n",
    "\n",
    "wallsAndGates(rooms)\n",
    "\n",
    "rooms"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f12a4c9a",
   "metadata": {},
   "source": [
    "# 41. Trapping rainwater"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "a9d41561",
   "metadata": {},
   "outputs": [],
   "source": [
    "def rainWater(height):\n",
    "    left_p = 0\n",
    "    right_p = len(height) - 1\n",
    "    max_left = 0\n",
    "    max_right = 0\n",
    "    total_water = 0\n",
    "    \n",
    "    while left_p < right_p:\n",
    "        if height[left_p] < height[right_p]:\n",
    "            if height[left_p] < max_left:\n",
    "                total_water += max_left - height[left_p]\n",
    "            else:\n",
    "                max_left = height[left_p]\n",
    "            left_p += 1\n",
    "        \n",
    "        else:\n",
    "            if height[right_p] < max_right:\n",
    "                total_water += max_right - height[right_p]\n",
    "            else:\n",
    "                max_right = height[right_p]\n",
    "            right_p -= 1\n",
    "    \n",
    "    return total_water"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "b672b674",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "elevationArray = [0,1,0,2,1,0,1,3,2,1,2,1]\n",
    "\n",
    "rainWater(elevationArray)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "497d9235",
   "metadata": {},
   "source": [
    "# 42. Single number"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "67a0495a",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "\n",
    "def singleNumber(nums):\n",
    "    count_num = Counter(nums)\n",
    "    \n",
    "    for num in nums:\n",
    "        if count_num[num] == 1:\n",
    "            return num\n",
    "    return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "613277ec",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [2,2,1]\n",
    "\n",
    "singleNumber(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aa131a0f",
   "metadata": {},
   "source": [
    "# 43. Linked List cycle"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "07ac2d82",
   "metadata": {},
   "outputs": [],
   "source": [
    "def hasCycle(head):\n",
    "    \n",
    "    if head is None:\n",
    "        return False\n",
    "    \n",
    "    tortoise = head\n",
    "    hare = head\n",
    "    \n",
    "    while hare is not None and hare.next is not None:\n",
    "        hare = hare.next.next\n",
    "        tortoise = tortoise.next\n",
    "        if hare == tortoise:\n",
    "            return True\n",
    "    return False"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a298b97b",
   "metadata": {},
   "source": [
    "# 44. Binary tree post order traversal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "1b771556",
   "metadata": {},
   "outputs": [],
   "source": [
    "def postOrder(root):\n",
    "    \n",
    "    if root is None:\n",
    "        return None\n",
    "    \n",
    "    result = []\n",
    "    \n",
    "    def dfsPostOrder(node, result):\n",
    "        if node.left is not None:\n",
    "            dfsPostOrder(node.left, result)\n",
    "        \n",
    "        if node.right is not None:\n",
    "            dfsPostOrder(node.right, result)\n",
    "            \n",
    "        result.append(node.val)\n",
    "    \n",
    "    dfsPostOrder(root)\n",
    "    \n",
    "    return result"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "97f1b6e9",
   "metadata": {},
   "source": [
    "# 45. Right side view of the tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "b8c4b74b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def right_view_bfs(root):\n",
    "    result = []\n",
    "    level = 0\n",
    "    return traversePreOrder(root, level, result)\n",
    "\n",
    "def traversePreOrder(node, level, result):\n",
    "    if not node:\n",
    "        return None\n",
    "    \n",
    "    if level >= len(result):\n",
    "        result.append(node.val)\n",
    "        \n",
    "    if node.right is not None:\n",
    "        traversePreOrder(node.right, level + 1, result)\n",
    "    \n",
    "    if node.left is not None:\n",
    "        traversePreOrder(node.left, level + 1, result)\n",
    "    \n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "157c5419",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}