16_leetcode_easy_second_round.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "81ad2590",
   "metadata": {},
   "source": [
    "# 1. Two Sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "be95b9fc",
   "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 [i, index_map[nums[i]]]\n",
    "    return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "f8daf0bc",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 1]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [2,4,3,7]\n",
    "target = 7\n",
    "\n",
    "twoSum(nums, target)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ea87fa19",
   "metadata": {},
   "source": [
    "# 2. Palindrome Number\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "3b1bb64d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def isPalindrome(x):\n",
    "    \n",
    "    x = str(x)\n",
    "    \n",
    "    if '-' in x:\n",
    "        return False\n",
    "    \n",
    "    return x == x[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "4e1b90f9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isPalindrome(121)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8c32e21b",
   "metadata": {},
   "source": [
    "# 3. Roman to Integer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "f4171aba",
   "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",
    "        \n",
    "    total = 0\n",
    "    i = 0\n",
    "    \n",
    "    while i < len(s):\n",
    "        if i + 1 < len(s) and values[s[i + 1]] > values[s[i]]:\n",
    "            total += values[s[i+1]] - values[s[i]]\n",
    "            i += 2\n",
    "        else:\n",
    "            total += values[s[i]]\n",
    "            i += 1\n",
    "    \n",
    "    return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "e6dc7e44",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "58"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"LVIII\"\n",
    "\n",
    "romanToInt(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c017086c",
   "metadata": {},
   "source": [
    "# 4. Longest common prefix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "d7e807ac",
   "metadata": {},
   "outputs": [],
   "source": [
    "def longestCommonPrefix(strs):\n",
    "    \n",
    "    result = []\n",
    "    \n",
    "    \n",
    "    for i in zip(*strs):\n",
    "        if len(set(i)) == 1:\n",
    "            result.append(i[0])\n",
    "        else:\n",
    "            break\n",
    "    return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "350359ec",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['f', 'l']"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "strs = [\"flower\",\"flow\",\"flight\"]\n",
    "\n",
    "longestCommonPrefix(strs)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0c144095",
   "metadata": {},
   "source": [
    "# 5. Valid parenthesis"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "d2ad7f09",
   "metadata": {},
   "outputs": [],
   "source": [
    "def isValid(s):\n",
    "    \n",
    "    parens = {\n",
    "        '(':')',\n",
    "        '{':'}',\n",
    "        '[':']'\n",
    "    }\n",
    "    \n",
    "    stack = []\n",
    "    \n",
    "    for i in s:\n",
    "        if i in parens.keys():\n",
    "            stack.append(i)\n",
    "        else:\n",
    "            if len(stack) > 0:\n",
    "                lastBracket = stack.pop()\n",
    "            else:\n",
    "                return False\n",
    "            correctBracket = parens[lastBracket]\n",
    "            if i != correctBracket:\n",
    "                return False\n",
    "    \n",
    "    return len(stack) == 0\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "2b1686b6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"()[]{}\"\n",
    "\n",
    "isValid(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "9b9e39f5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = '{[()]}'\n",
    "isValid(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8361f5ed",
   "metadata": {},
   "source": [
    "# 6. Merge Two Sorted Lists"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "fbeb76b3",
   "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": "d0da9f48",
   "metadata": {},
   "source": [
    "# 7. Remove Duplicates from Sorted Array\n",
    "\n",
    "i += 1 before"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "f31e59ef",
   "metadata": {},
   "outputs": [],
   "source": [
    "def removeDuplicates(nums):\n",
    "    if len(nums) == 0:\n",
    "        return 0\n",
    "    \n",
    "    i = 0\n",
    "    \n",
    "    for j in range(len(nums)):\n",
    "        if nums[j] != nums[i]:\n",
    "            i += 1\n",
    "            nums[i] = nums[j]\n",
    "            \n",
    "    return i + 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "79a61289",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [1,1,2]\n",
    "\n",
    "removeDuplicates(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "70250dba",
   "metadata": {},
   "source": [
    "# 8. Remove element\n",
    "\n",
    "i += 1 after"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "id": "5edfb616",
   "metadata": {},
   "outputs": [],
   "source": [
    "def removeElement(nums, val):\n",
    "    if len(nums) == 0:\n",
    "        return 0\n",
    "    \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": 59,
   "id": "84765d43",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [3,2,2,3]\n",
    "val = 3\n",
    "\n",
    "removeElement(nums, val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "id": "8e97cd3e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [0,1,2,2,3,0,4,2]\n",
    "val = 2\n",
    "removeElement(nums, val)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "84b7d1d8",
   "metadata": {},
   "source": [
    "# 9. Search insert position\n",
    "\n",
    "Return left if not found"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "8c63a317",
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "def searchInsert(nums, target):\n",
    "    \n",
    "    left = 0\n",
    "    right = len(nums) - 1\n",
    "    \n",
    "    while left <= right:\n",
    "        mid = math.floor((left + right)/2)\n",
    "        if nums[mid] == target:\n",
    "            return mid\n",
    "        elif nums[mid] < target:\n",
    "            left = mid + 1\n",
    "        else:\n",
    "            right = mid - 1\n",
    "    return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "38a7237f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [1,3,5,6]\n",
    "target = 2\n",
    "\n",
    "searchInsert(nums, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "08cd168b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [1,3,5,6]\n",
    "target = 5\n",
    "\n",
    "searchInsert(nums, target)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "07488774",
   "metadata": {},
   "source": [
    "# 10. Length of Last Word"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "id": "146ede2e",
   "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": 67,
   "id": "0dbe5c24",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"   fly me   to   the moon  \"\n",
    "lengthOfLastWord(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bedab66b",
   "metadata": {},
   "source": [
    "# 11. Plus One"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "id": "3f20df63",
   "metadata": {},
   "outputs": [],
   "source": [
    "def plusOne(digits):\n",
    "    s = \"\".join([str(i) for i in digits])\n",
    "    \n",
    "    int_s = int(s)\n",
    "    result = int_s + 1\n",
    "    str_result = str(result)\n",
    "    \n",
    "    return [int(i) for i in str_result]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "id": "018579ed",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 4]"
      ]
     },
     "execution_count": 71,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "digits = [1,2,3]\n",
    "\n",
    "plusOne(digits)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "49a0e9d4",
   "metadata": {},
   "source": [
    "# 12. Add binary"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "id": "bc7e6614",
   "metadata": {},
   "outputs": [],
   "source": [
    "# int(a,2) --> O(n), bin() --> O(logn)\n",
    "\n",
    "def addBinary(a, b):\n",
    "    \n",
    "    return bin(int(a,2) + int(b,2)).replace('0b', '')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "id": "c125a347",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'100'"
      ]
     },
     "execution_count": 73,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = \"11\"\n",
    "b = \"1\"\n",
    "\n",
    "addBinary(a, b)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "35b64ea5",
   "metadata": {},
   "source": [
    "# 14. Sqrt X\n",
    "\n",
    "Return right if not found"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "id": "f90bfd94",
   "metadata": {},
   "outputs": [],
   "source": [
    "def mySqrt(x):\n",
    "    if x < 2:\n",
    "        return 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": 75,
   "id": "a094a4bb",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 75,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mySqrt(7)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5e1ba675",
   "metadata": {},
   "source": [
    "# 15. Climbing stairs "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "id": "a76276ee",
   "metadata": {},
   "outputs": [],
   "source": [
    "def climbStairs(n):\n",
    "    if n == 1:\n",
    "        return 1\n",
    "    \n",
    "    first = 1\n",
    "    second = 2\n",
    "    \n",
    "    third = 0\n",
    "    \n",
    "    for i in range(3, n+1):\n",
    "        third = first + second\n",
    "        first = second\n",
    "        second = third\n",
    "        \n",
    "    return second"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "id": "8b513bf7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 78,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "climbStairs(4)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5e05af78",
   "metadata": {},
   "source": [
    "# 16. Remove Duplicates from Sorted Linked List"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "id": "328d327f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def deleteDuplicates(head):\n",
    "    if not head:\n",
    "        return None\n",
    "    \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": "022e338f",
   "metadata": {},
   "source": [
    "# 17. Merge Sorted Array\n",
    "\n",
    "## IMP"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "id": "d79928ae",
   "metadata": {},
   "outputs": [],
   "source": [
    "def merge(nums1, m, nums2, n):\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": 83,
   "id": "1bbd6f73",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 2, 3, 5, 6]"
      ]
     },
     "execution_count": 83,
     "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": "8fee7add",
   "metadata": {},
   "source": [
    "# 18. Binary tree In order traversal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "id": "447fb2a3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def inorderTraversal(root):\n",
    "    if not root:\n",
    "        return None\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",
    "    return result"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "785af841",
   "metadata": {},
   "source": [
    "# 19. Same tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "id": "f69da3c1",
   "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": "e70da12a",
   "metadata": {},
   "source": [
    "# 20. Symmetric Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "id": "fb8d9bd0",
   "metadata": {},
   "outputs": [],
   "source": [
    "def isSymmetric(root):\n",
    "    return isMirror(root, root)\n",
    "\n",
    "def isMirror(node1, node2):\n",
    "    if not node1 and not node2:\n",
    "        return True\n",
    "    if not node1 or not node2:\n",
    "        return False\n",
    "    if node1.val != node2.val:\n",
    "        return False\n",
    "    return isMirror(node1.left, node2.right) and isMirror(node1.right, node2.left)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "de80887c",
   "metadata": {},
   "source": [
    "# 21. Max depth"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "id": "787c08ac",
   "metadata": {},
   "outputs": [],
   "source": [
    "def maxDepth(root):\n",
    "    if not root:\n",
    "        return 0\n",
    "    else:\n",
    "        leftHeight = maxDepth(root.left)\n",
    "        rightHeight = maxDepth(root.right)\n",
    "        return max(leftHeight, rightHeight) + 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a477aad5",
   "metadata": {},
   "source": [
    "# 22. Sorted array to binary search tree\n",
    "\n",
    "T --> O(n)\n",
    "\n",
    "S --> O(logN) (height)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "id": "e11c3898",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sortedArrayToBST(nums):\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(0, len(nums) - 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0408ccfc",
   "metadata": {},
   "source": [
    "# 23. Balanced Binary tree\n",
    "\n",
    "T --> O(nlogn)\n",
    "\n",
    "S --> O(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "id": "3b8f4fce",
   "metadata": {},
   "outputs": [],
   "source": [
    "def isBalanced(root):\n",
    "    \n",
    "    def height(node):\n",
    "        if not node:\n",
    "            return None\n",
    "        else:\n",
    "            leftHeight = height(node.left)\n",
    "            rightHeight = height(node.right)\n",
    "            return max(leftHeight, rightHeight) + 1\n",
    "        \n",
    "    return abs(height(root.left) - height(root.right)) < 2 and isBalanced(root.left) and isBalanced(root.right)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "049d0733",
   "metadata": {},
   "source": [
    "# 24. Minimum Depth of Binary Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "id": "5bc78239",
   "metadata": {},
   "outputs": [],
   "source": [
    "def minDepth(root):\n",
    "    if not root:\n",
    "        return 0\n",
    "    \n",
    "    children = [root.left, root.right]\n",
    "    \n",
    "    if not children:\n",
    "        return 1\n",
    "    \n",
    "    min_depth = float('inf')\n",
    "    \n",
    "    for c in children:\n",
    "        if c:\n",
    "            min_depth = min(min_depth, minDepth(c))\n",
    "    \n",
    "    return min_depth + 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e4b867f1",
   "metadata": {},
   "source": [
    "# 25. Path Sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "id": "8ccdc040",
   "metadata": {},
   "outputs": [],
   "source": [
    "def hasPathSum(root, targetSum):\n",
    "    if root is None:\n",
    "        return False\n",
    "    \n",
    "    queue = [(root, targetSum - root.val)]\n",
    "    \n",
    "    while queue:\n",
    "        currNode, currSum = queue.pop(0)\n",
    "        \n",
    "        if currSum == 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, currSum - currNode.left.val))\n",
    "            \n",
    "        if currNode.right is not None:\n",
    "            queue.append((currNode.right, currSum - currNode.right.val))\n",
    "        \n",
    "    return False\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e42205ab",
   "metadata": {},
   "source": [
    "# 26. Best time to buy and sell stock"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "id": "b3edbc8d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def maxProfit(prices):\n",
    "    min_price = float('inf')\n",
    "    max_profit = 0\n",
    "    \n",
    "    for i in prices:\n",
    "        if i < min_price:\n",
    "            min_price = i\n",
    "        elif i - min_price > max_profit:\n",
    "            max_profit = i - min_price\n",
    "    return max_profit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "id": "7c283201",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 96,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "prices = [7,1,5,3,6,4]\n",
    "\n",
    "maxProfit(prices)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "id": "b25b3fe7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 97,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "prices = [7,6,4,3,1]\n",
    "\n",
    "maxProfit(prices)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "82de598d",
   "metadata": {},
   "source": [
    "# 27. Valid Palindrome\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "id": "99af1393",
   "metadata": {},
   "outputs": [],
   "source": [
    "def isPalindrome(s):\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",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "id": "cf52306c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 102,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"A man, a plan, a canal: Panama\"\n",
    "\n",
    "isPalindrome(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6ecf7a01",
   "metadata": {},
   "source": [
    "# 28. Single Number"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "id": "6b632bc7",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "\n",
    "def singleNumber(nums):\n",
    "    \n",
    "    count_map = Counter(nums)\n",
    "    \n",
    "    for i in count_map.keys():\n",
    "        if count_map[i] == 1:\n",
    "            return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "id": "f530ea0c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 107,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [2,2,1]\n",
    "\n",
    "singleNumber(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "id": "f46a11b1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 108,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [4,1,2,1,2]\n",
    "singleNumber(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d4ebb52d",
   "metadata": {},
   "source": [
    "# 29. Linked List Cycle\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "id": "6f5e1825",
   "metadata": {},
   "outputs": [],
   "source": [
    "def hasCycle(head):\n",
    "    if head is None:\n",
    "        return False\n",
    "    \n",
    "    rabbit = head\n",
    "    tortoise = head\n",
    "    \n",
    "    while rabbit is not None and rabbit.next is not None:\n",
    "        rabbit = rabbit.next.next\n",
    "        tortoise = tortoise.next\n",
    "        \n",
    "        if rabbit == tortoise:\n",
    "            return True\n",
    "    return False"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8a175b75",
   "metadata": {},
   "source": [
    "# 30. Binary tree Post order traversal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "id": "d0eb8285",
   "metadata": {},
   "outputs": [],
   "source": [
    "def postorderTraversal(root):\n",
    "    if root is None:\n",
    "        return None\n",
    "    \n",
    "    result = []\n",
    "    \n",
    "    def traverse(node, result):\n",
    "        if node.left is not None:\n",
    "            traverse(node.left, result)\n",
    "        \n",
    "        if node.right is not None:\n",
    "            traverse(node.right, result)\n",
    "        \n",
    "        result.append(node.val)\n",
    "    \n",
    "    traverse(root, result)\n",
    "    \n",
    "    return result"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "191d0bba",
   "metadata": {},
   "source": [
    "# 31. Read4\n",
    "\n",
    "## IMP"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "id": "a68dc240",
   "metadata": {},
   "outputs": [],
   "source": [
    "def read(buf, n):\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": "63c4a13d",
   "metadata": {},
   "source": [
    "# 32. Intersection of Two Linked Lists"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 112,
   "id": "fd133d1b",
   "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": "7bc9800b",
   "metadata": {},
   "source": [
    "# 33. Missing Ranges\n",
    "\n",
    "## IMP"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "cb4a3b6a",
   "metadata": {},
   "outputs": [],
   "source": [
    "def findMissingRanges(nums, lower, upper):\n",
    "    \n",
    "    nums = [lower - 1] + nums + [upper + 1]\n",
    "    \n",
    "    result = []\n",
    "    \n",
    "    print(nums)\n",
    "    \n",
    "    for i in range(1, len(nums)):\n",
    "        curr, prev = nums[i], nums[i-1]\n",
    "        if curr - prev > 1:\n",
    "            addRange(result, prev, curr)\n",
    "    return result\n",
    "\n",
    "def addRange(result, low, high):\n",
    "    if low + 2 == high:\n",
    "        result.append(str(low + 1))\n",
    "    else:\n",
    "        result.append(str(low + 1) + '->' + str(high - 1))\n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "b7a3724e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[-1, 0, 1, 3, 50, 75, 100]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "['2', '4->49', '51->74', '76->99']"
      ]
     },
     "execution_count": 12,
     "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": "4c13552d",
   "metadata": {},
   "source": [
    "# 34. Excel Sheet Column Title"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "6a4e1ec6",
   "metadata": {},
   "outputs": [],
   "source": [
    "def convertToTitle(columnNumber):\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",
    "    return \"\".join(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "9ac10071",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'AB'"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "columnNumber = 28\n",
    "\n",
    "convertToTitle(columnNumber)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9738fcf4",
   "metadata": {},
   "source": [
    "# 35. Majority Element\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "09ecdd6b",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "\n",
    "def majorityElement(nums):\n",
    "    \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": 14,
   "id": "06026c24",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [2,2,1,1,1,2,2]\n",
    "\n",
    "majorityElement(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ff0d7fff",
   "metadata": {},
   "source": [
    "# 36. Excel Sheet Column Number"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "1785ad6f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def titleToNumber(columnTitle):\n",
    "    \n",
    "    alpha_map = {chr(i + 65):i+1 for i in range(26)}\n",
    "    \n",
    "    result = 0\n",
    "    n = len(columnTitle)\n",
    "    for i in range(n):\n",
    "        current_char = columnTitle[n-1-i]\n",
    "        result += (alpha_map[current_char] * (26 ** i))\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "ba5e558a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "28"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "columnTitle = \"AB\"\n",
    "\n",
    "titleToNumber(columnTitle)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7963b635",
   "metadata": {},
   "source": [
    "# 37. Happy number\n",
    "\n",
    "Use Floyd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "761b941e",
   "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",
    "        return total_sum\n",
    "    \n",
    "    slow_runner = n\n",
    "    fast_runner = getNext(n)\n",
    "    \n",
    "    while fast_runner != 1 and slow_runner != fast_runner:\n",
    "        slow_runner = getNext(slow_runner)\n",
    "        fast_runner = getNext(getNext(fast_runner))\n",
    "    \n",
    "    return fast_runner == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "fde7f923",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n = 19\n",
    "\n",
    "isHappy(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8cec7db3",
   "metadata": {},
   "source": [
    "# 38. Remove Linked List Elements\n",
    "\n",
    "Use sentinel"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "e4749b57",
   "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",
    "        if curr.val == val:\n",
    "            prev.next = curr.next\n",
    "        else:\n",
    "            prev = curr\n",
    "        curr = curr.next\n",
    "    \n",
    "    return sentinel.next"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dfa7f31a",
   "metadata": {},
   "source": [
    "# 39. Isomorphic Strings"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "abdfda23",
   "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, c in enumerate(s):\n",
    "        if c not in index_mapping:\n",
    "            index_mapping[c] = i\n",
    "        result.append(str(index_mapping[c]))\n",
    "    return \"\".join(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "f47c5f02",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"egg\" \n",
    "t = \"add\"\n",
    "\n",
    "isIsomorphic(s, t)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "42ffc759",
   "metadata": {},
   "source": [
    "# 40. Reverse linkedlist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "451b7d4d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def reverseList(head):\n",
    "    if head is None:\n",
    "        return None\n",
    "    \n",
    "    prev = None\n",
    "    curr = head\n",
    "    \n",
    "    while curr is not None:\n",
    "        nextTmp = curr.next\n",
    "        curr.next = prev\n",
    "        prev = curr\n",
    "        curr = nextTmp\n",
    "    \n",
    "    return prev"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3e0f5f30",
   "metadata": {},
   "source": [
    "# 41. Contains Duplicate II"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "7ff7faf6",
   "metadata": {},
   "outputs": [],
   "source": [
    "def containsNearbyDuplicate(nums, k):\n",
    "    index_map = {}\n",
    "    \n",
    "    for i, c in enumerate(nums):\n",
    "        if c in index_map and i - index_map[c] <= k:\n",
    "            return True\n",
    "        index_map[c] = i\n",
    "    \n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "2c9460bf",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [1,2,3,1]\n",
    "k = 3\n",
    "\n",
    "containsNearbyDuplicate(nums, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "85a32a99",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [1,2,3,1,2,3]\n",
    "k = 2\n",
    "\n",
    "containsNearbyDuplicate(nums, k)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "56c346e6",
   "metadata": {},
   "source": [
    "# 42. Invert binary tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "9e72722b",
   "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": "8abd68d4",
   "metadata": {},
   "source": [
    "# 43. Summary ranges"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "aff0bc15",
   "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",
    "            ans.append(str(nums[pointer]) + '->' + str(c) if nums[pointer] != c else str(c))\n",
    "            pointer = i + 1\n",
    "    \n",
    "    return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "id": "acecfaa0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['0->2', '4->5', '7']"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [0,1,2,4,5,7]\n",
    "\n",
    "summaryRanges(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c3ce8a44",
   "metadata": {},
   "source": [
    "# 44. Palindrome Linked List"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "id": "a7f7da49",
   "metadata": {},
   "outputs": [],
   "source": [
    "def isPalindrome(head):\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": "2d27e011",
   "metadata": {},
   "source": [
    "# 45. Shortest word distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "id": "f2a97439",
   "metadata": {},
   "outputs": [],
   "source": [
    "def shortestDistance(wordsDict, word1, word2):\n",
    "    \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": 52,
   "id": "b4e49ca4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "wordsDict = [\"practice\", \"makes\", \"perfect\", \"coding\", \"makes\"]\n",
    "word1 = \"coding\"\n",
    "word2 = \"practice\"\n",
    "\n",
    "shortestDistance(wordsDict, word1, word2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ec3c679c",
   "metadata": {},
   "source": [
    "# 46. Custom sort string\n",
    "\n",
    "## IMP"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "id": "7a14fba8",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "    \n",
    "def customSortString(order, s):\n",
    "    count_s = Counter(s)\n",
    "    \n",
    "    ans = []\n",
    "    \n",
    "    for c in order:\n",
    "        ans.append(c * count_s[c])\n",
    "        count_s[c] = 0\n",
    "    \n",
    "    for c in count_s:\n",
    "        ans.append(c * count_s[c])\n",
    "    \n",
    "    return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "id": "41a67673",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'cbad'"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "order = \"cbafg\"\n",
    "s = \"abcd\"\n",
    "\n",
    "customSortString(order, s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b8bbf8fc",
   "metadata": {},
   "source": [
    "# 47. Next Greater Element I\n",
    "\n",
    "## IMP"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "id": "1f368aa4",
   "metadata": {},
   "outputs": [],
   "source": [
    "def nextGreaterElement(nums1, nums2):\n",
    "    \n",
    "    next_number = {}\n",
    "    stack = []\n",
    "    \n",
    "    for num2 in nums2:\n",
    "        while len(stack) > 0 and num2 > stack[-1]:\n",
    "            num1 = stack.pop()\n",
    "            next_number[num1] = num2\n",
    "        stack.append(num2)\n",
    "    \n",
    "    while stack:\n",
    "        num1 = stack.pop()\n",
    "        next_number[num1] = -1\n",
    "    \n",
    "    result = [next_number[num1] for num1 in nums1]\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "id": "c7fabe4a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[-1, 3, -1]"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums1 = [4,1,2]\n",
    "nums2 = [1,3,4,2]\n",
    "\n",
    "nextGreaterElement(nums1, nums2)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e454397f",
   "metadata": {},
   "source": [
    "# 48. Longest Continuous Increasing Subsequence"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "id": "60f63ed4",
   "metadata": {},
   "outputs": [],
   "source": [
    "def findLengthOfLCIS(nums):\n",
    "\n",
    "    if len(nums) == 1:\n",
    "        return 1\n",
    "\n",
    "    left = 0\n",
    "    ans = 0\n",
    "\n",
    "    for i in range(1, len(nums)):\n",
    "        if nums[i - 1] >= nums[i]:\n",
    "            left = i\n",
    "        ans = max(ans, i - left + 1)\n",
    "\n",
    "    return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "id": "7463fef0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [1,3,5,4,7]\n",
    "\n",
    "findLengthOfLCIS(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "05c78f55",
   "metadata": {},
   "source": [
    "# 49. Split a String in Balanced Strings"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "id": "872fcdd7",
   "metadata": {},
   "outputs": [],
   "source": [
    "def balancedStringSplit(s):\n",
    "    \n",
    "    res = 0\n",
    "    cnt = 0\n",
    "    \n",
    "    for i in s:\n",
    "        if i == 'L':\n",
    "            cnt += 1\n",
    "        if i == 'R':\n",
    "            cnt -= 1\n",
    "        if cnt == 0:\n",
    "            res += 1\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "id": "7b946939",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"RLRRLLRLRL\"\n",
    "\n",
    "balancedStringSplit(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6827b8e1",
   "metadata": {},
   "source": [
    "# 50. Find common characters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "8b85758c",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "\n",
    "def findCommonChars(words):\n",
    "    res = Counter(words[0])\n",
    "    \n",
    "    for i in words:\n",
    "        res &= Counter(i)\n",
    "    \n",
    "    return list(res.elements())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "5a3e291c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['a', 'e', 'l', 'l']"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "words = ['abella', 'aballe', 'citadell']\n",
    "\n",
    "findCommonChars(words)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "35b1bf25",
   "metadata": {},
   "source": [
    "# 51. Nestedlist sum\n",
    "\n",
    "## IMP"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "id": "babf27b4",
   "metadata": {},
   "outputs": [],
   "source": [
    "def depthSumInverse(nestedList):\n",
    "    \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",
    "    \n",
    "    return total_sum"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "15fb8ee2",
   "metadata": {},
   "source": [
    "# 52. Sorted squares\n",
    "\n",
    "## IMP"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "80b4bad7",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sortedSquares(nums):\n",
    "    n = len(nums)\n",
    "    result = [0] * n\n",
    "    left = 0\n",
    "    right = n - 1\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": "code",
   "execution_count": 19,
   "id": "fcd6c34a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 9, 16, 100]"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [-4,-1,0,3,10]\n",
    "\n",
    "sortedSquares(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b6aa9367",
   "metadata": {},
   "source": [
    "# 53. Maximum Size Subarray Sum Equals k\n",
    "\n",
    "## IMP"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "id": "df66bb8e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def maxSubArrayLen(nums, k):\n",
    "    prefix_sum = 0\n",
    "    longest = 0\n",
    "    indices = {}\n",
    "    \n",
    "    for i, num in enumerate(nums):\n",
    "        prefix_sum += num\n",
    "        \n",
    "        if prefix_sum == k:\n",
    "            longest = i + 1\n",
    "        \n",
    "        if prefix_sum - k in indices:\n",
    "            longest = max(longest, i - indices[prefix_sum - k])\n",
    "        \n",
    "        if prefix_sum not in indices:\n",
    "            indices[prefix_sum] = i\n",
    "    \n",
    "    return longest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "id": "e16bbdd8",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 72,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [1,-1,5,-2,3]\n",
    "k = 3\n",
    "\n",
    "maxSubArrayLen(nums, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "525a4032",
   "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
}