11_facebook_mock_leetcode.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "230e5307",
   "metadata": {},
   "source": [
    "# 1. Check Completeness of a Binary Tree\n",
    "\n",
    "https://leetcode.com/problems/check-completeness-of-a-binary-tree/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "caeeba1c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def isCompleteTree(root):\n",
    "    \n",
    "    queue = [root]\n",
    "    prevNode = root\n",
    "    \n",
    "    while len(queue) > 0:\n",
    "        \n",
    "        currNode = queue.pop(0)\n",
    "        \n",
    "        if currNode is not None:\n",
    "            \n",
    "            if prevNode is None:\n",
    "                \n",
    "                return False\n",
    "            \n",
    "            queue.append(currNode.left)\n",
    "            queue.append(currNode.right)\n",
    "        \n",
    "        prevNode = currNode\n",
    "    \n",
    "    return True"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ef50ae47",
   "metadata": {},
   "source": [
    "# 2. Longest arithmatic subsequence\n",
    "\n",
    "https://leetcode.com/problems/longest-arithmetic-subsequence/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "87692ed9",
   "metadata": {},
   "outputs": [],
   "source": [
    "def longestArithSeqLength(nums):\n",
    "\n",
    "    dp = {}\n",
    "    for i in range(1,len(nums)):\n",
    "        for j in range(i):\n",
    "            dp[i,nums[i]-nums[j]] = dp.get((j,nums[i]-nums[j]), 1) + 1\n",
    "    return max(dp.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "aaf3911f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [20,1,15,3,10,5,8]\n",
    "\n",
    "longestArithSeqLength(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9d9c148d",
   "metadata": {},
   "source": [
    "# 3. Maximum Size Subarray Sum Equals k\n",
    "\n",
    "https://leetcode.com/problems/maximum-size-subarray-sum-equals-k/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "5845262c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def maxSubArrayLen(nums, k):\n",
    "    prefix_sum = 0\n",
    "    longest_subarray = 0\n",
    "    indices = {}\n",
    "\n",
    "    for i, num in enumerate(nums):\n",
    "        prefix_sum += num\n",
    "\n",
    "        if prefix_sum == k:\n",
    "            longest_subarray = i + 1\n",
    "\n",
    "        if prefix_sum - k in indices:\n",
    "            longest_subarray = max(longest_subarray, i - indices[prefix_sum - k])\n",
    "\n",
    "        if prefix_sum not in indices:\n",
    "            indices[prefix_sum] = i\n",
    "\n",
    "    return longest_subarray"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "d7671cf3",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [1,-1,5,-2,3]\n",
    "k = 3\n",
    "maxSubArrayLen(nums, k)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "97261246",
   "metadata": {},
   "source": [
    "# 4. Min depth of a binary tree\n",
    "\n",
    "\n",
    "https://leetcode.com/problems/minimum-depth-of-binary-tree/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "59dd388c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def minDepth(root):\n",
    "\n",
    "    if not root:\n",
    "        return 0\n",
    "\n",
    "    children  = [root.left, root.right]\n",
    "\n",
    "    if not any(children):\n",
    "        return 1\n",
    "\n",
    "    min_depth = float(\"inf\")\n",
    "\n",
    "    for c in children:\n",
    "        if c is not None:\n",
    "            min_depth = min(minDepth(c), min_depth)\n",
    "\n",
    "    return min_depth + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "3f6921a8",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = [1,2,3,3,3]\n",
    "\n",
    "a.index(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ed166c40",
   "metadata": {},
   "source": [
    "# 5. Randomly output the index of a given target number"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "4da06cfa",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "\n",
    "    def __init__(self, nums):\n",
    "        self.hashmap = defaultdict(list)\n",
    "        \n",
    "        for idx, num in enumerate(nums):\n",
    "            self.hashmap[num].append(idx)\n",
    "\n",
    "    def pick(self, target: int) -> int:\n",
    "        \n",
    "        return self.hashmap[target][random.randint(0,len(self.hashmap[target])-1)]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "16d093dd",
   "metadata": {},
   "source": [
    "# 6. Island Perimeter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "a89ae77c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def islandPerimeter(grid):\n",
    "    islandList = []\n",
    "\n",
    "    rows, cols = len(grid), len(grid[0])\n",
    "\n",
    "    directions = [[-1,0], [0,1], [1,0], [0,-1]]\n",
    "\n",
    "    for row in range(len(grid)):\n",
    "        for col in range(len(grid[0])):\n",
    "            if grid[row][col] == 1:\n",
    "                islandList.append([row,col])\n",
    "                grid[row][col] = 0\n",
    "                # BFS\n",
    "                queue = []\n",
    "                queue.append([row, col])\n",
    "                while len(queue):\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",
    "                            islandList.append([nextRow, nextCol])\n",
    "                            grid[nextRow][nextCol] = 0\n",
    "\n",
    "    totalIslands = len(islandList)\n",
    "    totalPerimeter = 0\n",
    "\n",
    "    for i in range(len(islandList)):\n",
    "        perimeter = 4\n",
    "        islandCoord = islandList[i]\n",
    "        islandRow = islandCoord[0]\n",
    "        islandCol = islandCoord[1]\n",
    "\n",
    "        numSurrounding = 0\n",
    "\n",
    "        for i in range(len(directions)):\n",
    "            currentDir = directions[i]\n",
    "            nextRow = islandRow + currentDir[0]\n",
    "            nextCol = islandCol + currentDir[1]\n",
    "            \n",
    "            if nextRow < 0 or nextRow >= len(grid) or nextCol < 0 or nextCol >= len(grid[0]):\n",
    "                continue\n",
    "\n",
    "            if [nextRow, nextCol] in islandList:\n",
    "                perimeter -= 1\n",
    "\n",
    "        totalPerimeter += perimeter\n",
    "\n",
    "    return totalPerimeter\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "cc0f2cee",
   "metadata": {},
   "outputs": [],
   "source": [
    "def islandPerimeter(grid) -> int:\n",
    "    rows = len(grid)\n",
    "    cols = len(grid[0])\n",
    "\n",
    "    result = 0\n",
    "\n",
    "    for r in range(rows):\n",
    "        for c in range(cols):\n",
    "            if grid[r][c] == 1:\n",
    "                result += 4\n",
    "\n",
    "                if r > 0 and grid[r-1][c] == 1:\n",
    "                    result -= 2\n",
    "\n",
    "                if c > 0 and grid[r][c-1] == 1:\n",
    "                    result -= 2\n",
    "\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "243b72ad",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "16"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]\n",
    "\n",
    "islandPerimeter(grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "f93f32d8",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grid = [[1,0]]\n",
    "islandPerimeter(grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "e7322403",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grid = [[1]]\n",
    "islandPerimeter(grid)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5937f6dd",
   "metadata": {},
   "source": [
    "# 7. Reorder List\n",
    "\n",
    "Overview\n",
    "\n",
    "Find a middle node of the linked list. If there are two middle nodes, return the second middle node. Example: for the list 1->2->3->4->5->6, the middle element is 4.\n",
    "\n",
    "Once a middle node has been found, reverse the second part of the list. Example: convert 1->2->3->4->5->6 into 1->2->3->4 and 6->5->4.\n",
    "\n",
    "Now merge the two sorted lists. Example: merge 1->2->3->4 and 6->5->4 into 1->6->2->5->3->4."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "4684fe16",
   "metadata": {},
   "outputs": [],
   "source": [
    "def reorderList(head):\n",
    "    if not head:\n",
    "        return\n",
    "    \n",
    "    tortoise = head\n",
    "    hare = head\n",
    "    # find the middle of linked list [Problem 876]\n",
    "    # in 1->2->3->4->5->6 find 4 \n",
    "    while hare is not None and hare.next is not None:\n",
    "        tortoise = tortoise.next\n",
    "        hare = hare.next.next\n",
    "        \n",
    "    prev, curr = None, tortoise\n",
    "    \n",
    "    # reverse the second part of the list [Problem 206]\n",
    "    # convert 1->2->3->4->5->6 into 1->2->3->4 and 6->5->4\n",
    "    # reverse the second half in-place\n",
    "    \n",
    "    while curr is not None:\n",
    "        curr.next, prev, curr = prev, curr, curr.next      \n",
    "        \n",
    "    # merge two sorted linked lists [Problem 21]\n",
    "    # merge 1->2->3->4 and 6->5->4 into 1->6->2->5->3->4\n",
    "    \n",
    "    first, second = head, prev\n",
    "    \n",
    "    while second.next is not None:\n",
    "        first.next, first = second, first.next\n",
    "        second.next, second = first, second.next"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "31c355a7",
   "metadata": {},
   "source": [
    "# 8. Clone Graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "f1ee7ff7",
   "metadata": {},
   "outputs": [],
   "source": [
    "def cloneGraph(self, node: 'Node') -> 'Node':\n",
    "    if not node:\n",
    "        return node\n",
    "\n",
    "    visited = {}\n",
    "\n",
    "    queue = [node]\n",
    "\n",
    "    visited[node] = Node(node.val, [])\n",
    "\n",
    "    while len(queue) > 0:\n",
    "        currNode = queue.pop(0)\n",
    "\n",
    "        for neighbor in currNode.neighbors:\n",
    "            if neighbor not in visited:\n",
    "                visited[neighbor] = Node(neighbor.val, [])\n",
    "                queue.append(neighbor)\n",
    "            visited[currNode].neighbors.append(visited[neighbor])\n",
    "\n",
    "    return visited[node]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c8bf9ba6",
   "metadata": {},
   "source": [
    "# 9. Longest Substring with At Most K Distinct Characters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "222c9f04",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "def lengthOfLongestSubstringKDistinct(s, k):\n",
    "    n = len(s)\n",
    "\n",
    "    if n * k == 0:\n",
    "        return 0\n",
    "\n",
    "    left, right = 0,0\n",
    "\n",
    "    hashmap = defaultdict()\n",
    "\n",
    "    max_len = 1\n",
    "\n",
    "    while right < len(s):\n",
    "        hashmap[s[right]] = right\n",
    "        right += 1\n",
    "\n",
    "        if len(hashmap) == k + 1:\n",
    "            del_idx = min(hashmap.values())\n",
    "\n",
    "            del hashmap[s[del_idx]]\n",
    "\n",
    "            left = del_idx + 1\n",
    "\n",
    "        max_len = max(max_len, right - left)\n",
    "\n",
    "    return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "e41e38ee",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"eceba\"\n",
    "k = 2\n",
    "\n",
    "lengthOfLongestSubstringKDistinct(s,k)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "10b7afc6",
   "metadata": {},
   "source": [
    "# 10. Intersection of two arrays"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "0ad5e014",
   "metadata": {},
   "outputs": [],
   "source": [
    "def intersect(nums1, nums2):\n",
    "        \n",
    "    nums1.sort()\n",
    "    nums2.sort()\n",
    "\n",
    "    i = 0\n",
    "    j = 0\n",
    "\n",
    "    ans = []\n",
    "\n",
    "    while i < len(nums1) and j < len(nums2):\n",
    "        if nums1[i] < nums2[j]:\n",
    "            i += 1\n",
    "        elif nums1[i] > nums2[j]:\n",
    "            j += 1\n",
    "        else:\n",
    "            ans.append(nums1[i])\n",
    "            i += 1\n",
    "            j += 1\n",
    "\n",
    "\n",
    "    return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "be476104",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 2]"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = [1,2,2,1]\n",
    "b = [2,2]\n",
    "intersect(a,b)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e1434b35",
   "metadata": {},
   "source": [
    "# 11. Array shuffling"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "1b9e2bce",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4 c\n",
      "5 o\n",
      "6 d\n",
      "7 e\n",
      "0 l\n",
      "2 e\n",
      "1 e\n",
      "3 t\n"
     ]
    }
   ],
   "source": [
    "s = \"codeleet\"\n",
    "indices = [4,5,6,7,0,2,1,3]\n",
    "\n",
    "for i, s in zip(indices, s):\n",
    "    print(i,s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8c781981",
   "metadata": {},
   "source": [
    "# 12. Buddy Strings"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "c2d42fc3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def buddyStrings(s, goal):\n",
    "    if len(s) != len(goal):\n",
    "        return False\n",
    "\n",
    "    if s == goal:\n",
    "        seen = set()\n",
    "        for a in s:\n",
    "            if a in seen:\n",
    "                return True\n",
    "            seen.add(a)\n",
    "        return False\n",
    "\n",
    "    pairs = []\n",
    "\n",
    "    for a, b in zip(s, goal):\n",
    "        if a != b:\n",
    "            pairs.append((a,b))\n",
    "        if len(pairs) >= 3:\n",
    "            return False\n",
    "    return len(pairs) == 2 and pairs[0] == pairs[1][::-1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "f2188c83",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"ab\"\n",
    "goal = \"ba\"\n",
    "\n",
    "buddyStrings(s, goal)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f886a5ef",
   "metadata": {},
   "source": [
    "# 13. Diagonal sort\n",
    "\n",
    "Time complexity: O(N x M x log(min(N,M))\n",
    "\n",
    "Pushing at heap has log O"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "b3e6df9e",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "import heapq\n",
    "\n",
    "def diagonalSort(mat):\n",
    "    rows, cols = len(mat), len(mat[0])\n",
    "\n",
    "    diagonals = defaultdict(list)\n",
    "\n",
    "    for row in range(rows):\n",
    "        for col in range(cols):\n",
    "            diagonals[row - col].append(mat[row][col])\n",
    "\n",
    "\n",
    "    for diagonal in diagonals.values():\n",
    "        heapq.heapify(diagonal)\n",
    "\n",
    "\n",
    "    for row in range(rows):\n",
    "        for col in range(cols):\n",
    "            value = heapq.heappop(diagonals[row-col])\n",
    "            mat[row][col] = value\n",
    "\n",
    "    return mat\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "440ce0ec",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 1, 1, 1], [1, 2, 2, 2], [1, 2, 3, 3]]"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]\n",
    "diagonalSort(mat)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "09da3a7d",
   "metadata": {},
   "source": [
    "# 14. Sum BST"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "460a72cb",
   "metadata": {},
   "outputs": [],
   "source": [
    "def rangeSumBST(root, low, high) -> int:\n",
    "        \n",
    "    if not root:\n",
    "        return 0\n",
    "\n",
    "    queue = [root]\n",
    "\n",
    "    result = 0\n",
    "\n",
    "    while len(queue) > 0:\n",
    "        currNode = queue.pop(0)\n",
    "\n",
    "        if currNode.val >= low and currNode.val <= high:\n",
    "            result += 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",
    "    return result"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "98d48447",
   "metadata": {},
   "source": [
    "# 15. Nested List Weight Sum II"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "d2b47a18",
   "metadata": {},
   "outputs": [],
   "source": [
    "#class NestedInteger:\n",
    "#    def __init__(self, value=None):\n",
    "#        \"\"\"\n",
    "#        If value is not specified, initializes an empty list.\n",
    "#        Otherwise initializes a single integer equal to value.\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def isInteger(self):\n",
    "#        \"\"\"\n",
    "#        @return True if this NestedInteger holds a single integer, rather than a nested list.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def add(self, elem):\n",
    "#        \"\"\"\n",
    "#        Set this NestedInteger to hold a nested list and adds a nested integer elem to it.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def setInteger(self, value):\n",
    "#        \"\"\"\n",
    "#        Set this NestedInteger to hold a single integer equal to value.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def getInteger(self):\n",
    "#        \"\"\"\n",
    "#        @return the single integer that this NestedInteger holds, if it holds a single integer\n",
    "#        Return None if this NestedInteger holds a nested list\n",
    "#        :rtype int\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def getList(self):\n",
    "#        \"\"\"\n",
    "#        @return the nested list that this NestedInteger holds, if it holds a nested list\n",
    "#        Return None if this NestedInteger holds a single integer\n",
    "#        :rtype List[NestedInteger]\n",
    "#        \"\"\"\n",
    "\n",
    "def depthSumInverse(nestedList) -> int:\n",
    "        \n",
    "    total_sum = 0\n",
    "    level_sum = 0\n",
    "\n",
    "    while len(nestedList) > 0:\n",
    "        next_level_list = []\n",
    "        for x in nestedList:\n",
    "            if x.isInteger():\n",
    "                level_sum += x.getInteger()\n",
    "            else:\n",
    "                for y in x.getList():\n",
    "                    next_level_list.append(y)\n",
    "        total_sum += level_sum\n",
    "        nestedList = next_level_list\n",
    "\n",
    "    return total_sum"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "820a4408",
   "metadata": {},
   "source": [
    "# 16. BST closest to the target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "c90e9832",
   "metadata": {},
   "outputs": [],
   "source": [
    "def closestValue(root, target):\n",
    "    if not root:\n",
    "        return None\n",
    "\n",
    "    if root.left is None and root.right is None:\n",
    "        return root.val\n",
    "\n",
    "    result = float('inf')\n",
    "\n",
    "    queue = [root]\n",
    "\n",
    "    hash_map = {}\n",
    "\n",
    "    while len(queue) > 0:\n",
    "        currNode = queue.pop(0)\n",
    "        result = min(result, abs(currNode.val - target))\n",
    "        hash_map[currNode.val] = result\n",
    "\n",
    "        if currNode.left is not None:\n",
    "            queue.append(currNode.left)\n",
    "\n",
    "        if currNode.right is not None:\n",
    "            queue.append(currNode.right)\n",
    "\n",
    "\n",
    "    return list(hash_map.keys())[list(hash_map.values()).index(min(hash_map.values()))]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e6748a85",
   "metadata": {},
   "source": [
    "# 17. Reverse vowels of a string"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "6b42d0d1",
   "metadata": {},
   "outputs": [],
   "source": [
    "def reverseVowels(s):\n",
    "    left = 0\n",
    "    right = len(s) - 1\n",
    "\n",
    "    list_s = [i for i in s]\n",
    "\n",
    "    vowels = ['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']\n",
    "\n",
    "    while left < right:\n",
    "        if list_s[left] in vowels and list_s[right] in vowels:\n",
    "            list_s[left], list_s[right] = list_s[right], list_s[left]\n",
    "            left += 1\n",
    "            right -= 1\n",
    "        elif list_s[left] not in vowels:\n",
    "            left += 1\n",
    "        else:\n",
    "            right -= 1\n",
    "\n",
    "    return \"\".join(list_s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "09cdffaa",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'leotcede'"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = 'leetcode'\n",
    "reverseVowels(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "de04be00",
   "metadata": {},
   "source": [
    "# 18. Find Largest Value in Each Tree Row"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "17cb4cbc",
   "metadata": {},
   "outputs": [],
   "source": [
    "def largestValues(root):\n",
    "    result = []\n",
    "\n",
    "\n",
    "\n",
    "    def dfs(node, level):\n",
    "        if not node:\n",
    "            return\n",
    "\n",
    "        if len(result) == level:\n",
    "            result.append(node.val)\n",
    "        else:\n",
    "            result[level] = max(result[level], node.val)\n",
    "\n",
    "        dfs(node.left, level + 1)\n",
    "        dfs(node.right, level + 1)\n",
    "\n",
    "    dfs(root, 0)\n",
    "\n",
    "    return result\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f3fd9d84",
   "metadata": {},
   "source": [
    "# 19. Add Two Numbers in linkedlist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "d15e5ae2",
   "metadata": {},
   "outputs": [],
   "source": [
    "def addTwoNumbers(l1, l2):\n",
    "        \n",
    "    dummyHead = ListNode(0)\n",
    "\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",
    "\n",
    "        columnSum = l1val + l2val + carry\n",
    "        carry = columnSum // 10\n",
    "        newNode = ListNode(columnSum % 10)\n",
    "        curr.next = newNode\n",
    "        curr = newNode\n",
    "        l1 = l1.next if l1 else None\n",
    "        l2 = l2.next if l2 else None\n",
    "    return dummyHead.next"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e2de4120",
   "metadata": {},
   "source": [
    "# 20. Intersection of three arrays"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "ca264d7e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def arraysIntersection(arr1, arr2, arr3):\n",
    "        \n",
    "    result = []\n",
    "\n",
    "    for i in arr1:\n",
    "        if i in arr2 and i in arr3:\n",
    "            result.append(i)\n",
    "\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "b406b20e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 5]"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr1 = [1,2,3,4,5] \n",
    "arr2 = [1,2,5,7,9]\n",
    "arr3 = [1,3,4,5,8]\n",
    "\n",
    "arraysIntersection(arr1, arr2, arr3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "47c0e92b",
   "metadata": {},
   "source": [
    "# 21. Next Greater element\n",
    "\n",
    "https://leetcode.com/problems/next-greater-element-i/\n",
    "\n",
    "**Read the logic of stacks**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "fad8c7f8",
   "metadata": {},
   "outputs": [],
   "source": [
    "def nextGreaterElement(nums1, nums2):\n",
    "        \n",
    "    stack = []\n",
    "\n",
    "    hashmap = {}\n",
    "\n",
    "    result = []\n",
    "\n",
    "    for i in range(len(nums2)):\n",
    "        while len(stack) > 0 and nums2[i] > stack[-1]:\n",
    "            hashmap[stack.pop()] = nums2[i]\n",
    "        stack.append(nums2[i])\n",
    "\n",
    "    while len(stack) != 0:\n",
    "        hashmap[stack.pop()] = -1\n",
    "\n",
    "    for i in range(len(nums1)):\n",
    "        result.append(hashmap[nums1[i]])\n",
    "\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "47068de4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[-1, 3, -1]"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums1 = [4,1,2]\n",
    "nums2 = [1,3,4,2]\n",
    "\n",
    "nextGreaterElement(nums1, nums2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9b23cc2e",
   "metadata": {},
   "source": [
    "# 22. Long pressed name"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "15aa50a8",
   "metadata": {},
   "outputs": [],
   "source": [
    "def isLongPressedName(name, typed):\n",
    "    i = 0\n",
    "    for j in range(len(typed)):\n",
    "        \n",
    "        \n",
    "        if i < len(name) and name[i] == typed[j]:\n",
    "            i += 1\n",
    "        elif j == 0 or typed[j] != typed[j - 1]:\n",
    "            return False\n",
    "    return i == len(name)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "a4bdee44",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "name = \"alex\"\n",
    "typed = \"aaleex\"\n",
    "isLongPressedName(name, typed)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "454a3d30",
   "metadata": {},
   "source": [
    "# 23. Sorted squares"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "id": "5b165619",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sortedSquares(nums):\n",
    "    n = len(nums)\n",
    "\n",
    "    result = [0]*n\n",
    "\n",
    "    left = 0\n",
    "    right = n - 1\n",
    "\n",
    "    for i in range(n-1, -1, -1):\n",
    "        if abs(nums[left]) < abs(nums[right]):\n",
    "            square = nums[right]\n",
    "            right -= 1\n",
    "        else:\n",
    "            square = nums[left]\n",
    "            left += 1\n",
    "\n",
    "        result[i] = square * square\n",
    "\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "id": "5301bcd7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 9, 16, 100]"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [-4,-1,0,3,10]\n",
    "sortedSquares(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3edc47ea",
   "metadata": {},
   "source": [
    "# 24. Custom sort string"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "id": "02460aee",
   "metadata": {},
   "outputs": [],
   "source": [
    "def customSortString(order, s):\n",
    "        \n",
    "    count = Counter(s)\n",
    "\n",
    "    result = []\n",
    "\n",
    "    for c in order:\n",
    "        result.append(c * count[c])\n",
    "        count[c] = 0\n",
    "\n",
    "    for c in count:\n",
    "        result.append(c * count[c])\n",
    "\n",
    "    return \"\".join(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "id": "b17bbc97",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'cbad'"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "order = \"cba\"\n",
    "s = \"abcd\"\n",
    "customSortString(order, s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a941365b",
   "metadata": {},
   "source": [
    "# 25. Range sum query"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "73541490",
   "metadata": {},
   "outputs": [],
   "source": [
    "class NumArray:\n",
    "\n",
    "    def __init__(self, nums):\n",
    "        self.accu = [0]\n",
    "        for num in nums: \n",
    "            self.accu += self.accu[-1] + num,\n",
    "        \n",
    "        \n",
    "\n",
    "    def sumRange(self, left: int, right: int) -> int:\n",
    "        return self.accu[right + 1] - self.accu[left]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "020a55ac",
   "metadata": {},
   "source": [
    "# 26. Read4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "481fbc01",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def read(self, buf, n):\n",
    "        \"\"\"\n",
    "        :type buf: Destination buffer (List[str])\n",
    "        :type n: Number of characters to read (int)\n",
    "        :rtype: The number of actual characters read (int)\n",
    "        \"\"\"\n",
    "        copied_chars = 0\n",
    "        read_chars = 4\n",
    "        buf4 = [''] * 4\n",
    "        \n",
    "        while copied_chars < n and read_chars == 4:\n",
    "            read_chars = read4(buf4)\n",
    "            \n",
    "            for i in range(read_chars):\n",
    "                if copied_chars == n:\n",
    "                    return copied_chars\n",
    "                buf[copied_chars] = buf4[i]\n",
    "                copied_chars += 1\n",
    "        return copied_chars"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8c608a74",
   "metadata": {},
   "source": [
    "# 27. Roman to Integer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "25f3bacc",
   "metadata": {},
   "outputs": [],
   "source": [
    "def romanToInt(s):\n",
    "        \n",
    "    romanIntMap = {\n",
    "        'I': 1,\n",
    "        'V': 5,\n",
    "        'X': 10,\n",
    "        'L': 50,\n",
    "        'C': 100,\n",
    "        'D': 500,\n",
    "        'M': 1000\n",
    "    }\n",
    "\n",
    "    result = 0\n",
    "\n",
    "    left = 0\n",
    "\n",
    "    while left < len(s):\n",
    "        if left + 1 < len(s) and romanIntMap[s[left]] < romanIntMap[s[left+1]]:\n",
    "            result += romanIntMap[s[left+1]] - romanIntMap[s[left]]\n",
    "            left += 2\n",
    "        else:\n",
    "            result += romanIntMap[s[left]]\n",
    "            left += 1\n",
    "\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "0a901b40",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "romanToInt('VI')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5bdbf1cb",
   "metadata": {},
   "source": [
    "# 28. Palindrome"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "0d42278e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def isPalindrome(s: str) -> bool:\n",
    "\n",
    "    if not s:\n",
    "        return False\n",
    "\n",
    "    left = 0\n",
    "    right = len(s) - 1\n",
    "\n",
    "    while left < right:\n",
    "        while left < right and not s[left].isalnum():\n",
    "            left += 1\n",
    "        while left < right and not s[right].isalnum():\n",
    "            right -= 1\n",
    "        if s[left].lower() != s[right].lower():\n",
    "            return False\n",
    "        left += 1\n",
    "        right -= 1\n",
    "\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "3ba470e4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"A man, a plan, a canal: Panama\"\n",
    "\n",
    "isPalindrome(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0fd5586a",
   "metadata": {},
   "source": [
    "# 29. Almost Palindrome"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "7e9fb398",
   "metadata": {},
   "outputs": [],
   "source": [
    "def validPalindrome(s: str) -> bool:\n",
    "        \n",
    "    def isValid(s, i, j):\n",
    "        while i < j:\n",
    "            if s[i] != s[j]:\n",
    "                return False\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        return True\n",
    "\n",
    "    left = 0\n",
    "    right = len(s) - 1\n",
    "\n",
    "    while left < right:\n",
    "        if s[left] != s[right]:\n",
    "            return isValid(s, left + 1, right) or isValid(s, left, right - 1)\n",
    "\n",
    "        left += 1\n",
    "        right -= 1\n",
    "\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "39cb91bc",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "validPalindrome('aba')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7cae8488",
   "metadata": {},
   "source": [
    "# 30. Lowest common ancestor"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "3cc220dc",
   "metadata": {},
   "outputs": [],
   "source": [
    "def lowestCommonAncestor(p, q):\n",
    "    p1, p2 = p,q\n",
    "    \n",
    "    while p1 != p2:\n",
    "        if p1.parent is not None:\n",
    "            p1 = p1.parent\n",
    "        else:\n",
    "            p1 = q\n",
    "        \n",
    "        if p2.parent is not None:\n",
    "            p2 = p2.parent\n",
    "        else:\n",
    "            p2 = p\n",
    "    return p1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "64ac2811",
   "metadata": {},
   "source": [
    "# 31. Binary tree vertical order traversal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "28e6aea8",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "def verticalOrder(root):\n",
    "    result = defaultdict(list)\n",
    "    queue = []\n",
    "    queue.append([root, 0])\n",
    "\n",
    "    while len(queue) > 0:\n",
    "        currNode = queue.pop(0)\n",
    "        node = currNode[0]\n",
    "        column = currNode[1]\n",
    "\n",
    "        if node is not None:\n",
    "            result[column].append(node.val)\n",
    "            queue.append([node.left, column - 1])\n",
    "            queue.append([node.right, column + 1])\n",
    "\n",
    "\n",
    "    return [result[x] for x in sorted(result.keys())]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4ff551e1",
   "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
}