3b_udemy_course_practice.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "edb37a2d",
   "metadata": {},
   "source": [
    "# A) Arrays\n",
    "\n",
    "## 1. Two Sum\n",
    "\n",
    "https://leetcode.com/problems/two-sum/\n",
    "\n",
    "T --> O(n)\n",
    "\n",
    "S --> O(n)\n",
    "\n",
    "Brute Force --> Iterate through array in two for loops and check every two item"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "f4ab9d88",
   "metadata": {},
   "outputs": [],
   "source": [
    "def twoSum(nums, target):\n",
    "    if len(nums) <= 1:\n",
    "        return -1\n",
    "    \n",
    "    hash_map = {}\n",
    "    \n",
    "    for i in range(len(nums)):\n",
    "        ntf = target - nums[i]\n",
    "        if nums[i] not in hash_map.keys():\n",
    "            hash_map[ntf] = i\n",
    "        else:\n",
    "            return [hash_map[nums[i]], i]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "85379575",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [2,7,11,15]\n",
    "target = 9\n",
    "\n",
    "twoSum(nums, target)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b65710f4",
   "metadata": {},
   "source": [
    "# 2. Container with most water\n",
    "\n",
    "https://leetcode.com/problems/container-with-most-water/\n",
    "\n",
    "T --> O(n)\n",
    "\n",
    "S --> O(1)\n",
    "\n",
    "Brute Force --> Iterate in two for loops and check area for every two element pairs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "446bd3c7",
   "metadata": {},
   "outputs": [],
   "source": [
    "def maxArea(height):\n",
    "    maxArea = 0\n",
    "    \n",
    "    left = 0\n",
    "    right = len(height) - 1\n",
    "    \n",
    "    while left < right:\n",
    "        length = min(height[left], height[right])\n",
    "        width = right - left\n",
    "        area = length*width\n",
    "        maxArea = max(area, maxArea)\n",
    "        if height[left] <= height[right]:\n",
    "            left += 1\n",
    "        else:\n",
    "            right -= 1\n",
    "    return maxArea"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "cc50dc4a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "49"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "height = [1,8,6,2,5,4,8,3,7]\n",
    "maxArea(height)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "67bb6b22",
   "metadata": {},
   "source": [
    "# 3. Trapping rainwater\n",
    "\n",
    "For each element in the array, we find the maximum level of water it can trap after the rain, which is equal to the minimum of maximum height of bars on both the sides minus its own height.\n",
    "\n",
    "\n",
    "https://leetcode.com/problems/trapping-rain-water/solution/\n",
    "\n",
    "T --> O(n)\n",
    "\n",
    "S --> O(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "858d326b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def trap(height):\n",
    "    total = 0\n",
    "    left = 0\n",
    "    right = len(height) - 1\n",
    "    max_left = 0\n",
    "    max_right = 0\n",
    "    \n",
    "    while left < right:\n",
    "        if height[left] < height[right]:\n",
    "            if height[left] < max_left:\n",
    "                total += max_left - height[left]\n",
    "            else:\n",
    "                max_left = height[left]\n",
    "            left += 1\n",
    "        else:\n",
    "            if height[right] < max_right:\n",
    "                total += max_right - height[right]\n",
    "            else:\n",
    "                max_right = height[right]\n",
    "            right -= 1\n",
    "    return total\n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "247410fb",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "elevationArray = [0,1,0,2,1,0,1,3,2,1,2,1]\n",
    "\n",
    "trap(elevationArray)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "87b7dd98",
   "metadata": {},
   "source": [
    "# 4. Typed out strings\n",
    "\n",
    "https://leetcode.com/problems/backspace-string-compare/\n",
    "\n",
    "T --> O(M+N)\n",
    "\n",
    "S --> O(M+N)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "9d2f1d35",
   "metadata": {},
   "outputs": [],
   "source": [
    "def backspaceCompare(s, t):\n",
    "    stack_s = []\n",
    "    stack_t = []\n",
    "    \n",
    "    for i in range(len(s)):\n",
    "        if s[i] != '#':\n",
    "            stack_s.append(s[i])\n",
    "        else:\n",
    "            if len(stack_s) > 0:\n",
    "                stack_s.pop()\n",
    "    \n",
    "    for i in range(len(t)):\n",
    "        if t[i] != '#':\n",
    "            stack_t.append(t[i])\n",
    "        else:\n",
    "            if len(stack_t) > 0:\n",
    "                stack_t.pop()\n",
    "    \n",
    "    return stack_s == stack_t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "5f792a1e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"ab#c\"\n",
    "t = \"ad#c\"\n",
    "backspaceCompare(s,t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "7c487771",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"a#\"\n",
    "t = \"\"\n",
    "backspaceCompare(s,t)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9b3c7e56",
   "metadata": {},
   "source": [
    "# 5. Longest Substring without repeating characters\n",
    "\n",
    "https://leetcode.com/problems/longest-substring-without-repeating-characters/solution/\n",
    "\n",
    "Sliding window\n",
    "\n",
    "T --> O(n)\n",
    "\n",
    "S --> O(min(m,n))\n",
    "\n",
    "Brute Force --> Check all the substring one by one to see if it has no duplicate character.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "ffe327da",
   "metadata": {},
   "outputs": [],
   "source": [
    "def lengthOfLongestSubstring(s):\n",
    "    longest = 0\n",
    "    left = 0\n",
    "    seen_chars = {}\n",
    "    \n",
    "    for right in range(len(s)):\n",
    "        currChar = s[right]\n",
    "        prevSeenChar = -1\n",
    "        if currChar in seen_chars.keys():\n",
    "            prevSeenChar = seen_chars[currChar]\n",
    "        if prevSeenChar >= left:\n",
    "            left = prevSeenChar + 1\n",
    "        seen_chars[currChar] = right\n",
    "        longest = max(longest, right - left + 1)\n",
    "    return longest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "b4d97fd8",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"abcabcbb\"\n",
    "lengthOfLongestSubstring(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dc4f412c",
   "metadata": {},
   "source": [
    "# 6. Valid Palindrome\n",
    "\n",
    "https://leetcode.com/problems/valid-palindrome/\n",
    "\n",
    "T --> O(n)\n",
    "\n",
    "S --> O(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "4007d7d5",
   "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",
    "        left += 1\n",
    "        right -= 1\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "8e88852c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"A man, a plan, a canal: Panama\"\n",
    "isPalindrome(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "1c691cea",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"race a car\"\n",
    "isPalindrome(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2e1b462e",
   "metadata": {},
   "source": [
    "# 7. Almost Palindrome\n",
    "\n",
    "https://leetcode.com/problems/valid-palindrome-ii/\n",
    "\n",
    "T --> O(N)\n",
    "\n",
    "The main while loop we use can iterate up to N / 2 times, since each iteration represents a pair of characters. On any given iteration, we may find a mismatch and call checkPalindrome twice. checkPalindrome can also iterate up to N / 2 times, in the worst case where the first and last character of s do not match.\n",
    "\n",
    "S --> O(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "87ad0bf6",
   "metadata": {},
   "outputs": [],
   "source": [
    "def almost_palindrome(s):\n",
    "    \n",
    "    def check_palindrome(s, i, j):\n",
    "        while i < j:\n",
    "            if s[i] != s[j]:\n",
    "                return False\n",
    "        return True\n",
    "    \n",
    "    left = 0\n",
    "    right = len(s) - 1\n",
    "    \n",
    "    while left < right:\n",
    "        if s[left] != s[right]:\n",
    "            return check_palindrome(s, left, right-1) or check_palindrome(s, left+1, right)\n",
    "        left += 1\n",
    "        right -= 1\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "090c4062",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"abca\"\n",
    "almost_palindrome(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "af345833",
   "metadata": {},
   "source": [
    "# 8. Reverse a LinkedList\n",
    "\n",
    "https://leetcode.com/problems/reverse-linked-list/solution/\n",
    "\n",
    "T --> O(n)\n",
    "\n",
    "S --> O(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "id": "a901a86a",
   "metadata": {},
   "outputs": [],
   "source": [
    "from functools import reduce\n",
    " \n",
    "# template to create node list\n",
    "class ListNode:\n",
    "    def __init__(self, val, next = None):\n",
    "            self.val = val\n",
    "            self.next = next\n",
    " \n",
    "# ---- Generate our linked list ----\n",
    "linkedList = reduce(lambda acc, val: ListNode(val, acc), [5,4,3,2,1], None) \n",
    " \n",
    "# ---- Print our linked list ----\n",
    " \n",
    "def printList(head):\n",
    "    if(not head):\n",
    "        return\n",
    " \n",
    "    print(head.val)\n",
    "    printList(head.next)\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "74368a7b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def reverseList(head):\n",
    "    \n",
    "    prev = None\n",
    "    current = head\n",
    "    \n",
    "    while current is not None:\n",
    "        nextTemp = current.next\n",
    "        current.next = prev\n",
    "        prev = current\n",
    "        current = nextTemp\n",
    "    \n",
    "    return prev"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "8d56b4b8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n",
      "4\n",
      "3\n",
      "2\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "printList(reverseList(linkedList))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9fc9cad1",
   "metadata": {},
   "source": [
    "# 9. Reverse linkedlist II\n",
    "\n",
    "https://leetcode.com/problems/reverse-linked-list-ii/\n",
    "\n",
    "[1,2,3,4,5] (2,4) --> [1,4,3,2,5]\n",
    "\n",
    "T --> O(n)\n",
    "S --> O(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "282576df",
   "metadata": {},
   "outputs": [],
   "source": [
    "def reverseList2(head, left, right):\n",
    "    \n",
    "    currentPos = 1\n",
    "    currentNode = head\n",
    "    start = head\n",
    "    \n",
    "    while currentPos < left:\n",
    "        start = currentNode\n",
    "        currentNode= currentNode.next\n",
    "        currentPos += 1\n",
    "    \n",
    "    list_so_far = None\n",
    "    tail = currentNode\n",
    "    \n",
    "    while currentPos >= left and currentPos <= right:\n",
    "        nextTemp = currentNode.next\n",
    "        currentNode.next = list_so_far\n",
    "        list_so_far = currentNode\n",
    "        currentNode = nextTemp\n",
    "        currentPos += 1\n",
    "    \n",
    "    start.next = list_so_far\n",
    "    tail.next = currentNode\n",
    "    \n",
    "    if left > 1:\n",
    "        return head\n",
    "    else:\n",
    "        return list_so_far"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "id": "fcd7943c",
   "metadata": {},
   "outputs": [],
   "source": [
    "linkedList = reduce(lambda acc, val: ListNode(val, acc), [5,4,3,2,1], None) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "id": "ac1e5572",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "After reverse\n",
      "1\n",
      "4\n",
      "3\n",
      "2\n",
      "5\n"
     ]
    }
   ],
   "source": [
    "printList(linkedList)\n",
    "print('After reverse')\n",
    "printList(reverseBetween(linkedList, 2, 4))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "id": "cea27ae6",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1---2---3---4---5---6\n",
      "        |\n",
      "        7---8---9---10\n",
      "            |\n",
      "            11---12\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "# helper functions\n",
    "\n",
    "class Node:\n",
    "  def __init__(self, val=None, prev=None, \n",
    "                next=None, child=None):\n",
    "    self.val = val\n",
    "    self.next = next\n",
    "    self.prev = prev\n",
    "    self.child = child\n",
    "\n",
    "null = None\n",
    "\n",
    "def makeLists(array):\n",
    "  '''\n",
    "  Recursively generates the complete graph from given serialization\n",
    "  Parameter:\n",
    "    array - serialization of the list as Python list\n",
    "  Returns:\n",
    "    head to the top most list (first node of the\n",
    "    graph)\n",
    "  '''\n",
    "  head = None\n",
    "  prev = None\n",
    "  i = 0\n",
    "  while i < len(array):\n",
    "    if array[i] != null:\n",
    "      node = Node(val=array[i], prev=prev)\n",
    "      if prev is None:\n",
    "        head = prev = node\n",
    "      else:\n",
    "        prev.next = node\n",
    "        prev = node\n",
    "      i += 1\n",
    "    else:\n",
    "      node = head\n",
    "      end = False\n",
    "      while array[i] == null:\n",
    "        if node.next is None:\n",
    "          end = True\n",
    "        else:\n",
    "          node = node.next\n",
    "        i += 1\n",
    "      if end:\n",
    "        node.child = makeLists(array[i:])\n",
    "      else:\n",
    "        node.prev.child = makeLists(array[i:])\n",
    "      break\n",
    "  return head\n",
    "\n",
    "def strLists(head, lists):\n",
    "  '''\n",
    "  Helper function to recursively serialize the graph prior to visualization. It's an interim step and\n",
    "  only meant to be called by the printLists function.\n",
    "\n",
    "  Parameters:\n",
    "    head - head of the present list \n",
    "    lists - the serialization being built recursively (passed by reference)\n",
    "\n",
    "  Returns:\n",
    "    None (lists is updated in place). \n",
    "  '''\n",
    "  if head is None:\n",
    "    return\n",
    "  nodes = []\n",
    "  while head:\n",
    "    nodes.append(str(head.val))\n",
    "    if head.child is not None:\n",
    "      nodes.append('|')\n",
    "      strLists(head.child, lists)\n",
    "    head = head.next\n",
    "  lists.append(nodes)\n",
    "\n",
    "def printLists(head):\n",
    "  '''\n",
    "  Visualizes the entire graph\n",
    "  Parameter:\n",
    "    head - the top most Node\n",
    "  '''\n",
    "  lists = []\n",
    "  strLists(head, lists)\n",
    "  if lists == []:\n",
    "    print(None)\n",
    "    return\n",
    "  previndent = 0\n",
    "  for j, l in enumerate(lists[::-1]):\n",
    "    count = -1\n",
    "    indent = 0\n",
    "    s = []\n",
    "    for i in range(len(l)):\n",
    "      if l[i] != '|':\n",
    "        s.append(l[i])\n",
    "        count += 1\n",
    "      else:\n",
    "        indent = count * 4\n",
    "        child = count\n",
    "    print('---'.join(s)) \n",
    "    if  len(lists) > 1 and j < len(lists) - 1:\n",
    "      previndent += indent\n",
    "      indentation = ''.join([' '] * previndent)\n",
    "      if len(l[0]) > 1:\n",
    "        indentation += ''.join([' '] * child)\n",
    "      print(indentation + '|')\n",
    "      print(indentation, end='')\n",
    "\n",
    "def checkLinks(head, lists=None):\n",
    "  '''\n",
    "  Verifies that all lists can be traversed in both directions.\n",
    "\n",
    "  Parameter:\n",
    "    head - top most Node\n",
    "\n",
    "  Returns:\n",
    "    Boolean, True if all lists traversable, False if not.\n",
    "  '''\n",
    "  if head is None:\n",
    "    return True\n",
    "  if lists is None:\n",
    "    lists = []\n",
    "  stack = []\n",
    "  result = True\n",
    "  node = head\n",
    "  while node is not None:\n",
    "    if node.child is not None:\n",
    "      checkLinks(node.child, lists)\n",
    "    stack.append(node)\n",
    "    prev = node\n",
    "    node = node.next\n",
    "  while prev is not None:\n",
    "    if len(stack) == 0 or stack.pop() != prev:\n",
    "      result = False\n",
    "    prev = prev.prev\n",
    "  lists.append(result)\n",
    "  return all(lists)\n",
    "\n",
    "\n",
    "# Example to show usage\n",
    "array = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]\n",
    "head = makeLists(array)\n",
    "printLists(head)\n",
    "print(checkLinks(head))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "436cbd55",
   "metadata": {},
   "source": [
    "# 10. Flatten multilevel doubly linkedlist\n",
    "\n",
    "https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/\n",
    "\n",
    "T --> O(n)\n",
    "\n",
    "S --> O(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "id": "3e57f8b1",
   "metadata": {},
   "outputs": [],
   "source": [
    "def flatten(head):\n",
    "    if head is None:\n",
    "        return head\n",
    "    \n",
    "    currentNode = head\n",
    "    \n",
    "    while currentNode is not None:\n",
    "        if currentNode.child is None:\n",
    "            currentNode = currentNode.next\n",
    "        else:\n",
    "            tail = currentNode.child\n",
    "            while tail.next is not None:\n",
    "                tail = tail.next\n",
    "            tail.next = currentNode.next\n",
    "            if tail.next is not None:\n",
    "                tail.next.prev = tail\n",
    "            currentNode.next = currentNode.child\n",
    "            currentNode.next.prev = currentNode\n",
    "            currentNode.child = None\n",
    "    return head\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "id": "0166c1b2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1---2---3---7---8---11---12---9---10---4---5---6\n"
     ]
    }
   ],
   "source": [
    "printLists(flatten(head))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fbb7691e",
   "metadata": {},
   "source": [
    "# 11. LinkedList Cycle - I\n",
    "\n",
    "https://leetcode.com/problems/linked-list-cycle/\n",
    "\n",
    "T --> O(n)\n",
    "\n",
    "S --> O(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "id": "2a87bfb3",
   "metadata": {},
   "outputs": [],
   "source": [
    "from functools import reduce\n",
    " \n",
    "class ListNode:\n",
    "    def __init__(self, val, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "        \n",
    "# ---- Generate our linked list ----\n",
    "lis = [8,7,6,5,4,3,2,1]\n",
    "linkedList = reduce(lambda acc, val: ListNode(val, acc), lis, None)\n",
    " \n",
    "curr = linkedList\n",
    "cycleNode = None\n",
    " \n",
    " \n",
    "while(curr.next != None):\n",
    "    if(curr.val == 3):\n",
    " \n",
    "        cycleNode = curr\n",
    "  \n",
    "    curr = curr.next\n",
    " \n",
    " \n",
    "curr.next = cycleNode"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "id": "320acd25",
   "metadata": {},
   "outputs": [],
   "source": [
    "def hasCycle(head):\n",
    "    tortoise = head\n",
    "    hare = head\n",
    "    \n",
    "    while hare is not None and hare.next is not None:\n",
    "        tortoise = tortoise.next\n",
    "        hare = hare.next.next\n",
    "        \n",
    "        if tortoise == hare:\n",
    "            return True\n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "id": "e723dabc",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "hasCycle(curr)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a60419f9",
   "metadata": {},
   "source": [
    "# 12. LinkedList Cycle - II\n",
    "\n",
    "https://leetcode.com/problems/linked-list-cycle-ii/solution/\n",
    "\n",
    "T --> O(n)\n",
    "\n",
    "S --> O(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "id": "c95dcd1d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def getIntersect(head):\n",
    "    tortoise = head\n",
    "    hare = head\n",
    "    \n",
    "    while hare is not None and hare.next is not None:\n",
    "        tortoise = tortoise.next \n",
    "        hare = hare.next.next\n",
    "        if tortoise == hare:\n",
    "            return hare\n",
    "    return None\n",
    "\n",
    "def detectCycle(head):\n",
    "    if head is None:\n",
    "        return None\n",
    "    \n",
    "    intersect = getIntersect(head)\n",
    "    \n",
    "    if intersect is None:\n",
    "        return None\n",
    "    \n",
    "    ptr1 = head\n",
    "    ptr2 = intersect\n",
    "    \n",
    "    while ptr1 != ptr2:\n",
    "        ptr1 = ptr1.next\n",
    "        ptr2 = ptr2.next\n",
    "    \n",
    "    return ptr1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "id": "4898fb27",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 70,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "detectCycle(curr)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f1db0499",
   "metadata": {},
   "source": [
    "# 13. Valid Parenthesis\n",
    "\n",
    "https://leetcode.com/problems/valid-parentheses/\n",
    "\n",
    "T --> O(n)\n",
    "\n",
    "S --> O(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "id": "0ff45a0c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def isValid(s):\n",
    "    \n",
    "    parens = {\n",
    "        '(':')',\n",
    "        '{':'}',\n",
    "        '[':']'\n",
    "    }\n",
    "    \n",
    "    stack = []\n",
    "    \n",
    "    for i in range(len(s)):\n",
    "        if s[i] in parens.keys():\n",
    "            stack.append(s[i])\n",
    "        else:\n",
    "            if len(stack) > 0:\n",
    "                leftBracket = stack.pop()\n",
    "            else:\n",
    "                return False\n",
    "            correctBracket = parens[leftBracket]\n",
    "            \n",
    "            if s[i] != correctBracket:\n",
    "                return False\n",
    "    return len(stack) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "id": "a34c6899",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 73,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"()[]{}\"\n",
    "isValid(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "id": "1de5a743",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 74,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = ']('\n",
    "isValid(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1c0fd6a8",
   "metadata": {},
   "source": [
    "# 14. Minimum remove to make valid parenthesis\n",
    "\n",
    "https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/\n",
    "\n",
    "T --> O(n)\n",
    "\n",
    "S --> O(n)\n",
    "\n",
    "As explained above, we should use a stack. If we put the indexes of the \"(\" on the stack, then we'll know that all the indexes on the stack at the end are the indexes of the unmatched \"(\". We should also use a set to keep track of the unmatched \")\" we come across. Then, we can remove the character at each of those indexes and then return the edited string."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "id": "50b44bb2",
   "metadata": {},
   "outputs": [],
   "source": [
    "def minRemoveToMakeValid(s):\n",
    "    indexes_to_remove = set()\n",
    "    stack = []\n",
    "    \n",
    "    for i, c in enumerate(s):\n",
    "        if c not in '()':\n",
    "            continue\n",
    "        if c == '(':\n",
    "            stack.append(i)\n",
    "        elif not stack:\n",
    "            indexes_to_remove.add(i)\n",
    "        else:\n",
    "            stack.pop()\n",
    "    \n",
    "    \n",
    "    indexes_to_remove = indexes_to_remove.union(set(stack))\n",
    "    string_builder = []\n",
    "    \n",
    "    for i, c in enumerate(s):\n",
    "        if i not in indexes_to_remove:\n",
    "            string_builder.append(c)\n",
    "    \n",
    "    return \"\".join(string_builder)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "id": "9960eee3",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "''"
      ]
     },
     "execution_count": 81,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "minRemoveToMakeValid('))((')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "id": "ce4f24e8",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'lee(t(c)o)de'"
      ]
     },
     "execution_count": 82,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "minRemoveToMakeValid('lee(t(c)o)de)')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "60d4305b",
   "metadata": {},
   "source": [
    "# 15. Find kth Largest element\n",
    "\n",
    "https://leetcode.com/problems/kth-largest-element-in-an-array/solution/\n",
    "\n",
    "## Divide and Conquer\n",
    "\n",
    "T --> O(nlogn)\n",
    "\n",
    "S --> O(nlogn)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "id": "6d2e361c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def quicksort(nums, left, right):\n",
    "    if left < right:\n",
    "        partitionIndex = partition(nums, left, right)\n",
    "        quicksort(nums, left, partitionIndex - 1)\n",
    "        quicksort(nums, partitionIndex + 1, right)\n",
    "\n",
    "def swap(nums, i, j):\n",
    "    temp = nums[i]\n",
    "    nums[i] = nums[j]\n",
    "    nums[j] = temp\n",
    "    \n",
    "\n",
    "\n",
    "def partition(nums, left, right):\n",
    "    pivotElement = nums[right]\n",
    "    partitionIndex = left\n",
    "    \n",
    "    for j in range(left, right):\n",
    "        \n",
    "        if nums[j] <= pivotElement:\n",
    "            swap(nums, partitionIndex, j)\n",
    "            partitionIndex += 1\n",
    "    swap(nums, partitionIndex, right)\n",
    "    return partitionIndex\n",
    "\n",
    "def findKthLargest(nums, k):\n",
    "    quicksort(nums, 0, len(nums) - 1)\n",
    "    return nums[-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "id": "a46e7da9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 108,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [3,2,1,5,6,4]\n",
    "k = 3\n",
    "findKthLargest(nums, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "id": "76805863",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 109,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "findKthLargest([5,6,1,4,8,3],2)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0ef142aa",
   "metadata": {},
   "source": [
    "## Quickselect\n",
    "\n",
    "T --> O(n)\n",
    "\n",
    "S --> O(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "15b6aa2d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def findKthLargest(nums, k):\n",
    "    index_to_find = len(nums) - k\n",
    "    quickselect(nums, 0, len(nums) - 1, index_to_find)\n",
    "    print(nums)\n",
    "    return nums[-k]\n",
    "\n",
    "\n",
    "def quickselect(nums, left, right, index_to_find):\n",
    "    partitionIndex = partition(nums, left, right)\n",
    "    \n",
    "    if index_to_find == partitionIndex:\n",
    "        return nums[index_to_find]\n",
    "    elif index_to_find > partitionIndex:\n",
    "        return quickselect(nums, partitionIndex + 1, right, index_to_find)\n",
    "    else:\n",
    "        return quickselect(nums, left, partitionIndex - 1, index_to_find)\n",
    "\n",
    "def partition(nums, left, right):\n",
    "    pivotElement = nums[right]\n",
    "    partitionIndex = left\n",
    "    \n",
    "    for j in range(left, right):\n",
    "        if nums[j] <= pivotElement:\n",
    "            nums[partitionIndex], nums[j] = nums[j], nums[partitionIndex]\n",
    "            partitionIndex += 1\n",
    "    nums[partitionIndex], nums[right] = nums[right], nums[partitionIndex]\n",
    "    return partitionIndex\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "3a72d56e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 3, 5, 4, 6, 8]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "findKthLargest([5,6,1,4,8,3],2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "f7256bf2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 6, 5]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [3,2,1,5,6,4]\n",
    "k = 4\n",
    "findKthLargest(nums, k)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d939e4bf",
   "metadata": {},
   "source": [
    "# 16. Start and End of a target\n",
    "\n",
    "https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/\n",
    "\n",
    "T --> O(logn)\n",
    "\n",
    "S --> O(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "ee1f8714",
   "metadata": {},
   "outputs": [],
   "source": [
    "def binary_search(nums, no_to_find, left, right):\n",
    "    \n",
    "    while left <= right:\n",
    "        mid = ((left + right)//2)\n",
    "        if nums[mid] == no_to_find:\n",
    "            return mid\n",
    "        elif nums[mid] < no_to_find:\n",
    "            left = mid + 1\n",
    "        else:\n",
    "            right = mid - 1\n",
    "    return -1\n",
    "\n",
    "def start_and_end(nums, target):\n",
    "    if len(nums) == 0:\n",
    "        return [-1, -1]\n",
    "    \n",
    "    firstPosition = binary_search(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 = binary_search(nums, target, 0, startPosition - 1)\n",
    "    startPosition = temp1\n",
    "    \n",
    "    while endPosition != -1:\n",
    "        temp2 = endPosition\n",
    "        endPosition = binary_search(nums, target, endPosition + 1, len(nums) - 1)\n",
    "    endPosition = temp2\n",
    "    \n",
    "    return [startPosition, endPosition]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "07ec3e4e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 4]"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [5,7,7,8,8,10]\n",
    "\n",
    "start_and_end(nums, 8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "916a0a19",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, val: int):\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.val = val\n",
    "\n",
    "    def __repr__(self):\n",
    "        return str(self.val)\n",
    "\n",
    "    def insert_node(self, val):\n",
    "        if self.val is not None:\n",
    "            if val < self.val:\n",
    "                if self.left is None:\n",
    "                    self.left = Node(val)\n",
    "                else:\n",
    "                    self.left.insert_node(val)\n",
    "            elif val > self.val:\n",
    "                if self.right is None:\n",
    "                    self.right = Node(val)\n",
    "                else:\n",
    "                    self.right.insert_node(val)\n",
    "\n",
    "    @staticmethod\n",
    "    def insert_nodes(vals: list, root):\n",
    "        for i in vals:\n",
    "            root.insert_node(i)\n",
    "\n",
    "    def bfs(self, root=None):\n",
    "        if root is None:\n",
    "            return\n",
    "        result = []\n",
    "        queue = [root]\n",
    "\n",
    "        while len(queue) > 0:\n",
    "            cur_node = queue.pop(0)\n",
    "            result.append(cur_node.val)\n",
    "            if cur_node.left is not None:\n",
    "                queue.append(cur_node.left)\n",
    "\n",
    "            if cur_node.right is not None:\n",
    "                queue.append(cur_node.right)\n",
    "\n",
    "            #print(queue)\n",
    "        return result\n",
    "    \n",
    "    def DFSInorder(self, root=None):\n",
    "        return self.traverseInOrder(root, [])\n",
    "    \n",
    "    def DFSPostOrder(self, root=None):\n",
    "        return self.traversePostOrder(root, [])\n",
    "    \n",
    "    def DFSPreOrder(self, root=None):\n",
    "        return self.traversePreOrder(root, [])\n",
    "    \n",
    "    def traverseInOrder(self, node, data):\n",
    "        if node.left is not None:\n",
    "            node.traverseInOrder(node.left, data)\n",
    "        data.append(node.val)\n",
    "        \n",
    "        if node.right is not None:\n",
    "            node.traverseInOrder(node.right, data)\n",
    "        #print(data)\n",
    "        return data\n",
    "    \n",
    "    def traversePostOrder(self, node, data):\n",
    "        \n",
    "        if node.left is not None:\n",
    "            node.traversePostOrder(node.left, data)\n",
    "              \n",
    "        if node.right is not None:\n",
    "            node.traversePostOrder(node.right, data)\n",
    "        #print(data)\n",
    "        data.append(node.val)\n",
    "        return data\n",
    "    \n",
    "    def traversePreOrder(self, node, data):\n",
    "        data.append(node.val)\n",
    "        if node.left is not None:\n",
    "            node.traversePreOrder(node.left, data)\n",
    "        \n",
    "        \n",
    "        if node.right is not None:\n",
    "            node.traversePreOrder(node.right, data)\n",
    "        #print(data)\n",
    "        return data\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "1a29df5c",
   "metadata": {},
   "outputs": [],
   "source": [
    "#       9\n",
    "#    4     20\n",
    "#  1  6  15   170\n",
    "\n",
    "def run():\n",
    "    root = Node(9)\n",
    "    root.insert_nodes([4,6,20,170,15,1], root)\n",
    "    bfs_result = root.bfs(root=root)\n",
    "    dfs_inorder = root.DFSInorder(root)\n",
    "    dfs_preorder = root.DFSPreOrder(root)\n",
    "    dfs_postorder = root.DFSPostOrder(root)\n",
    "    return root, bfs_result, dfs_inorder, dfs_preorder, dfs_postorder"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "117b224a",
   "metadata": {},
   "outputs": [],
   "source": [
    "root, bfs_result, dfs_inorder, dfs_preorder, dfs_postorder = run()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "393c2fa5",
   "metadata": {},
   "source": [
    "# 17. Maximum depth of a binary tree\n",
    "\n",
    "https://leetcode.com/problems/maximum-depth-of-binary-tree/\n",
    "\n",
    "T --> O(n)\n",
    "\n",
    "S --> O(logN) (height of the tree). Worst case: O(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "15d0bfa0",
   "metadata": {},
   "outputs": [],
   "source": [
    "def maxDepth(root):\n",
    "    if root is None:\n",
    "        return 0\n",
    "    else:\n",
    "        left_height = maxDepth(root.left)\n",
    "        right_height = maxDepth(root.right)\n",
    "        return max(left_height, right_height) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "53e91c5d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "maxDepth(root)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e1ee512b",
   "metadata": {},
   "source": [
    "# 18. Level order of binary tree\n",
    "\n",
    "https://leetcode.com/problems/binary-tree-level-order-traversal/\n",
    "\n",
    "T --> O(n)\n",
    "\n",
    "S --> O(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "f491bddb",
   "metadata": {},
   "outputs": [],
   "source": [
    "def levelOrder(root):\n",
    "    if root is None:\n",
    "        return\n",
    "    \n",
    "    result = []\n",
    "    queue = [root]\n",
    "    \n",
    "    while len(queue) > 0:\n",
    "        queue_length = len(queue)\n",
    "        currentLevelValues = []\n",
    "        counter = 0\n",
    "        \n",
    "        while counter < queue_length:\n",
    "            print(counter, queue)\n",
    "            currNode = queue.pop(0)\n",
    "            currentLevelValues.append(currNode.val)\n",
    "            \n",
    "            if currNode.left is not None:\n",
    "                queue.append(currNode.left)\n",
    "            \n",
    "            if currNode.right is not None:\n",
    "                queue.append(currNode.right)\n",
    "            \n",
    "            counter += 1\n",
    "        result.append(currentLevelValues)\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "7b118248",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 [9]\n",
      "0 [4, 20]\n",
      "1 [20, 1, 6]\n",
      "0 [1, 6, 15, 170]\n",
      "1 [6, 15, 170]\n",
      "2 [15, 170]\n",
      "3 [170]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[[9], [4, 20], [1, 6, 15, 170]]"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "levelOrder(root)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "53155001",
   "metadata": {},
   "source": [
    "# 19. Right side view of a tree\n",
    "\n",
    "https://leetcode.com/problems/binary-tree-right-side-view/\n",
    "\n",
    "T --> O(N)\n",
    "\n",
    "S --> O(H) --> O(logN) (worst case O(N)) (skewed tree)\n",
    "\n",
    "The trick here is pre order dfs with NRL instead of NLR"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "5f7b1315",
   "metadata": {},
   "outputs": [],
   "source": [
    "def rightSideView(root):\n",
    "    data = []\n",
    "    level = 0\n",
    "    return traversePreOrder(root, data, level)\n",
    "\n",
    "def traversePreOrder(node, data, level):\n",
    "    if not node:\n",
    "        return\n",
    "    \n",
    "    if level >= len(data):\n",
    "        data.append(node.val)\n",
    "    \n",
    "    if node.right is not None:\n",
    "        traversePreOrder(node.right, data, level+1)\n",
    "    \n",
    "    if node.left is not None:\n",
    "        traversePreOrder(node.left, data, level+1)\n",
    "        \n",
    "    return data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "a0434973",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[9, 20, 170]"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rightSideView(root)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f8b89984",
   "metadata": {},
   "source": [
    "# 20. Number of nodes in a complete tree\n",
    "\n",
    "https://leetcode.com/problems/count-complete-tree-nodes/\n",
    "\n",
    "## Naive\n",
    "\n",
    "T --> O(N)\n",
    "\n",
    "S --> O(logN)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "c54a8efc",
   "metadata": {},
   "outputs": [],
   "source": [
    "def countNodes(root):\n",
    "    if root is None:\n",
    "        return 0\n",
    "    else:\n",
    "        return countNodes(root.left) + countNodes(root.right) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "3b4c5c53",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "countNodes(root)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9738065c",
   "metadata": {},
   "source": [
    "## Binary search\n",
    "\n",
    "T --> O(h^2 + h) --> O(h^2) --> O(logN^2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "id": "5dd4b444",
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "def getTreeHeight(node):\n",
    "    height = 0\n",
    "    \n",
    "    while node.left is not None:\n",
    "        node = node.left\n",
    "        height += 1\n",
    "    return height\n",
    "\n",
    "def node_exists(index_to_find, height, node):\n",
    "    left = 0\n",
    "    right = 2**height - 1\n",
    "    counter = 0\n",
    "    \n",
    "    while counter < height:\n",
    "        midpoint = math.ceil((left + right)/2)\n",
    "        if index_to_find >= midpoint:\n",
    "            node = node.right\n",
    "            left = midpoint\n",
    "        else:\n",
    "            node = node.left\n",
    "            right = midpoint - 1\n",
    "        counter += 1\n",
    "    return node is not None\n",
    "\n",
    "def countNodes(root):\n",
    "    if root is None:\n",
    "        return 0\n",
    "    \n",
    "    height = getTreeHeight(root)\n",
    "    \n",
    "    if height == 0:\n",
    "        return 1\n",
    "    \n",
    "    upper_count = 2**height - 1\n",
    "    \n",
    "    left = 0\n",
    "    right = upper_count\n",
    "    \n",
    "    while left < right:\n",
    "        index_to_find = math.ceil((left+right)/2)\n",
    "        if node_exists(index_to_find, height, root):\n",
    "            left = index_to_find\n",
    "        else:\n",
    "            right = index_to_find - 1\n",
    "    return upper_count + left + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "id": "3ad171bd",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "countNodes(root)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e10c9a00",
   "metadata": {},
   "source": [
    "# 21. Validate binary search tree\n",
    "\n",
    "https://leetcode.com/problems/validate-binary-search-tree/\n",
    "\n",
    "T --> O(n)\n",
    "\n",
    "S --> O(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "53f64e94",
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "def isValidBST(root):\n",
    "    \n",
    "    def isValid(node, low=-math.inf, high=math.inf):\n",
    "        if not node:\n",
    "            return True\n",
    "        if node.val <= low or node.val >= high:\n",
    "            return False\n",
    "        return isValid(node.right, node.val, high) or isValid(node.left, low, node.val)\n",
    "    \n",
    "    return isValid(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "98bcbb0d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isValidBST(root)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6a9981c3",
   "metadata": {},
   "source": [
    "# 22. DFS in 2d array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "adf2903d",
   "metadata": {},
   "outputs": [],
   "source": [
    "directions = [[-1, 0], [0, 1], [1, 0], [0, -1]]\n",
    "\n",
    "def traversalDFS(arr2d):\n",
    "    \n",
    "    rows, cols = len(arr2d), len(arr2d[0])\n",
    "    \n",
    "    seen = [[False for x in range(cols)] for y in range(rows)]\n",
    "    \n",
    "    values = []\n",
    "    \n",
    "    dfs(arr2d, 0, 0, seen, values)\n",
    "    \n",
    "    return values\n",
    "\n",
    "def dfs(matrix, row, col, seen, values):\n",
    "    \n",
    "    if row < 0 or col < 0 or row >= len(matrix) or col >= len(matrix[0]) or seen[row][col]:\n",
    "        return \n",
    "    \n",
    "    seen[row][col] = True\n",
    "    values.append(matrix[row][col])\n",
    "    \n",
    "    for i in range(len(directions)):\n",
    "        currentDir = directions[i]\n",
    "        dfs(matrix, row + currentDir[0], col + currentDir[1], seen, values)\n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "b9a42108",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5, 10, 15, 20, 19, 14, 9, 8, 13, 18, 17, 12, 7, 6, 11, 16]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr2d = [[1,2,3,4,5],\n",
    "         [6,7,8,9,10],\n",
    "        [11,12,13,14,15],\n",
    "        [16,17,18,19,20]]\n",
    "\n",
    "traversalDFS(arr2d)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e3c93c3b",
   "metadata": {},
   "source": [
    "# 23. BFS in 2d array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "408532ae",
   "metadata": {},
   "outputs": [],
   "source": [
    "def traversalBFS(arr2d):\n",
    "    rows, cols = len(arr2d), len(arr2d[0])\n",
    "    seen = [[False for x in range(cols)] for y in range(rows)]\n",
    "    values = []\n",
    "    queue = [[0,0]]\n",
    "    \n",
    "    while len(queue) > 0:\n",
    "        currentPos = queue.pop(0)\n",
    "        row = currentPos[0]\n",
    "        col = currentPos[1]\n",
    "        \n",
    "        if row < 0 or col < 0 or row >= len(arr2d) or col >= len(arr2d[0]) or seen[row][col]:\n",
    "            continue\n",
    "        \n",
    "        seen[row][col] = True\n",
    "        values.append(arr2d[row][col])\n",
    "        \n",
    "        for i in range(len(directions)):\n",
    "            currentDir = directions[i]\n",
    "            queue.append([row + currentDir[0], col + currentDir[1]])\n",
    "    return values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "4fac8ad6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 6, 3, 7, 11, 4, 8, 12, 16, 5, 9, 13, 17, 10, 14, 18, 15, 19, 20]"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "traversalBFS(arr2d)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4551de36",
   "metadata": {},
   "source": [
    "# 24. Number of islands\n",
    "\n",
    "https://leetcode.com/problems/number-of-islands/\n",
    "\n",
    "T --> O(MxN)\n",
    "\n",
    "S --> O(min(M,N))\n",
    "\n",
    "## BFS"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "081b0455",
   "metadata": {},
   "outputs": [],
   "source": [
    "directions = [[-1, 0], [0, 1], [1, 0], [0, -1]]\n",
    "\n",
    "def numIslands(grid):\n",
    "    \n",
    "    if len(grid) == 0:\n",
    "        return 0\n",
    "    \n",
    "    islandCount = 0\n",
    "    \n",
    "    for row in range(len(grid)):\n",
    "        for col in range(len(grid[0])):\n",
    "            if grid[row][col] == '1':\n",
    "                islandCount += 1\n",
    "                grid[row][col] = '0'\n",
    "                queue = []\n",
    "                queue.append([row, col])\n",
    "                while len(queue) > 0:\n",
    "                    currentPos = queue.pop(0)\n",
    "                    currentRow = currentPos[0]\n",
    "                    currentCol = currentPos[1]\n",
    "                    \n",
    "                    for i in range(len(directions)):\n",
    "                        currentDir = directions[i]\n",
    "                        nextRow = currentRow + currentDir[0]\n",
    "                        nextCol = currentCol + currentDir[1]\n",
    "                        if nextRow < 0 or nextRow >= len(grid) or nextCol < 0 or nextCol >= len(grid[0]):\n",
    "                            continue\n",
    "                            \n",
    "                        if grid[nextRow][nextCol] == '1':\n",
    "                            queue.append([nextRow, nextCol])\n",
    "                            grid[nextRow][nextCol] = '0'\n",
    "    return islandCount"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "7ec34863",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grid = [\n",
    "  [\"1\",\"1\",\"1\",\"1\",\"0\"],\n",
    "  [\"1\",\"1\",\"0\",\"1\",\"0\"],\n",
    "  [\"1\",\"1\",\"0\",\"0\",\"0\"],\n",
    "  [\"0\",\"0\",\"0\",\"0\",\"0\"]\n",
    "]\n",
    "\n",
    "numIslands(grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "8adf907f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grid = [\n",
    "    [\"1\",\"1\",\"0\",\"0\",\"0\"],\n",
    "    [\"1\",\"1\",\"0\",\"0\",\"0\"],\n",
    "    [\"0\",\"0\",\"1\",\"0\",\"0\"],\n",
    "    [\"0\",\"0\",\"0\",\"1\",\"1\"]]\n",
    "\n",
    "numIslands(grid)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fa8d13f0",
   "metadata": {},
   "source": [
    "## DFS"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "ddd77828",
   "metadata": {},
   "outputs": [],
   "source": [
    "def numIslands(grid):\n",
    "    \n",
    "    if len(grid) == 0:\n",
    "        return 0\n",
    "    \n",
    "    islandCount = 0\n",
    "    \n",
    "    for row in range(len(grid)):\n",
    "        for col in range(len(grid[0])):\n",
    "            if grid[row][col] == '1':\n",
    "                islandCount += 1\n",
    "                dfs(grid, row, col)\n",
    "    return islandCount\n",
    "\n",
    "def dfs(grid, currentRow, currentCol):\n",
    "    \n",
    "    if currentRow < 0 or currentRow >= len(grid) or currentCol < 0 \\\n",
    "    or currentCol >= len(grid[0]) or grid[currentRow][currentCol] == '0':\n",
    "        return\n",
    "    \n",
    "    if grid[currentRow][currentCol] == '1':\n",
    "        grid[currentRow][currentCol] = '0'\n",
    "        \n",
    "    \n",
    "    for i in range(len(directions)):\n",
    "        currentDir = directions[i]\n",
    "        nextRow = currentDir[0]\n",
    "        nextCol = currentDir[1]\n",
    "        dfs(grid, currentRow + nextRow, currentCol + nextCol)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "1dbeed24",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grid = [\n",
    "  [\"1\",\"1\",\"1\",\"1\",\"0\"],\n",
    "  [\"1\",\"1\",\"0\",\"1\",\"0\"],\n",
    "  [\"1\",\"1\",\"0\",\"0\",\"0\"],\n",
    "  [\"0\",\"0\",\"0\",\"0\",\"0\"]\n",
    "]\n",
    "\n",
    "numIslands(grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "e63500af",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grid = [\n",
    "    [\"1\",\"1\",\"0\",\"0\",\"0\"],\n",
    "    [\"1\",\"1\",\"0\",\"0\",\"0\"],\n",
    "    [\"0\",\"0\",\"1\",\"0\",\"0\"],\n",
    "    [\"0\",\"0\",\"0\",\"1\",\"1\"]]\n",
    "\n",
    "numIslands(grid)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ddd7df1b",
   "metadata": {},
   "source": [
    "# 25. Rotting Oranges\n",
    "\n",
    "https://leetcode.com/problems/rotting-oranges/\n",
    "\n",
    "T --> O(N)\n",
    "\n",
    "S --> O(N)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "0fa73484",
   "metadata": {},
   "outputs": [],
   "source": [
    "def orangesRotting(grid):\n",
    "    rows, cols = len(grid), len(grid[0])\n",
    "    freshOranges = 0\n",
    "    queue = []\n",
    "    \n",
    "    for row in range(rows):\n",
    "        for col in range(cols):\n",
    "            if grid[row][col] == 2:\n",
    "                queue.append([row, col])\n",
    "            elif grid[row][col] == 1:\n",
    "                freshOranges += 1\n",
    "    \n",
    "    queue.append([-1, -1])\n",
    "    \n",
    "    minutes_elapsed = -1\n",
    "    \n",
    "    directions = [[-1, 0], [0, 1], [1, 0], [0, -1]]\n",
    "    \n",
    "    while len(queue) > 0:\n",
    "        currentPos = queue.pop(0)\n",
    "        currentRow = currentPos[0]\n",
    "        currentCol = currentPos[1]\n",
    "        \n",
    "        if currentRow == -1:\n",
    "            minutes_elapsed += 1\n",
    "            if len(queue) > 0:\n",
    "                queue.append([-1, -1])\n",
    "        else:\n",
    "            for i in range(len(directions)):\n",
    "                currentDir = directions[i]\n",
    "                nextRow = currentRow + currentDir[0]\n",
    "                nextCol = currentCol + currentDir[1]\n",
    "                \n",
    "                if nextRow < 0 or nextCol < 0 or nextRow >= len(grid) or nextCol >= len(grid[0]):\n",
    "                    continue\n",
    "                \n",
    "                if grid[nextRow][nextCol] == 1:\n",
    "                    grid[nextRow][nextCol] = 2\n",
    "                    freshOranges -= 1\n",
    "                    queue.append([nextRow, nextCol])\n",
    "    \n",
    "    if freshOranges == 0:\n",
    "        return minutes_elapsed\n",
    "    else:\n",
    "        return -1\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "7bb47349",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grid = [[2,1,1],[1,1,0],[0,1,1]]\n",
    "\n",
    "orangesRotting(grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "aab3ec4d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grid = [[0,2]]\n",
    "orangesRotting(grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "9dbdab42",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-1"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grid = [[2,1,1],[0,1,1],[1,0,1]]\n",
    "orangesRotting(grid)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b3dcc80b",
   "metadata": {},
   "source": [
    "# 26. Walls and Gates\n",
    "\n",
    "https://leetcode.com/problems/walls-and-gates/\n",
    "\n",
    "T --> O(N)\n",
    "\n",
    "S --> O(N)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "id": "fbced635",
   "metadata": {},
   "outputs": [],
   "source": [
    "directions = [[-1, 0], [0, 1], [1, 0], [0, -1]]\n",
    "\n",
    "def wallsAndGates(matrix):\n",
    "    WALL = -1\n",
    "    GATE = 0\n",
    "    EMPTY = 2147483647\n",
    "    \n",
    "    for row in range(len(matrix)):\n",
    "        for col in range(len(matrix[0])):\n",
    "            if matrix[row][col] == GATE:\n",
    "                dfs(matrix, row, col, 0)\n",
    "    \n",
    "\n",
    "def dfs(matrix, row, col, current_step):\n",
    "    \n",
    "    if row < 0 or col < 0 or row >= len(matrix) or col >= len(matrix[0]) or matrix[row][col] < current_step:\n",
    "        return \n",
    "    \n",
    "    \n",
    "    if matrix[row][col] == -1:\n",
    "        return\n",
    "    \n",
    "    matrix[row][col] = current_step\n",
    "    \n",
    "    for i in range(len(directions)):\n",
    "        currentDir = directions[i]\n",
    "        dfs(matrix, row + currentDir[0], col + currentDir[1], current_step + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "id": "096cd35b",
   "metadata": {},
   "outputs": [],
   "source": [
    "rooms = [[2147483647,-1,0,2147483647],\n",
    "         [2147483647,2147483647,2147483647,-1],\n",
    "         [2147483647,-1,2147483647,-1],\n",
    "         [0,-1,2147483647,2147483647]]\n",
    "\n",
    "wallsAndGates(rooms)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "id": "b9cb58f2",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[3, -1, 0, 1], [2, 2, 1, -1], [1, -1, 2, -1], [0, -1, 3, 4]]"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rooms"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "df06dbdc",
   "metadata": {},
   "source": [
    "# 27. BFS in graphs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "id": "cf305583",
   "metadata": {},
   "outputs": [],
   "source": [
    "adjacencyList = [\n",
    "  [1, 3],       # 0\n",
    "  [0],          # 1\n",
    "  [3, 8],       # 2\n",
    "  [0, 2, 4, 5], # 3\n",
    "  [3, 6],       # 4\n",
    "  [3],          # 5\n",
    "  [4, 7],       # 6\n",
    "  [6],          # 7\n",
    "  [2]           # 8\n",
    "]\n",
    "\n",
    "def bfs_graph(adj_list):\n",
    "    seen = {}\n",
    "    result = []\n",
    "    queue = [0]\n",
    "    \n",
    "    while len(queue) > 0:\n",
    "        currNode = queue.pop(0)\n",
    "        result.append(currNode)\n",
    "        seen[currNode] = True\n",
    "        \n",
    "        connections = adj_list[currNode]\n",
    "        \n",
    "        for connection in connections:\n",
    "            if connection not in seen.keys():\n",
    "                queue.append(connection)\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "id": "56776014",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 3, 2, 4, 5, 8, 6, 7]"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bfs_graph(adjacencyList)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e33a143f",
   "metadata": {},
   "source": [
    "# 28. DFS in graphs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "id": "35ec4167",
   "metadata": {},
   "outputs": [],
   "source": [
    "def dfs_graph(currNode, adj_list, result, seen):\n",
    "    \n",
    "    result.append(currNode)\n",
    "    seen[currNode] = True\n",
    "    \n",
    "    connections = adj_list[currNode]\n",
    "    \n",
    "    for connection in connections:\n",
    "        if connection not in seen.keys():\n",
    "            dfs_graph(connection, adj_list, result, seen)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "id": "e87247de",
   "metadata": {},
   "outputs": [],
   "source": [
    "seen = {}\n",
    "result = []\n",
    "dfs_graph(0, adjacencyList, result, seen)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "id": "a2643569",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 3, 2, 8, 4, 6, 7, 5]"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "result"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "71f776f7",
   "metadata": {},
   "source": [
    "# 29. Time Needed to inform all employees\n",
    "\n",
    "https://leetcode.com/problems/time-needed-to-inform-all-employees/\n",
    "\n",
    "## DFS"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "6099cabd",
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 8\n",
    "headID = 4\n",
    "manager = [2,2,4,6,-1,4,4,5]\n",
    "informTime = [0,0,4,0,7,3,5,0]\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "def numOfMinutes(n, headID, manager, informTime):\n",
    "    \n",
    "    graph = defaultdict(list)\n",
    "    \n",
    "    for i in range(len(manager)):\n",
    "        graph[manager[i]].append(i)\n",
    "    \n",
    "    def dfs(u):\n",
    "        ans = 0\n",
    "        for v in graph[u]:\n",
    "            ans = max(dfs(v) + informTime[u], ans)\n",
    "        return ans\n",
    "    \n",
    "    return dfs(headID)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "id": "bac2905b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "numOfMinutes(n, headID, manager, informTime)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8bd26f70",
   "metadata": {},
   "source": [
    "## BFS"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "id": "c03e7ae5",
   "metadata": {},
   "outputs": [],
   "source": [
    "def numOfMinutes(n, headID, manager, informTime):\n",
    "    \n",
    "    graph = defaultdict(list)\n",
    "    \n",
    "    for i in range(len(manager)):\n",
    "        graph[manager[i]].append(i)\n",
    "        \n",
    "    result = 0\n",
    "    queue = [(headID, 0)]\n",
    "    \n",
    "    while len(queue) > 0:\n",
    "        employee, time = queue.pop(0)        \n",
    "        result = max(result, time)\n",
    "        \n",
    "        for subordinate in graph[employee]:\n",
    "            queue.append((subordinate, time + informTime[employee]))\n",
    "    \n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "fac56f70",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "numOfMinutes(n, headID, manager, informTime)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cb813726",
   "metadata": {},
   "source": [
    "# 30. Course schedule"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5e00ebcb",
   "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
}