21_leetcode_top_150.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "1cc15fea",
   "metadata": {},
   "source": [
    "# 1. Two Sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "5180427f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def twoSum(nums, target):\n",
    "    indexMap = {}\n",
    "    \n",
    "    for i in range(len(nums)):\n",
    "        ntf = target - nums[i]\n",
    "        if nums[i] not in indexMap:\n",
    "            indexMap[ntf] = i\n",
    "        else:\n",
    "            return [indexMap[nums[i]], i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "f591c08c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [1,3,4,6,7]\n",
    "target = 7\n",
    "twoSum(nums, target)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e8948bbb",
   "metadata": {},
   "source": [
    "# 2. Roman to integer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "4ab83d7f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def romanToInt(s):\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",
    "    total = 0\n",
    "    i = 0\n",
    "    \n",
    "    while i < len(s):\n",
    "        if i + i < 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",
    "    return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "ad752b82",
   "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": "f989cdf6",
   "metadata": {},
   "source": [
    "# 3. Longest Common prefix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "4fde7c27",
   "metadata": {},
   "outputs": [],
   "source": [
    "def longestCommonPrefix(strs):\n",
    "    result = []\n",
    "    \n",
    "    for i in zip(*strs):\n",
    "        if len(set(i)) == 1:\n",
    "            result.append(i[0])\n",
    "        else:\n",
    "            break\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "0dce4864",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['f', 'l']"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "strs = [\"flower\",\"flow\",\"flight\"]\n",
    "\n",
    "longestCommonPrefix(strs)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "22e23d16",
   "metadata": {},
   "source": [
    "# 4. Valid Parenthesis"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "0daedbf0",
   "metadata": {},
   "outputs": [],
   "source": [
    "def isValid(s):\n",
    "    parens = {\n",
    "        '(':')',\n",
    "        '{':'}',\n",
    "        '[':']'\n",
    "    }\n",
    "    \n",
    "    stack = []\n",
    "    \n",
    "    for c in s:\n",
    "        if c in parens:\n",
    "            stack.append(c)\n",
    "        else:\n",
    "            if len(stack) > 0:\n",
    "                leftBracket = stack.pop()\n",
    "            else:\n",
    "                return False\n",
    "            correctBracket = parens[leftBracket]\n",
    "            if c != correctBracket:\n",
    "                return False\n",
    "    return len(stack) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "1a36ddf1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"()[]{}\"\n",
    "\n",
    "isValid(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9635ef06",
   "metadata": {},
   "source": [
    "# 5. Merge Two Sorted Lists"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "221e3b45",
   "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": "9168cf51",
   "metadata": {},
   "source": [
    "# 6. Remove Duplicates from Sorted Array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "ba5930b7",
   "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[i] != nums[j]:\n",
    "            i += 1\n",
    "            nums[i] = nums[j]\n",
    "    return i + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "a51cfeaf",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [1,1,2,2]\n",
    "removeDuplicates(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3c2075ee",
   "metadata": {},
   "source": [
    "# 7. Remove value from sorted array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "f5622352",
   "metadata": {},
   "outputs": [],
   "source": [
    "def removeValue(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": 22,
   "id": "303f1796",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [3,2,2,3]\n",
    "val = 3\n",
    "removeValue(nums, val)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fd8a8c9e",
   "metadata": {},
   "source": [
    "# 8. Plus One"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "af6eb8f1",
   "metadata": {},
   "outputs": [],
   "source": [
    "def plusOne(digits):\n",
    "    str_digits = \"\".join([str(i) for i in digits])\n",
    "    int_digits = int(str_digits)\n",
    "    result = int_digits + 1\n",
    "    str_back = str(result)\n",
    "    return [int(i) for i in str_back]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "42d4d667",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 4]"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "digits = [1,2,3]\n",
    "plusOne(digits)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f45c5cd6",
   "metadata": {},
   "source": [
    "# 9. Sqrt x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "be5d00cc",
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "def sqrt(x):\n",
    "    \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 += 1\n",
    "        else:\n",
    "            right -= 1\n",
    "    return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "c71fffd6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sqrt(12)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "785c575b",
   "metadata": {},
   "source": [
    "# 10. Climbing stairs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "13951aaf",
   "metadata": {},
   "outputs": [],
   "source": [
    "def climbStair(n):\n",
    "    if n == 1:\n",
    "        return 1\n",
    "    \n",
    "    first = 1\n",
    "    second = 2\n",
    "    third = 0\n",
    "    \n",
    "    for i in range(3, n+1):\n",
    "        third = first + second\n",
    "        first = second\n",
    "        second = third\n",
    "    return second"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "aa3ff4b1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n = 3\n",
    "climbStair(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7e28867d",
   "metadata": {},
   "source": [
    "# 11. Merge sorted array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "c017f02d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def merge(nums1, m, nums2, n):\n",
    "    nums1_copy = nums1[:m]\n",
    "    p1 = 0\n",
    "    p2 = 0\n",
    "    \n",
    "    for i in range(m+n):\n",
    "        if p2 >= n or (p1 < m and nums1_copy[p1] <= nums2[p2]):\n",
    "            nums1[i] = nums1_copy[p1]\n",
    "            p1 += 1\n",
    "        else:\n",
    "            nums1[i] = nums2[p2]\n",
    "            p2 += 1\n",
    "    return nums1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "7898ea4c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 2, 3, 5, 6]"
      ]
     },
     "execution_count": 39,
     "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": "690e416e",
   "metadata": {},
   "source": [
    "# 12. Binary tree in order"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "c884b961",
   "metadata": {},
   "outputs": [],
   "source": [
    "def inorderTraversal(root):\n",
    "    if root is None:\n",
    "        return \n",
    "    \n",
    "    result = []\n",
    "    \n",
    "    def traverseInOrder(node, result):\n",
    "        if node.left is not None:\n",
    "            traverseInOrder(node.left, result)\n",
    "        \n",
    "        result.append(node.val)\n",
    "        \n",
    "        if node.right is not None:\n",
    "            traverseInOrder(node.right, result)\n",
    "    \n",
    "    traverseInOrder(root, result)\n",
    "    return result"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a2e9c5ff",
   "metadata": {},
   "source": [
    "# 14. Tree Symmetric or not"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "e564df74",
   "metadata": {},
   "outputs": [],
   "source": [
    "def isSymmetric(root):\n",
    "    return isMirror(root, root)\n",
    "\n",
    "def isMirror(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 isMirror(p.left, q.right) and isMirror(p.right, q.left)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2ca449a4",
   "metadata": {},
   "source": [
    "# 15. Maximum Depth of binary tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "6edc31fb",
   "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": "74a62da7",
   "metadata": {},
   "source": [
    "# 16. Sorted array to binary search tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "ab39a002",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sortedArrayToBST(nums):\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",
    "    return helper(0, len(nums) - 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "943d1eaa",
   "metadata": {},
   "source": [
    "# 17. Best time to buy and sell stock"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "dc6a62e3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def maxProfit(prices):\n",
    "    min_price = float('inf')\n",
    "    max_profit = 0\n",
    "    \n",
    "    for price in prices:\n",
    "        if price < min_price:\n",
    "            min_price = price\n",
    "        elif price - min_price > max_profit:\n",
    "            max_profit = price - min_price\n",
    "    return max_profit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "fc1de00f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "prices = [7,1,5,3,6,4]\n",
    "\n",
    "maxProfit(prices)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9dcd02c6",
   "metadata": {},
   "source": [
    "# 18. Valid Palindrome"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "id": "4eafad52",
   "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": 49,
   "id": "8ccdddc4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"A man, a plan, a canal: Panama\"\n",
    "\n",
    "isPalindrome(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5a81af78",
   "metadata": {},
   "source": [
    "# 19. Single Number"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "id": "109fa96e",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "\n",
    "def singleNumber(nums):\n",
    "    nums_occurence = Counter(nums)\n",
    "    \n",
    "    for num in nums_occurence.keys():\n",
    "        if nums_occurence[num] == 1:\n",
    "            return num\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "id": "483cf4de",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [4,1,2,1,2]\n",
    "\n",
    "singleNumber(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2af5b19e",
   "metadata": {},
   "source": [
    "# 20. Linked List Cycle"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "id": "e06c19ed",
   "metadata": {},
   "outputs": [],
   "source": [
    "def hasCycle(head):\n",
    "    if not head:\n",
    "        return False\n",
    "    \n",
    "    fast = head\n",
    "    slow = head\n",
    "    \n",
    "    while fast and fast.next:\n",
    "        fast = fast.next.next\n",
    "        slow = slow.next\n",
    "        \n",
    "        if fast == slow:\n",
    "            return True\n",
    "    return False"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0dbaefff",
   "metadata": {},
   "source": [
    "# 21. Intersection of two linked lists"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "id": "25ee94d3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def getIntersectionNode(headA, headB):\n",
    "    nodes_in_B = set()\n",
    "    \n",
    "    while headB:\n",
    "        nodes_in_B.add(headB)\n",
    "        headB = headB.next\n",
    "    \n",
    "    while headA:\n",
    "        if headA in nodes_in_B:\n",
    "            return headA\n",
    "        headA = headA.next\n",
    "    return None"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7ca24244",
   "metadata": {},
   "source": [
    "# 22. Missing ranges"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "id": "5e093473",
   "metadata": {},
   "outputs": [],
   "source": [
    "def findMissingRanges(nums, lower, upper):\n",
    "    result = []\n",
    "    nums = [lower - 1] + nums + [upper + 1]\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",
    "                result.append(str(prev + 1))\n",
    "            else:\n",
    "                result.append(str(prev + 1) + '->' + str(curr - 1))\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "id": "3e8a6a95",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['2', '4->49', '51->74', '76->99']"
      ]
     },
     "execution_count": 88,
     "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": "79eb9ea7",
   "metadata": {},
   "source": [
    "# 23. Majority element"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "id": "63007ae2",
   "metadata": {},
   "outputs": [],
   "source": [
    "def majorityElement(nums):\n",
    "    count_nums = Counter(nums)\n",
    "    \n",
    "    for i in count_nums:\n",
    "        if count_nums[i] > len(nums) / 2:\n",
    "            return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "id": "a4670e60",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 90,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [2,2,1,1,1,2,2]\n",
    "majorityElement(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f487c602",
   "metadata": {},
   "source": [
    "# 24. Excel Sheet Column Number"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "id": "4a95fca3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def titleToNumber(columnTitle):\n",
    "    alpha_map = {chr(i + 65) : i + 1 for i in range(26)}\n",
    "    result = 0\n",
    "    n = len(columnTitle)\n",
    "    \n",
    "    for i in range(n):\n",
    "        currentChar = columnTitle[n - 1 - i]\n",
    "        result += (alpha_map[currentChar]) * (26 ** i)\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "id": "4f4b8e96",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "701"
      ]
     },
     "execution_count": 94,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "columnTitle = \"ZY\"\n",
    "titleToNumber(columnTitle)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a028e7bc",
   "metadata": {},
   "source": [
    "# 25. Excel sheet column title"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "id": "39797bd9",
   "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": 99,
   "id": "a9f505a6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'ZY'"
      ]
     },
     "execution_count": 99,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "columnNumber = 701\n",
    "convertToTitle(columnNumber)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bb4daf42",
   "metadata": {},
   "source": [
    "# 26. Reverse Bits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "id": "6b4df034",
   "metadata": {},
   "outputs": [],
   "source": [
    "def reverseBits(n):\n",
    "    res, power = 0, 31\n",
    "        \n",
    "    while n:\n",
    "        res += (n & 1) << power\n",
    "        n = n >> 1\n",
    "        power -= 1\n",
    "    return res"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "748a01f7",
   "metadata": {},
   "source": [
    "# 27. Number of one bits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "id": "79d20c29",
   "metadata": {},
   "outputs": [],
   "source": [
    "def hammingWeight(n):\n",
    "    sums = 0\n",
    "    \n",
    "    while n != 0:\n",
    "        sums += 1\n",
    "        n &= (n-1)\n",
    "    return sums"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "01c1c0e9",
   "metadata": {},
   "source": [
    "# 28. Happy Number"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "id": "0401b0af",
   "metadata": {},
   "outputs": [],
   "source": [
    "def isHappy(n):\n",
    "    \n",
    "    def getNext(number):\n",
    "        total_sum = 0\n",
    "        \n",
    "        while number > 0:\n",
    "            digit = number % 10\n",
    "            number = number // 10\n",
    "            total_sum += digit ** 2\n",
    "        return total_sum\n",
    "    \n",
    "    slow = n\n",
    "    fast = getNext(n)\n",
    "    \n",
    "    while fast != 1 and slow != fast:\n",
    "        slow = getNext(slow)\n",
    "        fast = getNext(getNext(fast))\n",
    "    \n",
    "    return fast == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "id": "9dbf427e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 110,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n = 19\n",
    "\n",
    "isHappy(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "93ca18f4",
   "metadata": {},
   "source": [
    "# 29. Reverse linked list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 112,
   "id": "d70cc333",
   "metadata": {},
   "outputs": [],
   "source": [
    "def reverseList(head):\n",
    "    if not head:\n",
    "        return\n",
    "    \n",
    "    curr = head\n",
    "    prev = None\n",
    "    \n",
    "    while curr:\n",
    "        nextTmp = curr.next\n",
    "        curr.next = prev\n",
    "        prev = curr\n",
    "        curr = nextTmp\n",
    "    return prev\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f1a749be",
   "metadata": {},
   "source": [
    "# 30. Contains Duplicate"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 113,
   "id": "ce4cfec5",
   "metadata": {},
   "outputs": [],
   "source": [
    "def containsDuplicate(nums):\n",
    "    count_nums = Counter(nums)\n",
    "    \n",
    "    for i in count_nums:\n",
    "        if count_nums[i] > 1:\n",
    "            return True\n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 114,
   "id": "c98fa5ae",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 114,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [1,1,1,3,3,4,3,2,4,2]\n",
    "\n",
    "containsDuplicate(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 115,
   "id": "ad62b5bc",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 115,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [1,2,3,4]\n",
    "\n",
    "containsDuplicate(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "52a17f10",
   "metadata": {},
   "source": [
    "# 31. Palindrome linked list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "8029e3b4",
   "metadata": {},
   "outputs": [],
   "source": [
    "def isPalindrome(head):\n",
    "    if not head:\n",
    "        return False\n",
    "    \n",
    "    result = []\n",
    "    \n",
    "    curr = head\n",
    "    \n",
    "    while curr:\n",
    "        result.append(curr.val)\n",
    "        curr = curr.next\n",
    "    \n",
    "    return result == result[::-1]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4e3b1337",
   "metadata": {},
   "source": [
    "# 32. Valid anagram"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "da4ac372",
   "metadata": {},
   "outputs": [],
   "source": [
    "def isAnagram(s: str, t: str):\n",
    "    if len(s) != len(t):\n",
    "        return False\n",
    "\n",
    "    return sorted(s) == sorted(t)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c9073d36",
   "metadata": {},
   "source": [
    "# 33. Missing number"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "4a0755b3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def missingNumber(nums):\n",
    "    nums.sort()\n",
    "    \n",
    "    if nums[0] != 0:\n",
    "        return 0\n",
    "    \n",
    "    if nums[-1] != len(nums):\n",
    "        return len(nums)\n",
    "    \n",
    "    for i in range(1, len(nums)):\n",
    "        expected_number = nums[i-1] + 1\n",
    "        if nums[i] != expected_number:\n",
    "            return expected_number"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "d4b86ed4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [3,0,1]\n",
    "\n",
    "missingNumber(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c6a16bd6",
   "metadata": {},
   "source": [
    "# 34. Move zeroes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "9597c3dc",
   "metadata": {},
   "outputs": [],
   "source": [
    "def moveZeroes(nums):\n",
    "    countZeroes = 0\n",
    "    left = 0\n",
    "    \n",
    "    while left < len(nums) - 1:\n",
    "        if nums[left] == 0:\n",
    "            nums.pop(left)\n",
    "            countZeroes += 1\n",
    "        else:\n",
    "            left += 1\n",
    "    \n",
    "    for i in range(countZeroes):\n",
    "        nums.append(0)\n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "31ca1874",
   "metadata": {},
   "source": [
    "# 35. Power of 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "5fe48c0c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def isPowerOfThree(n):\n",
    "    \n",
    "    if n < 0:\n",
    "        return False\n",
    "    \n",
    "    while n % 3 == 0:\n",
    "        n /= 3\n",
    "    return n == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "919bcd3f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isPowerOfThree(27)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5796331e",
   "metadata": {},
   "source": [
    "# 36. Intersection of Two Arrays II"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "cbe7131a",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "\n",
    "def intersect(nums1, nums2):\n",
    "    c = Counter(nums1) & Counter(nums2)\n",
    "    return list(c.elements())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "2ddd24d6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 2]"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums1 = [1,2,2,1]\n",
    "nums2 = [2,2]\n",
    "\n",
    "intersect(nums1, nums2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "68bb691e",
   "metadata": {},
   "source": [
    "# 37. First Unique Character in a String"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "ec225dea",
   "metadata": {},
   "outputs": [],
   "source": [
    "def firstUniqChar(s):\n",
    "    count_s = Counter(s)\n",
    "    \n",
    "    for i, c in enumerate(s):\n",
    "        if count_s[c] == 1:\n",
    "            return i\n",
    "    return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "9acea106",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"loveleetcode\"\n",
    "\n",
    "firstUniqChar(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "46af1362",
   "metadata": {},
   "source": [
    "# 38. FizzBuzz"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "0b4c5c64",
   "metadata": {},
   "outputs": [],
   "source": [
    "def fizzBuzz(n):\n",
    "    result = []\n",
    "    \n",
    "    for i in range(1, n+1):\n",
    "        if i % 3 == 0 and i % 5 == 0:\n",
    "            result.append('FizzBuzz')\n",
    "        elif i % 3 == 0:\n",
    "            result.append('Fizz')\n",
    "        elif i % 5 == 0:\n",
    "            result.append('Buzz')\n",
    "        else:\n",
    "            result.append(str(i))\n",
    "\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "8a7223f6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['1', '2', 'Fizz', '4', 'Buzz']"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n = 5\n",
    "fizzBuzz(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "63ce6965",
   "metadata": {},
   "source": [
    "# 39. Linked List Add Two Numbers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "0a196f06",
   "metadata": {},
   "outputs": [],
   "source": [
    "def addTwoNumbers(l1, l2):\n",
    "    dummyHead = ListNode(0)\n",
    "    curr = dummyHead\n",
    "    carry = 0\n",
    "    \n",
    "    while l1 != None or l2 != 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\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4749165e",
   "metadata": {},
   "source": [
    "# 40. Longest Substring Without Repeating Characters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "bc1ba3b1",
   "metadata": {},
   "outputs": [],
   "source": [
    "def lengthOfLongestSubstring(s):\n",
    "    if len(s) <= 1:\n",
    "        return len(s)\n",
    "    \n",
    "    longest = 0\n",
    "    left = 0\n",
    "    seenChars = {}\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",
    "        longest = max(longest, right - left + 1)\n",
    "    return longest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "70cab0bc",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"abcabcbb\"\n",
    "lengthOfLongestSubstring(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "a5aabccd",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"pwwkew\"\n",
    "lengthOfLongestSubstring(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "4d78f30e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = 'bbbb'\n",
    "lengthOfLongestSubstring(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8777dcbf",
   "metadata": {},
   "source": [
    "# 41. Reverse integer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "51cbca19",
   "metadata": {},
   "outputs": [],
   "source": [
    "def reverse(x):\n",
    "    s = str(abs(x))\n",
    "    reversed = int(s[::-1])\n",
    "    \n",
    "    if reversed > 2**31 - 1:\n",
    "        return 0\n",
    "    \n",
    "    return reversed if x > 0 else (reversed * -1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "198ff0e9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "321"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = 123\n",
    "reverse(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eeb3275b",
   "metadata": {},
   "source": [
    "# 42. String to Integer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "49e146ae",
   "metadata": {},
   "outputs": [],
   "source": [
    "def myAtoi(s):\n",
    "    index = 0\n",
    "    sign = 1\n",
    "    result = 0\n",
    "    n = len(s)\n",
    "    \n",
    "    INT_MAX = pow(2,31) - 1 \n",
    "    INT_MIN = -pow(2,31)\n",
    "    \n",
    "    while index < n and s[index] == ' ':\n",
    "        index += 1\n",
    "    \n",
    "    if index < n and s[index] == '+':\n",
    "        sign = 1\n",
    "        index += 1\n",
    "    elif index < n and s[index] == '-':\n",
    "        sign = -1\n",
    "        index += 1\n",
    "    \n",
    "    while index < n and s[index].isdigit():\n",
    "        digit = int(s[index])\n",
    "        \n",
    "        if ((result > INT_MAX // 10) or (result == INT_MAX // 10 and digit > INT_MAX % 10)):\n",
    "            return INT_MAX if sign == 1 else INT_MIN\n",
    "        \n",
    "        result = 10 * result + digit\n",
    "        index += 1\n",
    "    \n",
    "    return result * sign\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "2eba4c16",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-42"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"   -42\"\n",
    "\n",
    "myAtoi(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "97f7fa8f",
   "metadata": {},
   "source": [
    "# 43. Container With Most Water"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "12210d99",
   "metadata": {},
   "outputs": [],
   "source": [
    "def maxArea(height):\n",
    "    max_area = 0\n",
    "    left = 0\n",
    "    right = len(height) - 1\n",
    "    \n",
    "    while left < right:\n",
    "        length = right - left\n",
    "        width = min(height[right], height[left])\n",
    "        area = length * width\n",
    "        max_area = max(max_area, area)\n",
    "        if height[left] <= height[right]:\n",
    "            left += 1\n",
    "        else:\n",
    "            right -= 1\n",
    "    return max_area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "0f2c2fcc",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "49"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "height = [1,8,6,2,5,4,8,3,7]\n",
    "\n",
    "maxArea(height)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "921e889d",
   "metadata": {},
   "source": [
    "# 44. Three Sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "758c8c6b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def threeSum(nums):\n",
    "    result = []\n",
    "    nums.sort()\n",
    "    \n",
    "    for i in range(len(nums)):\n",
    "        if nums[i] > 0:\n",
    "            break\n",
    "        if i == 0 or nums[i-1] != nums[i]:\n",
    "            twoSum(nums, i, result)\n",
    "    return result\n",
    "\n",
    "def twoSum(nums, i, result):\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",
    "            result.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"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "74e4458a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[-1, -1, 2], [-1, 0, 1]]"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [-1,0,1,2,-1,-4]\n",
    "threeSum(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7fa23faf",
   "metadata": {},
   "source": [
    "# 45. Letter Combinations of a Phone Number\n",
    "\n",
    "T --> O(4^N * N)\n",
    "\n",
    "S --> O(N)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "343ff7d5",
   "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",
    "    \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",
    "            for j in letter_map[int(digits[i])]:\n",
    "                queue.append(currLetter + j)\n",
    "            s -= 1\n",
    "    return queue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "203dc931",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "digits = \"23\"\n",
    "\n",
    "letterCombinations(digits)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8befdfec",
   "metadata": {},
   "source": [
    "# 46. Remove Nth node from end of linked list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "id": "9e9488ac",
   "metadata": {},
   "outputs": [],
   "source": [
    "def removeNthFromEnd(head, n):\n",
    "    dummy = ListNode(0)\n",
    "    dummy.next = head\n",
    "    first = dummy\n",
    "    second = dummy\n",
    "\n",
    "    # first pointer moves n + 1 steps while second pointer remains the same\n",
    "    # so gap between first and second is n nodes apart\n",
    "    for i in range(1, n+2):\n",
    "        first = first.next\n",
    "\n",
    "    # move first to end, maintaining the gap\n",
    "    while first != None:\n",
    "        first = first.next\n",
    "        second = second.next\n",
    "\n",
    "    second.next = second.next.next\n",
    "    return dummy.next"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ad141339",
   "metadata": {},
   "source": [
    "# 47. Generate Parentheses\n",
    "\n",
    "T --> O(4^N/N^0.5)\n",
    "\n",
    "S --> O(4^N/N^0.5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "id": "bf5e5c34",
   "metadata": {},
   "outputs": [],
   "source": [
    "def generateParenthesis(n):\n",
    "    result = []\n",
    "    stack = []\n",
    "    left_bracket_count = 0\n",
    "    right_bracket_count = 0\n",
    "    \n",
    "    def backtrack(stack, left_bracket_count, right_bracket_count):\n",
    "        if len(stack) == 2 * n:\n",
    "            result.append(\"\".join(stack))\n",
    "            return\n",
    "        \n",
    "        if left_bracket_count < n:\n",
    "            stack.append('(')\n",
    "            backtrack(stack, left_bracket_count + 1, right_bracket_count)\n",
    "            stack.pop()\n",
    "        \n",
    "        if right_bracket_count < left_bracket_count:\n",
    "            stack.append(')')\n",
    "            backtrack(stack, left_bracket_count, right_bracket_count + 1)\n",
    "            stack.pop()\n",
    "    \n",
    "    backtrack(stack, left_bracket_count, right_bracket_count)\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "id": "23eab5bc",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['((()))', '(()())', '(())()', '()(())', '()()()']"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n = 3\n",
    "generateParenthesis(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "id": "4247f099",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['a', 'b', 'c']"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list('abc')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9276bf47",
   "metadata": {},
   "source": [
    "# 48. Find the Index of the First Occurrence in a String\n",
    "\n",
    "T --> O(n * h)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "id": "ce835377",
   "metadata": {},
   "outputs": [],
   "source": [
    "def strStr(needle, haystack):\n",
    "    \n",
    "    for i in range(len(haystack) - len(needle) + 1):\n",
    "        if haystack[i:i+len(needle)] == needle:\n",
    "            return i\n",
    "    return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "id": "fda0ef43",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "haystack = \"sadbutsad\"\n",
    "needle = \"sad\"\n",
    "\n",
    "strStr(needle, haystack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "id": "7e93aeb4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-1"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "haystack = \"leetcode\"\n",
    "needle = \"leeto\"\n",
    "strStr(needle, haystack)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2162879e",
   "metadata": {},
   "source": [
    "# 49. Find First and Last Position of Element in Sorted Array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "8ff5fad3",
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "def searchRange(nums, target):\n",
    "    if len(nums) == 0:\n",
    "        return [-1, -1]\n",
    "    \n",
    "    firstPosition = binarySearch(nums, target, 0, len(nums) - 1)\n",
    "    \n",
    "    if firstPosition == -1:\n",
    "        return [-1, -1]\n",
    "    \n",
    "    startPosition = firstPosition\n",
    "    endPosition = firstPosition\n",
    "    temp1 = 0\n",
    "    temp2 = 0\n",
    "    \n",
    "    while startPosition != -1:\n",
    "        temp1 = startPosition\n",
    "        startPosition = binarySearch(nums, target, 0, startPosition - 1)\n",
    "    startPosition = temp1\n",
    "    \n",
    "    while endPosition != -1:\n",
    "        temp2 = endPosition\n",
    "        endPosition = binarySearch(nums, target, endPosition + 1, len(nums) - 1)\n",
    "    endPosition = temp2\n",
    "    \n",
    "    return [startPosition, endPosition]\n",
    "\n",
    "def binarySearch(nums, target, left, right):\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": 2,
   "id": "1f6724c5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 4]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [5,7,7,8,8,10]\n",
    "target = 8\n",
    "\n",
    "searchRange(nums, target)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9bcaddd1",
   "metadata": {},
   "source": [
    "# 50. Permutations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "a1c52046",
   "metadata": {},
   "outputs": [],
   "source": [
    "def permute(nums):\n",
    "    result = []\n",
    "    path = []\n",
    "    dfs(nums, path, result)\n",
    "    return result\n",
    "\n",
    "def dfs(nums, path, result):\n",
    "    if not nums:\n",
    "        result.append(path)\n",
    "    for i in range(len(nums)):\n",
    "        dfs(nums[:i] + nums[i+1:], path + [nums[i]], result)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "9fdd0c50",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [1,2,3]\n",
    "\n",
    "permute(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "136403d5",
   "metadata": {},
   "source": [
    "# 51. Group Anagrams"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "696195e1",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "def groupAnagrams(strs):\n",
    "    ans = defaultdict(list)\n",
    "    \n",
    "    \n",
    "    for s in strs:\n",
    "        count = [0] * 26\n",
    "        for c in s:\n",
    "            count[ord(c) - ord('a')] += 1\n",
    "        ans[tuple(count)].append(s)\n",
    "    return ans.values()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "8389873f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "dict_values([['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']])"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "strs = [\"eat\",\"tea\",\"tan\",\"ate\",\"nat\",\"bat\"]\n",
    "groupAnagrams(strs)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "84caf6ad",
   "metadata": {},
   "source": [
    "# 52. Pow(x,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "4bd72b35",
   "metadata": {},
   "outputs": [],
   "source": [
    "def myPow(x, n):\n",
    "    if n == 0:\n",
    "        return 1\n",
    "    \n",
    "    if n < 0:\n",
    "        return myPow(1/x, -n)\n",
    "    \n",
    "    lower = myPow(x, n//2)\n",
    "    \n",
    "    if n % 2 == 0:\n",
    "        return lower * lower\n",
    "    else:\n",
    "        return lower * lower * x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "f2a64bcf",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "9.261000000000001"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "myPow(2.1, 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06e0f099",
   "metadata": {},
   "source": [
    "# 53. Maximum Subarray"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "a26f1e93",
   "metadata": {},
   "outputs": [],
   "source": [
    "def maxSubArray(nums):\n",
    "    currentSubarray = nums[0]\n",
    "    maxSubarray = nums[0]\n",
    "    \n",
    "    for num in nums[1:]:\n",
    "        currentSubarray = max(num, currentSubarray + num)\n",
    "        maxSubarray = max(maxSubarray, currentSubarray)\n",
    "    \n",
    "    return maxSubarray"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "230c79b9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [-2,1,-3,4,-1,2,1,-5,4]\n",
    "\n",
    "maxSubArray(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "b2816de5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "1%4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ed29e812",
   "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
}