18_leetcode_easy_medium_fourth_round.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "fa993037",
   "metadata": {},
   "source": [
    "# 1. Two Sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "e924a120",
   "metadata": {},
   "outputs": [],
   "source": [
    "def twoSum(nums, target):\n",
    "    \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": 6,
   "id": "a98df310",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [2,4,3,7]\n",
    "target = 7\n",
    "\n",
    "twoSum(nums, target)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "816e9597",
   "metadata": {},
   "source": [
    "# 2. Two Sum II"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "a20663a7",
   "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 + 1\n",
    "        else:\n",
    "            return [index_map[nums[i]], i + 1]\n",
    "    return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "a97e68c0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 3]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [2,4,3,7]\n",
    "target = 5\n",
    "\n",
    "twoSum(nums, target)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9ae1cdda",
   "metadata": {},
   "source": [
    "# 3. Three Sum to zero"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "adf7acb3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def threeSum(nums):\n",
    "    \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": 14,
   "id": "2c1dc1f5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[-1, -1, 2], [-1, 0, 1]]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [-1,0,1,2,-1,-4]\n",
    "\n",
    "threeSum(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "77c750a8",
   "metadata": {},
   "source": [
    "# 4. Palindrome number"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "986fbc28",
   "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": 17,
   "id": "00510477",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "palindromeNumber(121)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5e8c3850",
   "metadata": {},
   "source": [
    "# 5. Roman to integer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "4549ba08",
   "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",
    "    \n",
    "    left = 0\n",
    "    result = 0\n",
    "    \n",
    "    while left < len(s):\n",
    "        if left + 1 < len(s) and values[s[left]] < values[s[left + 1]]:\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": 19,
   "id": "73f5671e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "58"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"LVIII\"\n",
    "\n",
    "romanToInt(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "94902e27",
   "metadata": {},
   "source": [
    "# 6. Longest Common prefix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "0fb4403f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def longestCommonPrefix(strs):\n",
    "    result = []\n",
    "    \n",
    "    for c in zip(*strs):\n",
    "        if len(set(c)) == 1:\n",
    "            result.append(c[0])\n",
    "        else:\n",
    "            break\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "23253c76",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['f', 'l']"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "strs = [\"flower\",\"flow\",\"flight\"]\n",
    "\n",
    "longestCommonPrefix(strs)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e9b6e7f3",
   "metadata": {},
   "source": [
    "# 7. Valid Parenthesis"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "87749d7d",
   "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 correctBracket != c:\n",
    "                return False\n",
    "    return len(stack) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "dcd9b69c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"()[]{}\"\n",
    "\n",
    "isValid(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "adefceb4",
   "metadata": {},
   "source": [
    "# 8. Merge two sorted lists"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "8837e3e5",
   "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": "94afe605",
   "metadata": {},
   "source": [
    "# 9. Remove duplicates from sorted array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "2c128959",
   "metadata": {},
   "outputs": [],
   "source": [
    "def removeDuplicates(nums):\n",
    "    i = 0\n",
    "    \n",
    "    for j in range(len(nums)):\n",
    "        if nums[i] != nums[j]:\n",
    "            i += 1\n",
    "            nums[i] = nums[j]\n",
    "    return i + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "d12fd5d9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [1,1,2]\n",
    "\n",
    "removeDuplicates(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5b793729",
   "metadata": {},
   "source": [
    "# 10. Remove element"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "1a74fe16",
   "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": 40,
   "id": "6c22a10e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [3,2,2,3,3]\n",
    "val = 3\n",
    "\n",
    "removeElement(nums, val)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "491e34b2",
   "metadata": {},
   "source": [
    "# 11. Search insert position"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "3196e510",
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "def searchInsert(nums, target):\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": 42,
   "id": "01018811",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [1,3,5,6]\n",
    "target = 2\n",
    "\n",
    "searchInsert(nums, target)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ab198a31",
   "metadata": {},
   "source": [
    "# 12. Length of last word\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "e032eefe",
   "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",
    "        right -= 1\n",
    "        length += 1\n",
    "    \n",
    "    return length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "bddfdf88",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"   fly me   to   the moon  \"\n",
    "lengthOfLastWord(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "41b44c54",
   "metadata": {},
   "source": [
    "# 13. Plus One"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "6ca00380",
   "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": 46,
   "id": "439790d5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 4]"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "digits = [1,2,3]\n",
    "\n",
    "plusOne(digits)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fc23ae59",
   "metadata": {},
   "source": [
    "# 14. Add binary"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "c91d9428",
   "metadata": {},
   "outputs": [],
   "source": [
    "def addBinary(a, b):\n",
    "    return bin(int(a,2) + int(b,2)).replace('0b', '')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "id": "5cef6aca",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'100'"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = \"11\"\n",
    "b = \"1\"\n",
    "\n",
    "addBinary(a, b)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e2a0a546",
   "metadata": {},
   "source": [
    "# 15. Sqrt x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "8d2379cc",
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "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": 7,
   "id": "c509978c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sqrt(9)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a9c3007d",
   "metadata": {},
   "source": [
    "# 16. Climbing stairs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "id": "a1611070",
   "metadata": {},
   "outputs": [],
   "source": [
    "def climbStairs(n):\n",
    "    \n",
    "    if n == 1:\n",
    "        return 1\n",
    "    \n",
    "    first = 1\n",
    "    second = 2\n",
    "    \n",
    "    third = 0\n",
    "    \n",
    "    for _ in range(3, n+1):\n",
    "        third = first + second\n",
    "        first = second\n",
    "        second = third\n",
    "    return second"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "id": "8d279b7c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "climbStairs(4)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ec04e1d2",
   "metadata": {},
   "source": [
    "# 17. Remove duplicates from sorted linked list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "c2e68dc7",
   "metadata": {},
   "outputs": [],
   "source": [
    "def deleteDuplicates(head):\n",
    "    curr = head\n",
    "    \n",
    "    while curr is not None and curr.next is not None:\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": "99cb1713",
   "metadata": {},
   "source": [
    "# 18. Merge sorted array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "id": "2fb0679c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def merge(nums1, m, nums2, n):\n",
    "    nums1_copy = nums1[:m]\n",
    "    \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": 56,
   "id": "e7436297",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 2, 3, 5, 6]"
      ]
     },
     "execution_count": 56,
     "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": "c8663363",
   "metadata": {},
   "source": [
    "# 19. Binary tree in order traversal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "19ced3d1",
   "metadata": {},
   "outputs": [],
   "source": [
    "def inorderTraversal(root):\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, result)\n",
    "    \n",
    "    return result"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "91cbf275",
   "metadata": {},
   "source": [
    "# 20. Same tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "id": "a0e2bba9",
   "metadata": {},
   "outputs": [],
   "source": [
    "def isSameTree(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 isSameTree(p.left, q.left) and isSameTree(p.right, q.right)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "24ded94a",
   "metadata": {},
   "source": [
    "# 21. Symmetric tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "id": "fb907f3d",
   "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": "6cc6947a",
   "metadata": {},
   "source": [
    "# 22. Max Depth"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "id": "6e889d65",
   "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": "81711920",
   "metadata": {},
   "source": [
    "# 23. Sorted array to binary search tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "id": "3ebd06a8",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sortedArrayToBST(nums):\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",
    "        \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": "441ba600",
   "metadata": {},
   "source": [
    "# 24. Balanced Binary tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "id": "0ee49937",
   "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": "f9b5cfbe",
   "metadata": {},
   "source": [
    "# 25. Minimum depth of binary tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "id": "01c92419",
   "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": "2fa69118",
   "metadata": {},
   "source": [
    "# 25. Path Sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "id": "19a07e52",
   "metadata": {},
   "outputs": [],
   "source": [
    "def hasPathSum(root, targetSum):\n",
    "    if root is None:\n",
    "        return False\n",
    "    \n",
    "    queue = []\n",
    "    \n",
    "    queue.append((root, targetSum - root.val))\n",
    "    \n",
    "    while len(queue) > 0:\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": "30b8e190",
   "metadata": {},
   "source": [
    "# 26. Best time to buy and sell stock"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "id": "3c6380bf",
   "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",
    "    \n",
    "    return max_profit"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fae7116e",
   "metadata": {},
   "source": [
    "# 27. Valid palindrome"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "id": "ad24e266",
   "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": 70,
   "id": "eb8dc5bd",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 70,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"A man, a plan, a canal: Panama\"\n",
    "\n",
    "isPalindrome(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e8d6ecb2",
   "metadata": {},
   "source": [
    "# 28. Almost Palindrome"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "f32c7058",
   "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",
    "        \n",
    "        left += 1\n",
    "        right -= 1\n",
    "    \n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "8a38502d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"abad\"\n",
    "almostPalindrome(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "13240c24",
   "metadata": {},
   "source": [
    "# 29. Typed out strings"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "id": "f4068cc4",
   "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": 79,
   "id": "fca6e6ec",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 79,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = 'ad##'\n",
    "t = 'bc##'\n",
    "\n",
    "backspaceCompare(s,t)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "26a85568",
   "metadata": {},
   "source": [
    "# 30. Longest Substring without repeating characters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "id": "e88b956b",
   "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",
    "        prevSeenChar = -1\n",
    "        \n",
    "        if currentChar in seenChars.keys():\n",
    "            prevSeenChar = seenChars[currentChar]\n",
    "        \n",
    "        if prevSeenChar >= left:\n",
    "            left = prevSeenChar + 1\n",
    "        \n",
    "        seenChars[currentChar] = right\n",
    "        \n",
    "        longest = max(longest, right - left + 1)\n",
    "    return longest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "9628f31f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"abcdeabcbb\"\n",
    "lengthOfLongestSubstring(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c35e8041",
   "metadata": {},
   "source": [
    "# 31. Reverse a linked list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "id": "4b2ad8c8",
   "metadata": {},
   "outputs": [],
   "source": [
    "def reverseList(head):\n",
    "    \n",
    "    curr = head\n",
    "    prev = None\n",
    "    \n",
    "    while curr is not None:\n",
    "        nextTmp = curr.next\n",
    "        curr.next = prev\n",
    "        prev = curr\n",
    "        curr = nextTmp\n",
    "    \n",
    "    return head"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "920a2ef0",
   "metadata": {},
   "source": [
    "# 32. Min remove to make valid parenthesis"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "id": "e0a3cf23",
   "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": 91,
   "id": "4b5cb70e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "''"
      ]
     },
     "execution_count": 91,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "minRemoveToMakeValid('))((')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "id": "6d650e39",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'lee(t(c)o)de'"
      ]
     },
     "execution_count": 92,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "minRemoveToMakeValid('lee(t(c)o)de)')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a8861182",
   "metadata": {},
   "source": [
    "# 33. Find Kth Largest element"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "id": "a5c2ef7f",
   "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",
    "    \n",
    "    partitionIndex = partition(nums, left, right)\n",
    "    \n",
    "    if partitionIndex == targetIndex:\n",
    "        return nums[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",
    "\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[partitionIndex], nums[j] = nums[j], nums[partitionIndex]\n",
    "            partitionIndex += 1\n",
    "    nums[partitionIndex], nums[right] = nums[right], nums[partitionIndex]\n",
    "    return partitionIndex"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 128,
   "id": "705d9f8b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 128,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [3,2,1,5,6,4]\n",
    "k = 4\n",
    "findKthLargest(nums, k)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ac604aff",
   "metadata": {},
   "source": [
    "# 34. Find kth smallest element"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 143,
   "id": "819993df",
   "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": 145,
   "id": "78fe45f1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 145,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [3,2,1,5,6,4]\n",
    "k = 2\n",
    "findKthSmallest(nums, k)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7c09d2a5",
   "metadata": {},
   "source": [
    "# 35. Start and end of a target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 150,
   "id": "9c5c674d",
   "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",
    "    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": 151,
   "id": "4a8eafe8",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2]"
      ]
     },
     "execution_count": 151,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [5,7,7,8,8,10]\n",
    "\n",
    "start_and_end(nums, 7)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e88ee25f",
   "metadata": {},
   "source": [
    "# 36. Level order of binary tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 149,
   "id": "d72c08fc",
   "metadata": {},
   "outputs": [],
   "source": [
    "def levelOrder(root):\n",
    "    if root is None:\n",
    "        return None\n",
    "    \n",
    "    result = []\n",
    "    queue = [root]\n",
    "    \n",
    "    while len(queue) > 0:\n",
    "        queue_length = len(queue)\n",
    "        currentLevelValue = []\n",
    "        counter = 0\n",
    "        \n",
    "        while counter < queue_length:\n",
    "            currNode = queue.pop(0)\n",
    "            currentLevelValue.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",
    "                \n",
    "            counter += 1\n",
    "        result.append(currentLevelValue)\n",
    "    return result"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c483afc7",
   "metadata": {},
   "source": [
    "# 37. Number of Islands"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 152,
   "id": "d6bff033",
   "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 len(queue) > 0:\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",
    "                            queue.append([nextRow, nextCol])\n",
    "                            grid[nextRow][nextCol] = '0'\n",
    "    return islandCount"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 156,
   "id": "e94c5ee3",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 156,
     "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": "8f4f124f",
   "metadata": {},
   "source": [
    "# 38. Rotting oranges"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 161,
   "id": "d1b629ef",
   "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 len(queue) > 0:\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",
    "                    \n",
    "    return minutesElapsed if freshOranges == 0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 162,
   "id": "6da4e561",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 162,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grid = [[2,1,1],[1,1,0],[0,1,1]]\n",
    "\n",
    "orangesRotting(grid)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "57becc4f",
   "metadata": {},
   "source": [
    "# 39. Walls and gates"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "30068b05",
   "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",
    "        dfs(matrix, nextRow, nextCol, currentStep + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "6343ce5d",
   "metadata": {},
   "outputs": [],
   "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)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "f9e8ec32",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[3, -1, 0, 1], [2, 2, 1, -1], [1, -1, 2, -1], [0, -1, 3, 4]]"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rooms"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3dcd3e7d",
   "metadata": {},
   "source": [
    "# 40. Single Number"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 170,
   "id": "16dbcf81",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "\n",
    "def singleNumber(nums):\n",
    "    count_nums = Counter(nums)\n",
    "    \n",
    "    for i in range(len(nums)):\n",
    "        if count_nums[nums[i]] == 1:\n",
    "            return nums[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 171,
   "id": "7697458d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 171,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [2,2,1]\n",
    "\n",
    "singleNumber(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c92e342f",
   "metadata": {},
   "source": [
    "# 41. Linked List cycle"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 172,
   "id": "301749eb",
   "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",
    "        tortoise = tortoise.next\n",
    "        hare = hare.next.next\n",
    "        if tortoise == hare:\n",
    "            return True\n",
    "    return False"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4dc584f6",
   "metadata": {},
   "source": [
    "# 42. Binary tree post order traversal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 173,
   "id": "3d26e081",
   "metadata": {},
   "outputs": [],
   "source": [
    "def postOrder(root):\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, result)\n",
    "    return result"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "74acf277",
   "metadata": {},
   "source": [
    "# 43. Right side view of the tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 175,
   "id": "ac69e453",
   "metadata": {},
   "outputs": [],
   "source": [
    "def right_view_bfs(root):\n",
    "    result = []\n",
    "    level = 0\n",
    "    return traversePreOrder(root, result, level)\n",
    "\n",
    "def traversePreOrder(node, result, level):\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, result, level + 1)\n",
    "    \n",
    "    if node.left is not None:\n",
    "        traversePreOrder(node.left, result, level + 1)\n",
    "    \n",
    "    return result"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1452135f",
   "metadata": {},
   "source": [
    "# 44. Number of nodes in a complete tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 176,
   "id": "56e809a1",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Naive\n",
    "\n",
    "def countNodes(root):\n",
    "    if root is None:\n",
    "        return 0\n",
    "    else:\n",
    "        return countNodes(root.left) + countNodes(root.right) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 177,
   "id": "02065a3b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def countNodes(root):\n",
    "    if root is None:\n",
    "        return 0\n",
    "    \n",
    "    # O(h)\n",
    "    height = getTreeHeight(root)\n",
    "    \n",
    "    # zero indexed\n",
    "    if height == 0:\n",
    "        return 1\n",
    "    \n",
    "    # maximum index of the last level and also the number of nodes uptil the last level\n",
    "    upper_count = 2**height - 1\n",
    "    \n",
    "    left = 0\n",
    "    right = upper_count\n",
    "    \n",
    "    # O(h)\n",
    "    while left <  right:\n",
    "        index_to_find = math.ceil((left + right)/2)\n",
    "        # O(h)\n",
    "        if node_exists(index_to_find, height, root):\n",
    "            left = index_to_find\n",
    "        else:\n",
    "            right = index_to_find - 1\n",
    "    \n",
    "    # we are adding +1 as it is zero indexed.\n",
    "    return upper_count + left + 1\n",
    "\n",
    "def getTreeHeight(node):\n",
    "    height = 0\n",
    "    \n",
    "    while node.left is not None:\n",
    "        height += 1\n",
    "        node = node.left\n",
    "        \n",
    "    return height\n",
    "\n",
    "\n",
    "def node_exists(index_to_find, height, node):\n",
    "    left = 0\n",
    "    right = 2**height - 1\n",
    "    count = 0\n",
    "    \n",
    "    while count < height:\n",
    "        midpoint = math.ceil((left + right)/2)\n",
    "        \n",
    "        if index_to_find >= midpoint:\n",
    "            node = node.right\n",
    "            left = midpoint\n",
    "        else:\n",
    "            node = node.left\n",
    "            right = midpoint - 1\n",
    "        \n",
    "        count += 1\n",
    "        \n",
    "    return node is not None"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ffa3119c",
   "metadata": {},
   "source": [
    "# 45. Validate binary search tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 179,
   "id": "b41e1e40",
   "metadata": {},
   "outputs": [],
   "source": [
    "def isValidBST(root):\n",
    "    \n",
    "    def validate(node, low=-math.inf, high=math.inf):\n",
    "        if not node:\n",
    "            return True\n",
    "        if node.val <= low or node.val >= high:\n",
    "            return False\n",
    "        return (validate(node.right, node.val, high) and validate(node.left, low, node.val))\n",
    "    \n",
    "    return validate(root)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "51455e26",
   "metadata": {},
   "source": [
    "# 46. Read 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 180,
   "id": "90354ee7",
   "metadata": {},
   "outputs": [],
   "source": [
    "def read4(buf, n):\n",
    "    copied_chars = 0\n",
    "    read_chars = 4\n",
    "    buf4 = [' '] * 4\n",
    "    \n",
    "    while copied_chars < n and read_chars == 4:\n",
    "        read_chars = read4(buf4)\n",
    "        \n",
    "        for i in range(read_chars):\n",
    "            if copied_chars == n:\n",
    "                return copied_chars\n",
    "            buf[copied_chars] = buf4[i]\n",
    "            copied_chars += 1\n",
    "    return copied_chars"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3d25824c",
   "metadata": {},
   "source": [
    "# 47. Intersection of two linkedlist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 181,
   "id": "8b501038",
   "metadata": {},
   "outputs": [],
   "source": [
    "def getIntersectionNode(headA, headB):\n",
    "    \n",
    "    nodes_in_B = set()\n",
    "    \n",
    "    while headB is not None:\n",
    "        nodes_in_B.add(headB)\n",
    "        headB = headB.next\n",
    "    \n",
    "    while headA is not None:\n",
    "        if headA in nodes_in_B:\n",
    "            return headA\n",
    "        headA = headA.next\n",
    "    \n",
    "    return None"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6622f017",
   "metadata": {},
   "source": [
    "# 48. Missing Ranges"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "475980db",
   "metadata": {},
   "outputs": [],
   "source": [
    "def findMissingRanges(nums, lower, upper):\n",
    "    \n",
    "    nums = [lower - 1] + nums + [upper + 1]\n",
    "    \n",
    "    ans = []\n",
    "    \n",
    "    for i in range(1, len(nums)):\n",
    "        curr, prev = nums[i], nums[i-1]\n",
    "        if curr - prev > 1:\n",
    "            if curr == prev + 2:\n",
    "                ans.append(str(prev + 1))\n",
    "            else:\n",
    "                ans.append(str(prev + 1) + '->' + str(curr - 1))\n",
    "    return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "2eb98269",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['2', '4->49', '51->74', '76->99']"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [0,1,3,50,75]\n",
    "lower = 0\n",
    "upper = 99\n",
    "\n",
    "findMissingRanges(nums, lower, upper)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "15ee22fd",
   "metadata": {},
   "source": [
    "# 49. Summary Ranges"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 220,
   "id": "9060fdf2",
   "metadata": {},
   "outputs": [],
   "source": [
    "def summaryRanges(nums):\n",
    "    pointer = 0\n",
    "    ans = []\n",
    "    \n",
    "    for i, num in enumerate(nums):\n",
    "        if i == len(nums) - 1 or nums[i + 1] - nums[i] > 1:\n",
    "            if nums[pointer] != num:\n",
    "                ans.append(str(nums[pointer]) + '->' + str(num))\n",
    "            else:\n",
    "                ans.append(str(num))\n",
    "            pointer = i + 1\n",
    "    return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "f3604d06",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['0->2', '4->5', '7']"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [0,1,2,4,5,7]\n",
    "\n",
    "summaryRanges(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a0b96388",
   "metadata": {},
   "source": [
    "# 50. Excel sheet column title"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 224,
   "id": "eeda895e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def convertToTitle(columnNumber):\n",
    "    \n",
    "    capitals = [chr(x) for x in range(ord('A'), ord('Z') + 1)]\n",
    "    \n",
    "    result = []\n",
    "    \n",
    "    while columnNumber > 0:\n",
    "        result.append(capitals[(columnNumber - 1) % 26] )\n",
    "        columnNumber = (columnNumber - 1) // 26\n",
    "    result.reverse()\n",
    "    \n",
    "    return \"\".join(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 225,
   "id": "c3bc274d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'AA'"
      ]
     },
     "execution_count": 225,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "convertToTitle(27)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "da916e78",
   "metadata": {},
   "source": [
    "# 51. Excel sheet column number"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 226,
   "id": "52fb84e3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def titleToNumber(columnTitle):\n",
    "    alpha_map = {chr(i + 65): i + 1 for i in range(26)}\n",
    "    \n",
    "    result = 0\n",
    "    \n",
    "    n = len(columnTitle)\n",
    "    \n",
    "    for i in range(n):\n",
    "        current_char = columnTitle[n-1-i]\n",
    "        result += (alpha_map[current_char] * (26 ** i))\n",
    "    \n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 227,
   "id": "9296b78e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "28"
      ]
     },
     "execution_count": 227,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "columnTitle = \"AB\"\n",
    "\n",
    "titleToNumber(columnTitle)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "067563ba",
   "metadata": {},
   "source": [
    "# 52. Majority element"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 228,
   "id": "28a0c655",
   "metadata": {},
   "outputs": [],
   "source": [
    "def majorityElement(nums):\n",
    "    nums_map = Counter(nums)\n",
    "    \n",
    "    for i in nums:\n",
    "        if nums_map[i] > len(nums) / 2:\n",
    "            return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 229,
   "id": "20f46b85",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 229,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [2,2,1,1,1,2,2]\n",
    "\n",
    "majorityElement(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "88b6fe39",
   "metadata": {},
   "source": [
    "# 53. Happy number"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 231,
   "id": "05b200cd",
   "metadata": {},
   "outputs": [],
   "source": [
    "def isHappy(n):\n",
    "    \n",
    "    def getNext(number):\n",
    "        total_sum = 0\n",
    "        \n",
    "        while number > 0:\n",
    "            number, digit = divmod(number, 10)\n",
    "            total_sum += digit ** 2\n",
    "        \n",
    "        return total_sum\n",
    "    \n",
    "    slow = n\n",
    "    fast = getNext(n)\n",
    "    \n",
    "    while fast != slow and fast != 1:\n",
    "        slow = getNext(slow)\n",
    "        fast = getNext(getNext(fast))\n",
    "        \n",
    "    return fast == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 232,
   "id": "7378b16d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 232,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n = 19\n",
    "\n",
    "isHappy(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 233,
   "id": "82358927",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 233,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n = 20\n",
    "\n",
    "isHappy(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7b54b8fe",
   "metadata": {},
   "source": [
    "# 54. Remove linkedlist element"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 234,
   "id": "24f6c8fb",
   "metadata": {},
   "outputs": [],
   "source": [
    "def removeElements(head, val):\n",
    "    sentinel = ListNode(0)\n",
    "    sentinel.next = head\n",
    "    \n",
    "    prev = sentinel\n",
    "    curr = head\n",
    "    \n",
    "    while curr is not None:\n",
    "        currVal = curr.val\n",
    "        if currVal == val:\n",
    "            prev.next = curr.next\n",
    "        else:\n",
    "            prev = curr\n",
    "        curr = curr.next\n",
    "    return sentinel.next"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4b5c1321",
   "metadata": {},
   "source": [
    "# 55. Add two linked lists"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "605b0ae3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def addTwoNumbers(l1, l2):\n",
    "    dummyHead = ListNode(0)\n",
    "    curr = dummyHead\n",
    "    carry = 0\n",
    "    \n",
    "    while l1 is not None or l2 is not None or carry != 0:\n",
    "        l1val = l1.val if l1 else 0\n",
    "        l2val = l2.val if l2 else 0\n",
    "        columnSum = (l1val + l2val + carry) % 10\n",
    "        carry = (l1val + l2val + carry) // 10\n",
    "        newNode = ListNode(columnSum)\n",
    "        curr.next = newNode\n",
    "        curr = newNode\n",
    "        l1 = l1.next if l1 else None\n",
    "        l2 = l2.next if l2 else None\n",
    "    return dummyHead.next"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f3f2683f",
   "metadata": {},
   "source": [
    "# 55. Isomorphic Strings"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 235,
   "id": "954464b4",
   "metadata": {},
   "outputs": [],
   "source": [
    "def isIsomorphic(s, t):\n",
    "    return transformString(s) == transformString(t)\n",
    "\n",
    "def transformString(s):\n",
    "    index_mapping = {}\n",
    "    result = []\n",
    "    \n",
    "    for i in range(len(s)):\n",
    "        if s[i] not in index_mapping:\n",
    "            index_mapping[s[i]] = i\n",
    "        result.append(str(index_mapping[s[i]]))\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 238,
   "id": "aaad83d2",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 238,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"egg\" \n",
    "t = \"add\"\n",
    "\n",
    "isIsomorphic(s, t)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0325c57c",
   "metadata": {},
   "source": [
    "# 56. Contains duplicate 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 239,
   "id": "380c9772",
   "metadata": {},
   "outputs": [],
   "source": [
    "def containsNearbyDuplicate(nums, k):\n",
    "    index_mapping = {}\n",
    "    \n",
    "    for i, c in enumerate(nums):\n",
    "        if c in index_mapping and c - index_mapping[c] <= k:\n",
    "            return True\n",
    "        index_mapping[c] = i\n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 240,
   "id": "809fec10",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 240,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [1,2,3,1]\n",
    "k = 3\n",
    "\n",
    "containsNearbyDuplicate(nums, k)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f6f84e13",
   "metadata": {},
   "source": [
    "# 57. Invert binary tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 241,
   "id": "cef6643f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def invertTree(root):\n",
    "    if root is None:\n",
    "        return None\n",
    "    \n",
    "    left = invertTree(root.left)\n",
    "    right = invertTree(root.right)\n",
    "    \n",
    "    root.left = right\n",
    "    root.right = left\n",
    "    \n",
    "    return root"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9f9a218c",
   "metadata": {},
   "source": [
    "# 58. Summary ranges"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 242,
   "id": "d263c69f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def summaryRanges(nums):\n",
    "    ans = []\n",
    "    pointer = 0\n",
    "    \n",
    "    for i, c in enumerate(nums):\n",
    "        if i == len(nums) - 1 or nums[i + 1] - nums[i] > 1:\n",
    "            if nums[pointer] != c:\n",
    "                ans.append(str(nums[pointer]) + '->' + str(c))\n",
    "            else:\n",
    "                ans.append(str(c))\n",
    "            pointer = i + 1\n",
    "    return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 243,
   "id": "0bc8d048",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['0->2', '4->5', '7']"
      ]
     },
     "execution_count": 243,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [0,1,2,4,5,7]\n",
    "\n",
    "summaryRanges(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "95373931",
   "metadata": {},
   "source": [
    "# 59. Palindrome Linked List"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 244,
   "id": "92b95d72",
   "metadata": {},
   "outputs": [],
   "source": [
    "def isPalindrome(head):\n",
    "    if head is None:\n",
    "        return False\n",
    "    \n",
    "    vals = []\n",
    "    \n",
    "    curr = head\n",
    "    \n",
    "    while curr is not None:\n",
    "        vals.append(curr.val)\n",
    "        curr = curr.next\n",
    "    \n",
    "    return vals == vals[::-1]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5237556a",
   "metadata": {},
   "source": [
    "# 60.Shortest word distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 267,
   "id": "b4ab119a",
   "metadata": {},
   "outputs": [],
   "source": [
    "def shortestDistance(wordsDict, word1, word2):\n",
    "    shortest = len(wordsDict)\n",
    "    index = None\n",
    "    found = None\n",
    "    \n",
    "    for i, word in enumerate(wordsDict):\n",
    "        if word == word1 or word == word2:\n",
    "            if found is not None:\n",
    "                if word != found:\n",
    "                    shortest = min(shortest, i - index)\n",
    "            found = word\n",
    "            index = i\n",
    "    return shortest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "adbd8631",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "wordsDict = [\"practice\", \"makes\", \"perfect\", \"coding\", \"makes\"]\n",
    "word1 = \"coding\"\n",
    "word2 = \"makes\"\n",
    "\n",
    "shortestDistance(wordsDict, word1, word2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8ce185db",
   "metadata": {},
   "source": [
    "# 61. Custom sort string"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "4ce95ca4",
   "metadata": {},
   "outputs": [],
   "source": [
    "def customSortString(order, s):\n",
    "    count_s = Counter(s)\n",
    "    result = []\n",
    "    \n",
    "    for c in order:\n",
    "        result.append(c * count_s[c])\n",
    "        count_s[c] = 0\n",
    "    \n",
    "    for c in count_s:\n",
    "        result.append(c * count_s[c])\n",
    "    \n",
    "    return \"\".join(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "8285ba46",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'cbaad'"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "order = \"cbafg\"\n",
    "s = \"aabcd\"\n",
    "\n",
    "customSortString(order, s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d2e8fa6f",
   "metadata": {},
   "source": [
    "# 62. Next greater element"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "7ae7995d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def nextGreaterElement(nums1, nums2):\n",
    "    next_num = {}\n",
    "    stack = []\n",
    "    \n",
    "    for num2 in nums2:\n",
    "        while len(stack) > 0 and num2 > stack[-1]:\n",
    "            num1 = stack.pop()\n",
    "            next_num[num1] = num2\n",
    "        stack.append(num2)\n",
    "    \n",
    "    while stack:\n",
    "        num1 = stack.pop()\n",
    "        next_num[num1] = -1\n",
    "    \n",
    "    return [next_num[num1] for num1 in nums1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 270,
   "id": "48237962",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[-1, 3, -1]"
      ]
     },
     "execution_count": 270,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums1 = [4,1,2]\n",
    "nums2 = [1,3,4,2]\n",
    "\n",
    "nextGreaterElement(nums1, nums2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "32c16576",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[7, 7, 7, 7, 7]"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums1 = [1,3,5,2,4]\n",
    "nums2 = [6,5,4,3,2,1,7]\n",
    "\n",
    "nextGreaterElement(nums1, nums2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "00585b2f",
   "metadata": {},
   "source": [
    "# 63. Longest Continuous Increasing Subsequence"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 279,
   "id": "9313a329",
   "metadata": {},
   "outputs": [],
   "source": [
    "def findLengthOfLCIS(nums):\n",
    "    left = 0\n",
    "    longest = 0\n",
    "    \n",
    "    for right in range(1, len(nums)):\n",
    "        if nums[right - 1] >= nums[right]:\n",
    "            left = right\n",
    "        longest = max(longest, right - left + 1)\n",
    "    return longest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 280,
   "id": "ffa0bf50",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 280,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [1,3,5,4,7]\n",
    "\n",
    "findLengthOfLCIS(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e183b214",
   "metadata": {},
   "source": [
    "# 64. Maximum Size Subarray Sum Equals k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 281,
   "id": "78aa5e55",
   "metadata": {},
   "outputs": [],
   "source": [
    "def maxSubArrayLen(nums, k):\n",
    "    prefix_sum = 0\n",
    "    dict_cumsum = defaultdict(int)\n",
    "    longest = 0\n",
    "    \n",
    "    for i in range(len(nums)):\n",
    "        prefix_sum += nums[i]\n",
    "        \n",
    "        if prefix_sum == k:\n",
    "            longest = i + 1\n",
    "        \n",
    "        if prefix_sum - k in dict_cumsum:\n",
    "            longest = max(longest, i - dict_cumsum[prefix_sum - k])\n",
    "        \n",
    "        if prefix_sum not in dict_cumsum:\n",
    "            dict_cumsum[prefix_sum] = i\n",
    "    return longest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "9752e3ea",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [1,-1,5,-2,3]\n",
    "k = 3\n",
    "\n",
    "maxSubArrayLen(nums, k)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "75c83532",
   "metadata": {},
   "source": [
    "# 65. Subarray sum equals k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 262,
   "id": "5bb9303e",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "def subarraySum(nums, k):\n",
    "    count = 0\n",
    "    dict_cumsum = defaultdict(int)\n",
    "    prefix_sum = 0\n",
    "    n = len(nums)\n",
    "    \n",
    "    for i in range(len(nums)):\n",
    "        prefix_sum += nums[i]\n",
    "        \n",
    "        if prefix_sum == k:\n",
    "            count += 1\n",
    "        \n",
    "        if prefix_sum - k in dict_cumsum:\n",
    "            count += dict_cumsum[prefix_sum - k]\n",
    "        \n",
    "        dict_cumsum[prefix_sum] += 1\n",
    "    return count\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 263,
   "id": "0542b929",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 263,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [1,1,1]\n",
    "k = 2\n",
    "\n",
    "subarraySum(nums, k)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6f1da8fc",
   "metadata": {},
   "source": [
    "# 66. Longest Substring without repeating characters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 285,
   "id": "76661014",
   "metadata": {},
   "outputs": [],
   "source": [
    "def lengthOfLongestSubstring(s):\n",
    "    seenChars = {}\n",
    "    left = 0\n",
    "    longest = 0\n",
    "    \n",
    "    for right in range(len(s)):\n",
    "        currentChar = s[right]\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",
    "        \n",
    "        longest = max(longest, right - left + 1)\n",
    "    return longest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 286,
   "id": "7174c6a4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 286,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"abcdeabcbb\"\n",
    "lengthOfLongestSubstring(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6559216a",
   "metadata": {},
   "source": [
    "# 67. Three Sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 289,
   "id": "a2dad52a",
   "metadata": {},
   "outputs": [],
   "source": [
    "def threeSum(nums):\n",
    "    ans = []\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, ans)\n",
    "    \n",
    "    return ans\n",
    "\n",
    "def twoSum(nums, i, result):\n",
    "    left = i + 1\n",
    "    right = len(nums) - 1\n",
    "    \n",
    "    while left < right:\n",
    "        sums = nums[i] + nums[left] + nums[right]\n",
    "        \n",
    "        if sums > 0:\n",
    "            right -= 1\n",
    "        elif sums < 0:\n",
    "            left += 1\n",
    "        else:\n",
    "            result.append([nums[i], nums[left], nums[right]])\n",
    "            left += 1\n",
    "            right -= 1\n",
    "            \n",
    "            while left < right and nums[left] == nums[left - 1]:\n",
    "                left += 1\n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 290,
   "id": "08cffef1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[-1, -1, 2], [-1, 0, 1]]"
      ]
     },
     "execution_count": 290,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [-1,0,1,2,-1,-4]\n",
    "\n",
    "threeSum(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "21d77fb2",
   "metadata": {},
   "source": [
    "# 68. Linked List Sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 291,
   "id": "d4e7441b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def addTwoNumbers(l1, l2):\n",
    "    dummyHead = ListNode(0)\n",
    "    curr = dummyHead\n",
    "    carry = 0\n",
    "    \n",
    "    while l1 is not None or l2 is not None or carry != 0:\n",
    "        l1val = l1.val if l1 else 0\n",
    "        l2val = l2.val if l2 else 0\n",
    "        columnSum = (l1val + l2val + carry) % 10\n",
    "        carry = (l1val + l2val + carry) // 10\n",
    "        newNode = ListNode(columnSum)\n",
    "        curr.next = newNode\n",
    "        curr = newNode\n",
    "        l1 = l1.next if l1 else None\n",
    "        l2 = l2.next if l2 else None\n",
    "    return dummyHead.next"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1672b2dd",
   "metadata": {},
   "source": [
    "# 69. Left most column with at least a one"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "34b3220b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def leftMostColumnWithOne(binaryMatrix):\n",
    "    rows, cols = binaryMatrix.dimensions()\n",
    "    smallest_index = cols\n",
    "    \n",
    "    for row in range(rows):\n",
    "        low = 0\n",
    "        high = cols - 1\n",
    "        \n",
    "        while low < high:\n",
    "            mid = math.floor((low + high)/2)\n",
    "            \n",
    "            if binaryMatrix.get(row, mid) == 0:\n",
    "                low = mid + 1\n",
    "            else:\n",
    "                high = mid\n",
    "            \n",
    "        if binaryMatrix.get(row, low) == 1:\n",
    "            smallest_index = min(smallest_index, low)\n",
    "    return smallest_index if smallest_index != cols else -1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dbd21682",
   "metadata": {},
   "source": [
    "# 70. Reverse vowels"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 294,
   "id": "b1ec264c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def reverseVowels(s: str) -> str:\n",
    "    vowels = ['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']\n",
    "    \n",
    "    s = [i for i in s]\n",
    "    \n",
    "    left = 0\n",
    "    right = len(s) - 1\n",
    "    \n",
    "    while left < right:\n",
    "        left_val, right_val = s[left], s[right]\n",
    "        \n",
    "        if left_val in vowels and right_val in vowels:\n",
    "            s[left], s[right] = s[right], s[left]\n",
    "            left += 1\n",
    "            right -= 1\n",
    "        elif left_val in vowels and right_val not in vowels:\n",
    "            right -= 1\n",
    "        elif left_val not in vowels and right_val in vowels:\n",
    "            left += 1\n",
    "        else:\n",
    "            left += 1\n",
    "            right -= 1\n",
    "    \n",
    "    return \"\".join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 295,
   "id": "75119463",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'leotcede'"
      ]
     },
     "execution_count": 295,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"leetcode\"\n",
    "reverseVowels(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "672eafaf",
   "metadata": {},
   "source": [
    "# 71. Find Largest Value in Each Tree Row"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 296,
   "id": "09784dba",
   "metadata": {},
   "outputs": [],
   "source": [
    "def largestValues(root):\n",
    "    result = []\n",
    "    if root is None:\n",
    "        return result\n",
    "    \n",
    "    queue = [root]\n",
    "    \n",
    "    while len(queue) > 0:\n",
    "        result.append(max(x.val) for x in queue)\n",
    "        \n",
    "        for _ in range(len(queue)):\n",
    "            currNode = queue.pop(0)\n",
    "            if currNode.left is not None:\n",
    "                queue.append(currNode.left)\n",
    "            if currNode.right is not None:\n",
    "                queue.append(currNode.right)\n",
    "    return result"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9ff7b950",
   "metadata": {},
   "source": [
    "# 72. Merge two linked lists"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 297,
   "id": "6c3d7f9d",
   "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": "ee1571bb",
   "metadata": {},
   "source": [
    "# 73. Minimum time visiting all points"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 298,
   "id": "b55d8407",
   "metadata": {},
   "outputs": [],
   "source": [
    "def minTimeToVisitAllPoints(points):\n",
    "    x1, y1 = points.pop()\n",
    "    result = 0\n",
    "    \n",
    "    while points:\n",
    "        x2, y2 = points.pop()\n",
    "        result += max(abs(y2 - y1), abs(x2 - x1))\n",
    "        x1, y1 = x2, y2\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 299,
   "id": "05b72395",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7"
      ]
     },
     "execution_count": 299,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "points = [[1,1],[3,4],[-1,0]]\n",
    "\n",
    "minTimeToVisitAllPoints(points)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d7bcb36b",
   "metadata": {},
   "source": [
    "# 74. Buddy strings"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 300,
   "id": "81f8f643",
   "metadata": {},
   "outputs": [],
   "source": [
    "def buddyStrings(s, goal):\n",
    "    \n",
    "    if len(s) != len(goal):\n",
    "        return False\n",
    "    \n",
    "    if s == goal:\n",
    "        seen = set()\n",
    "        for c in s:\n",
    "            if c in seen:\n",
    "                return True\n",
    "            seen.add(c)\n",
    "        return False\n",
    "    \n",
    "    pairs = []\n",
    "    \n",
    "    for a, b in zip(s, goal):\n",
    "        if a != b:\n",
    "            pairs.append((a,b))\n",
    "        \n",
    "        if len(pairs) >= 3:\n",
    "            return False\n",
    "        \n",
    "    return len(pairs) == 2 and pairs[0] == pairs[1][::-1]\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 301,
   "id": "8336764f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 301,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = 'abcd'\n",
    "goal = 'cbad'\n",
    "\n",
    "buddyStrings(s, goal)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "07932d42",
   "metadata": {},
   "source": [
    "# 75. Diagonal sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 303,
   "id": "4431aa2d",
   "metadata": {},
   "outputs": [],
   "source": [
    "import heapq\n",
    "\n",
    "def diagonalSort(mat):\n",
    "    \n",
    "    rows, cols = len(mat), len(mat[0])\n",
    "    \n",
    "    diagonals = defaultdict(list)\n",
    "    \n",
    "    for row in range(rows):\n",
    "        for col in range(cols):\n",
    "            diagonals[row - col].append(mat[row][col])\n",
    "    \n",
    "    for diagonal in diagonals.values():\n",
    "        heapq.heapify(diagonal)\n",
    "    \n",
    "    for row in range(rows):\n",
    "        for col in range(cols):\n",
    "            values = heapq.heappop(diagonals[row - col])\n",
    "            mat[row][col] = values\n",
    "    \n",
    "    return mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 304,
   "id": "7bf79b51",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 1, 1, 1], [1, 2, 2, 2], [1, 2, 3, 3]]"
      ]
     },
     "execution_count": 304,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]\n",
    "\n",
    "diagonalSort(mat)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d7e46d22",
   "metadata": {},
   "source": [
    "# 76. Binary tree vertical order traversal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 305,
   "id": "b6c7bac5",
   "metadata": {},
   "outputs": [],
   "source": [
    "def verticalOrder(root):\n",
    "    result = defaultdict(list)\n",
    "    queue = []\n",
    "    queue.append((root, 0))\n",
    "    \n",
    "    while len(queue) > 0:\n",
    "        currNode = queue.pop(0)\n",
    "        node = currNode[0]\n",
    "        column = currNode[1]\n",
    "        \n",
    "        if node is not None:\n",
    "            result[column].append(node.val)\n",
    "            queue.append((node.left, column - 1))\n",
    "            queue.append((node.right, column + 1))\n",
    "    \n",
    "    return [result[x] for x in sorted(result.keys())]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "758128e9",
   "metadata": {},
   "source": [
    "# 77. Lowest Common Ancestor"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 306,
   "id": "6a7157c4",
   "metadata": {},
   "outputs": [],
   "source": [
    "def lowestCommonAncestor(p,q):\n",
    "    p1, p2 = p, q\n",
    "    \n",
    "    while p1 != p2:\n",
    "        if p1.parent is not None:\n",
    "            p1 = p1.parent\n",
    "        else:\n",
    "            p1 = q\n",
    "    \n",
    "        if p2.parent is not None:\n",
    "            p2 = p2.parent\n",
    "        else:\n",
    "            p2 = p\n",
    "    return p1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b6205575",
   "metadata": {},
   "source": [
    "# 78. Minimum depth of binary tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 307,
   "id": "20eb2853",
   "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",
    "    return min_depth"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7a1ddead",
   "metadata": {},
   "source": [
    "# 79. Tribonacci"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 308,
   "id": "0008dba6",
   "metadata": {},
   "outputs": [],
   "source": [
    "def tribonacci(n):\n",
    "    if n < 3:\n",
    "        return 1 if n else 0\n",
    "    \n",
    "    first = 0\n",
    "    second = 1\n",
    "    third = 1\n",
    "    \n",
    "    for _ in range(n-2):\n",
    "        first, second, third = second, third, first + second + third\n",
    "    \n",
    "    return third"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "45cf200e",
   "metadata": {},
   "source": [
    "# 80. Array strings are equal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 309,
   "id": "1bb60b4e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def arrayStringsAreEqual(word1, word2) -> bool:\n",
    "    return \"\".join(word1) == \"\".join(word2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fdf7518a",
   "metadata": {},
   "source": [
    "# 81. Randomly output the index of a given number"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 310,
   "id": "feb74f7e",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "\n",
    "    def __init__(self, nums):\n",
    "        self.hashmap = defaultdict(list)\n",
    "        \n",
    "        for i, num in enumerate(nums):\n",
    "            self.hashmap[num].append(i)\n",
    "    \n",
    "    def pick(self, target: int) -> int:\n",
    "        return self.hashmap[target][random.randint(0, len(self.hashmap[target]) - 1)]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "190e26db",
   "metadata": {},
   "source": [
    "# 82. Strobogrammatic Numbers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 311,
   "id": "fbffa55d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def isStrobogrammatic(num):\n",
    "    strob_map = {\n",
    "            '1':'1',\n",
    "            '2': '',\n",
    "            '3': '',\n",
    "            '4': '',\n",
    "            '5': '',\n",
    "            '7': '',\n",
    "            '0':'0',\n",
    "            '6':'9',\n",
    "            '8':'8',\n",
    "            '9':'6'\n",
    "        }\n",
    "    \n",
    "    stringBuilder = []\n",
    "    \n",
    "    for c in num:\n",
    "        stringBuilder.append(strob_map[c])\n",
    "    \n",
    "    rotated_string = \"\".join(stringBuilder)[::-1]\n",
    "    return rotated_string == num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 312,
   "id": "a6fa46db",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 312,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "num = \"69\"\n",
    "isStrobogrammatic(num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 315,
   "id": "e4b3b042",
   "metadata": {},
   "outputs": [],
   "source": [
    "def facebook_stickers(s):\n",
    "    sticker = 'facebook'\n",
    "    \n",
    "    res = 1\n",
    "    \n",
    "    s = s.lower()\n",
    "    \n",
    "    char_count = Counter(sticker)\n",
    "    \n",
    "    s_count = Counter(s)\n",
    "    \n",
    "    for c in s:\n",
    "        if c.isalpha():\n",
    "            if c not in char_count:\n",
    "                return 0\n",
    "            \n",
    "            if s_count[c] > res * char_count[c]:\n",
    "                res += 1\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 316,
   "id": "91915d1e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 316,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "facebook_stickers('book FACE cook')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1552c02e",
   "metadata": {},
   "source": [
    "# 83. Phone Digits\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 320,
   "id": "32331d3b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def letterCombinations(digits):\n",
    "    letter_map = {2: ['a', 'b', 'c'],\n",
    "                  3: ['d', 'e', 'f'],\n",
    "                  4: ['g', 'h', 'i'],\n",
    "                  5: ['j', 'k', 'l'],\n",
    "                  6: ['m', 'n', 'o'],\n",
    "                  7: ['p', 'q', 'r', 's'],\n",
    "                  8: ['t', 'u', 'v'],\n",
    "                  9: ['w', 'x', 'y', 'z']}\n",
    "    if digits == \"\":\n",
    "        return []\n",
    "    \n",
    "    queue = letter_map[int(digits[0])]\n",
    "    \n",
    "    for i in range(1, len(digits)):\n",
    "        s = len(queue)\n",
    "        while s:\n",
    "            currLetter = queue.pop(0)\n",
    "            \n",
    "            for j in letter_map[int(digits[i])]:\n",
    "                queue.append(currLetter + j)\n",
    "            s -= 1\n",
    "    return queue\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 321,
   "id": "02c59f38",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']"
      ]
     },
     "execution_count": 321,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "digits = \"23\"\n",
    "\n",
    "letterCombinations(digits)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d00cfa9f",
   "metadata": {},
   "source": [
    "# 84. Nestedlist sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "9b193240",
   "metadata": {},
   "outputs": [],
   "source": [
    "def depthSumInverse(nestedList):\n",
    "    total_sum = 0\n",
    "    level_sum = 0\n",
    "    \n",
    "    while len(nestedList) > 0:\n",
    "        next_level_list = []\n",
    "        \n",
    "        for x in nestedList:\n",
    "            if x.isInteger():\n",
    "                level_sum += x.getInteger()\n",
    "            else:\n",
    "                for y in x.getList():\n",
    "                    next_level_list.append(y)\n",
    "        total_sum += level_sum\n",
    "        nestedList = next_level_list\n",
    "    return total_sum"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "304ef07a",
   "metadata": {},
   "source": [
    "# 85. Restore string"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "b52b7ac7",
   "metadata": {},
   "outputs": [],
   "source": [
    "def restoreString(s, indices):\n",
    "    result = [0] * len(s)\n",
    "\n",
    "    for i, c in zip(indices, s):\n",
    "        result[i] = c\n",
    "\n",
    "    return \"\".join(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "8ce01ced",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'leetcode'"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"codeleet\"\n",
    "indices = [4,5,6,7,0,2,1,3]\n",
    "\n",
    "restoreString(s, indices)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6bc2a171",
   "metadata": {},
   "source": [
    "# 86. Simplify paths"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "e358dffe",
   "metadata": {},
   "outputs": [],
   "source": [
    "def simplifyPath(path: str) -> str:\n",
    "    stack = []\n",
    "\n",
    "    paths = path.split('/')\n",
    "\n",
    "    for path in paths:\n",
    "        if path == '..':\n",
    "            if len(stack) > 0:\n",
    "                stack.pop()\n",
    "        elif path == '.' or len(path) == 0:\n",
    "            continue\n",
    "        else:\n",
    "            stack.append(path)\n",
    "\n",
    "    return '/' + '/'.join(stack)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cabd0a2a",
   "metadata": {},
   "source": [
    "# 87. Value of BST closest to target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "1080279b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def closestValue(root, target):\n",
    "    if root is None:\n",
    "        return None\n",
    "\n",
    "    if root.left is None and root.right is None:\n",
    "        return root.val\n",
    "\n",
    "    queue = []\n",
    "\n",
    "    queue.append(root)\n",
    "\n",
    "    closest = float('inf')\n",
    "\n",
    "    targetNode = 0\n",
    "\n",
    "    while len(queue) > 0:\n",
    "        currNode = queue.pop(0)\n",
    "        currVal = currNode.val\n",
    "\n",
    "        result = abs(target - currVal)\n",
    "\n",
    "        if result < closest:\n",
    "            targetNode = currVal\n",
    "\n",
    "        closest = min(closest, result)\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",
    "\n",
    "    return targetNode"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "70b4cb95",
   "metadata": {},
   "source": [
    "# 88. Island perimeter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "2f0933a8",
   "metadata": {},
   "outputs": [],
   "source": [
    "def islandPerimeter(grid) -> int:\n",
    "    rows, cols = len(grid), len(grid[0])\n",
    "    result = 0\n",
    "\n",
    "    for row in range(rows):\n",
    "        for col in range(cols):\n",
    "            if grid[row][col] == 1:\n",
    "                result += 4\n",
    "\n",
    "\n",
    "                if row > 0 and grid[row-1][col] == 1:\n",
    "                    result -= 2\n",
    "\n",
    "                if col > 0 and grid[row][col-1] == 1:\n",
    "                    result -= 2\n",
    "\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "aee06595",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "16"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]\n",
    "\n",
    "islandPerimeter(grid)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f6f0324a",
   "metadata": {},
   "source": [
    "# 89. Sorted squares"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "f84082a8",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sortedSquares(nums):\n",
    "\n",
    "    left = 0\n",
    "    right = len(nums) - 1\n",
    "    result = [0] * len(nums)\n",
    "    n = len(nums)\n",
    "\n",
    "    for i in range(n-1, -1, -1):\n",
    "        if abs(nums[left]) < abs(nums[right]):\n",
    "            square = nums[right]\n",
    "            right -= 1\n",
    "        else:\n",
    "            square = nums[left]\n",
    "            left += 1\n",
    "\n",
    "        result[i] = square * square\n",
    "\n",
    "    return result"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6956b9fd",
   "metadata": {},
   "source": [
    "# 90. Contiguous subarrays"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "id": "b699da2f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def count_subarrays(arr): \n",
    "    \n",
    "    n = len(arr)\n",
    "    stack = []\n",
    "    result = [n] * n\n",
    "    \n",
    "    for i, x in enumerate(arr):\n",
    "        while stack and x >= arr[stack[-1]]:\n",
    "            result[stack.pop()] -= n - i\n",
    "        stack.append(i)\n",
    "    \n",
    "    stack.clear()\n",
    "    \n",
    "    for i, x in reversed(list(enumerate(arr))):\n",
    "        while stack and x >= arr[stack[-1]]:\n",
    "            result[stack.pop()] -= i + 1\n",
    "        stack.append(i)\n",
    "    \n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "id": "a236b399",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 3, 1, 5, 1]"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = [3, 4, 1, 6, 2]\n",
    "\n",
    "count_subarrays(arr)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "444a1d1e",
   "metadata": {},
   "source": [
    "# 91. Revenue milestone"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "id": "a2f4f4ee",
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "def accumulate(nums):\n",
    "    prefix_sums = []\n",
    "    total = 0\n",
    "    \n",
    "    for num in nums:\n",
    "        total += num\n",
    "        prefix_sums.append(total)\n",
    "    \n",
    "    return prefix_sums\n",
    "\n",
    "def getMilestoneDays(revenues, milestones):\n",
    "    prefix_sums = accumulate(revenues)\n",
    "    \n",
    "    def search(target):\n",
    "        left = 0\n",
    "        right = len(prefix_sums) - 1\n",
    "        \n",
    "        while left < right:\n",
    "            mid = math.floor((left + right)/2)\n",
    "            if prefix_sums[mid] < target:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left + 1 if left < len(prefix_sums) else -1\n",
    "    \n",
    "    result = []\n",
    "    \n",
    "    for milestone in milestones:\n",
    "        result.append(search(milestone))\n",
    "    \n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "id": "44e4553f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4, 6, 10]"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "revenues = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]\n",
    "milestones = [100, 200, 500]\n",
    "\n",
    "getMilestoneDays(revenues, milestones)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b6fc9a6a",
   "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
}