6_get_well_prepared_facebook_leetcode.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "311c3611",
   "metadata": {},
   "source": [
    "# 1. Longest Substring without repeating characters\n",
    "\n",
    "https://leetcode.com/explore/interview/card/facebook/5/array-and-strings/3008/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 157,
   "id": "b65f7360",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "import collections\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "27138974",
   "metadata": {},
   "outputs": [],
   "source": [
    "def lengthOfLongestSubstring(s):\n",
    "    if len(s) <= 1:\n",
    "        return 1\n",
    "    \n",
    "    longest = 0\n",
    "    left = 0\n",
    "    seenChars = {}\n",
    "    \n",
    "    for right in range(len(s)):\n",
    "        currentChar = s[right]\n",
    "        prevseenChar = -1\n",
    "        if currentChar in seenChars.keys():\n",
    "            prevseenChar = seenChars[currentChar]\n",
    "        \n",
    "        if left <= prevseenChar:\n",
    "            left = prevseenChar + 1\n",
    "        \n",
    "        seenChars[currentChar] = right\n",
    "        longest = max(longest, right - left + 1)\n",
    "    return longest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "b8e1784c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"pwwkew\"\n",
    "lengthOfLongestSubstring(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "4cff0cc2",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-12"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = ['-', '12']\n",
    "\n",
    "int(\"\".join(a))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "83d06775",
   "metadata": {},
   "source": [
    "# 2. String to Integer\n",
    "\n",
    "https://leetcode.com/explore/interview/card/facebook/5/array-and-strings/3009/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "b92d6a64",
   "metadata": {},
   "outputs": [],
   "source": [
    "def myAtoi(s):\n",
    "    \n",
    "    sign = 1 \n",
    "    result = 0\n",
    "    index = 0\n",
    "    n = len(s)\n",
    "\n",
    "    INT_MAX = pow(2,31) - 1 \n",
    "    INT_MIN = -pow(2,31)\n",
    "\n",
    "    # Discard all spaces from the beginning of the input string.\n",
    "    while index < n and s[index] == ' ':\n",
    "        index += 1\n",
    "\n",
    "    # sign = +1, if it's positive number, otherwise sign = -1. \n",
    "    if index < n and s[index] == '+':\n",
    "        sign = 1\n",
    "        index += 1\n",
    "    elif index < n and s[index] == '-':\n",
    "        sign = -1\n",
    "        index += 1\n",
    "\n",
    "    # Traverse next digits of input and stop if it is not a digit. \n",
    "    # End of string is also non-digit character.\n",
    "    while index < n and s[index].isdigit():\n",
    "        digit = int(s[index])\n",
    "\n",
    "        # Check overflow and underflow conditions. \n",
    "        if ((result > INT_MAX // 10) or (result == INT_MAX // 10 and digit > INT_MAX % 10)):\n",
    "            # If integer overflowed return 2^31-1, otherwise if underflowed return -2^31.    \n",
    "            return INT_MAX if sign == 1 else INT_MIN\n",
    "\n",
    "        # Append current digit to the result.\n",
    "        result = 10 * result + digit\n",
    "        index += 1\n",
    "\n",
    "    # We have formed a valid number without any overflow/underflow.\n",
    "    # Return it after multiplying it with its sign.\n",
    "    return sign * result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "2c0eb623",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "42"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"42\"\n",
    "myAtoi(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "a1277296",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4193"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"4193 with words\"\n",
    "myAtoi(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "222f59e0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"words and 987\"\n",
    "myAtoi(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "19360ca5",
   "metadata": {},
   "source": [
    "# 3. Roman to Integer\n",
    "\n",
    "https://leetcode.com/explore/interview/card/facebook/5/array-and-strings/3010/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "615812d3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def romanToInt(s):\n",
    "    values = {\n",
    "    \"I\": 1,\n",
    "    \"V\": 5,\n",
    "    \"X\": 10,\n",
    "    \"L\": 50,\n",
    "    \"C\": 100,\n",
    "    \"D\": 500,\n",
    "    \"M\": 1000,\n",
    "}\n",
    "\n",
    "    total = 0\n",
    "    i = 0\n",
    "    \n",
    "    while i < len(s):\n",
    "        if i + 1 < len(s) and values[s[i]] < values[s[i+1]]:\n",
    "            total += values[s[i+1]] - values[s[i]]\n",
    "            i += 2\n",
    "        else:\n",
    "            total += values[s[i]]\n",
    "            i += 1\n",
    "    return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "e6f9675d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "58"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"LVIII\"\n",
    "romanToInt(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "e63423ee",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1994"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"MCMXCIV\"\n",
    "romanToInt(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8ae4d19e",
   "metadata": {},
   "source": [
    "# 4. Remove Duplicates from Sorted Array\n",
    "\n",
    "https://leetcode.com/explore/interview/card/facebook/5/array-and-strings/3011/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "id": "00a3fd8b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def removeDuplicates(nums):\n",
    "    if len(nums) == 0:\n",
    "        return 0\n",
    "    \n",
    "    i = 0\n",
    "    \n",
    "    for j in range(1, len(nums)):\n",
    "        if nums[j] != nums[i]:\n",
    "            i += 1\n",
    "            nums[i] = nums[j]\n",
    "    \n",
    "    return i + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "id": "9912fb4f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 71,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [0,0,1,1,1,2,2,3,3,4]\n",
    "removeDuplicates(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f8728cde",
   "metadata": {},
   "source": [
    "# 5. Group Anagrams\n",
    "\n",
    "https://leetcode.com/explore/interview/card/facebook/5/array-and-strings/3014/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 135,
   "id": "5b0b405c",
   "metadata": {},
   "outputs": [],
   "source": [
    "import collections\n",
    "# O(NK)\n",
    "def groupAnagrams(strs):\n",
    "    ans = collections.defaultdict(list)\n",
    "    \n",
    "    for s in strs:\n",
    "        count = [0] * 26\n",
    "        for c in s:\n",
    "            count[ord(c) - ord('a')] += 1\n",
    "        ans[tuple(count)].append(s)\n",
    "    return ans.values()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 136,
   "id": "ab14281c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "dict_values([[['a', 'e', 't'], ['a', 'e', 't'], ['a', 'e', 't']], [['a', 'n', 't'], ['a', 'n', 't']], [['a', 'b', 't']]])"
      ]
     },
     "execution_count": 136,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[\"eat\",\"tea\",\"tan\",\"ate\",\"nat\",\"bat\"]\n",
    "groupAnagrams(strs)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4cc0b193",
   "metadata": {},
   "source": [
    "# 6. Add Binary\n",
    "\n",
    "https://leetcode.com/explore/interview/card/facebook/5/array-and-strings/263/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 143,
   "id": "0f4673e2",
   "metadata": {},
   "outputs": [],
   "source": [
    "def addBinary(a, b):\n",
    "    return '{0:b}'.format(int(a, 2) + int(b, 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 145,
   "id": "5ce99065",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'100'"
      ]
     },
     "execution_count": 145,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "addBinary('11', '1')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "280bc515",
   "metadata": {},
   "source": [
    "# 7. Valid Palindrome\n",
    "\n",
    "https://leetcode.com/explore/interview/card/facebook/5/array-and-strings/288/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 146,
   "id": "2bbc5112",
   "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",
    "        if s[left].lower() != s[right].lower():\n",
    "            return False\n",
    "        left += 1\n",
    "        right -= 1\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 149,
   "id": "e58b428d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 149,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"A man, a plan, a canal: Panama\"\n",
    "isPalindrome(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8a61112f",
   "metadata": {},
   "source": [
    "# 8. Valid Palindrome II\n",
    "\n",
    "https://leetcode.com/explore/interview/card/facebook/5/array-and-strings/289/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 150,
   "id": "30a8c4ad",
   "metadata": {},
   "outputs": [],
   "source": [
    "def validPalindrome(s):\n",
    "    def checkPalindrome(s, i, j):\n",
    "        while i < j:\n",
    "            if s[i] != s[j]:\n",
    "                return False\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        return True\n",
    "    \n",
    "    i = 0\n",
    "    j = len(s) - 1\n",
    "    \n",
    "    while i < j:\n",
    "        if s[i] != s[j]:\n",
    "            return checkPalindrome(s, i+1, j) or checkPalindrome(s, i, j-1)\n",
    "        i += 1\n",
    "        j -= 1\n",
    "    \n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 153,
   "id": "c95ca40e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 153,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"abca\"\n",
    "validPalindrome(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5cd0b281",
   "metadata": {},
   "source": [
    "# 9. Merge Sorted Array\n",
    "\n",
    "https://leetcode.com/explore/interview/card/facebook/5/array-and-strings/309/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "7702297b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def merge(nums1, m, nums2, n):\n",
    "    nums1_copy = nums1[:m]\n",
    "    \n",
    "    p1 = 0\n",
    "    p2 = 0\n",
    "    \n",
    "    for i in range(m+n):\n",
    "        if p2 >= n or (p1 < m and nums1_copy[p1] <= nums2[p2]):\n",
    "            nums1[i] = nums1_copy[p1]\n",
    "            p1 += 1\n",
    "        else:\n",
    "            nums1[i] = nums2[p2]\n",
    "            p2 += 1\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "dac20136",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 2, 3, 5, 6]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums1 = [1,2,3,0,0,0]\n",
    "m = 3\n",
    "nums2 = [2,5,6]\n",
    "n = 3\n",
    "\n",
    "merge(nums1, m, nums2, n)\n",
    "\n",
    "nums1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0b845349",
   "metadata": {},
   "source": [
    "# 10. One edit distance\n",
    "\n",
    "https://leetcode.com/explore/interview/card/facebook/5/array-and-strings/3015/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "6dcb03b7",
   "metadata": {},
   "outputs": [],
   "source": [
    "def isOneEditDistance(s, t):\n",
    "    ns = len(s)\n",
    "    nt = len(t)\n",
    "    \n",
    "    if ns > nt:\n",
    "        return isOneEditDistance(t, s)\n",
    "    \n",
    "    # The strings are NOT one edit away distance  \n",
    "    # if the length diff is more than 1.\n",
    "    if nt - ns > 1:\n",
    "        return False\n",
    "    \n",
    "    for i in range(ns):\n",
    "        if s[i] != t[i]:\n",
    "            # if strings have the same length\n",
    "            if ns == nt:\n",
    "                return s[i+1:] == t[i+1:]\n",
    "            # if strings have different length\n",
    "            else:\n",
    "                return s[i:] == t[i+1:]\n",
    "            \n",
    "    # If there is no diffs on ns distance\n",
    "    # the strings are one edit away only if\n",
    "    # t has one more character. \n",
    "    return ns + 1 == nt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "26f99ed7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"ab\"\n",
    "t = \"acb\"\n",
    "isOneEditDistance(s, t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "ae04bc38",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"\"\n",
    "t = \"\"\n",
    "isOneEditDistance(s, t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "84c6b5f7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"abcd\"\n",
    "t = \"abc\"\n",
    "isOneEditDistance(s, t)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fb01216d",
   "metadata": {},
   "source": [
    "# 11. Product of Array Except Self\n",
    "\n",
    "https://leetcode.com/explore/interview/card/facebook/5/array-and-strings/3016/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "f2d5b3ca",
   "metadata": {},
   "outputs": [],
   "source": [
    "# [1,2,4,5]\n",
    "def productExceptSelf(nums):\n",
    "        \n",
    "    # The length of the input array \n",
    "    length = len(nums)\n",
    "\n",
    "    # The left and right arrays as described in the algorithm\n",
    "    L, R, answer = [0]*length, [0]*length, [0]*length\n",
    "\n",
    "    # L[i] contains the product of all the elements to the left\n",
    "    # Note: for the element at index '0', there are no elements to the left,\n",
    "    # so the L[0] would be 1\n",
    "    L[0] = 1\n",
    "    for i in range(1, length):\n",
    "\n",
    "        # L[i - 1] already contains the product of elements to the left of 'i - 1'\n",
    "        # Simply multiplying it with nums[i - 1] would give the product of all \n",
    "        # elements to the left of index 'i'\n",
    "        L[i] = nums[i - 1] * L[i - 1]\n",
    "\n",
    "    # R[i] contains the product of all the elements to the right\n",
    "    # Note: for the element at index 'length - 1', there are no elements to the right,\n",
    "    # so the R[length - 1] would be 1\n",
    "    R[length - 1] = 1\n",
    "    for i in reversed(range(length - 1)):\n",
    "\n",
    "        # R[i + 1] already contains the product of elements to the right of 'i + 1'\n",
    "        # Simply multiplying it with nums[i + 1] would give the product of all \n",
    "        # elements to the right of index 'i'\n",
    "        R[i] = nums[i + 1] * R[i + 1]\n",
    "\n",
    "    # Constructing the answer array\n",
    "    for i in range(length):\n",
    "        # For the first element, R[i] would be product except self\n",
    "        # For the last element of the array, product except self would be L[i]\n",
    "        # Else, multiple product of all elements to the left and to the right\n",
    "        answer[i] = L[i] * R[i]\n",
    "\n",
    "    return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "dcd82d0a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[24, 12, 8, 6]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [1,2,3,4]\n",
    "productExceptSelf(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "e7dc3c76",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 0, 9, 0, 0]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [-1,1,0,-3,3]\n",
    "productExceptSelf(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b532a402",
   "metadata": {},
   "source": [
    "# 12. Move Zeroes\n",
    "\n",
    "https://leetcode.com/explore/interview/card/facebook/5/array-and-strings/262/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "87db3f08",
   "metadata": {},
   "outputs": [],
   "source": [
    "# not in place\n",
    "def moveZeroes(nums):\n",
    "    result = []\n",
    "    \n",
    "    countZeroes = 0\n",
    "    \n",
    "    for i in range(len(nums)):\n",
    "        if nums[i] == 0:\n",
    "            countZeroes += 1\n",
    "        else:\n",
    "            result.append(nums[i])\n",
    "    \n",
    "    for i in range(countZeroes):\n",
    "        result.append(0)\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "57975f24",
   "metadata": {},
   "outputs": [],
   "source": [
    "# in place\n",
    "def moveZeroes(nums):\n",
    "    countZeroes = 0\n",
    "    \n",
    "    left = 0\n",
    "    \n",
    "    while left < len(nums) - 1:\n",
    "        if nums[left] == 0:\n",
    "            nums.pop(left)\n",
    "            countZeroes += 1\n",
    "        # we are not moving left if 0 because, if there are successive 0s, then \n",
    "        # we will miss them for shfting of left\n",
    "        else:\n",
    "            left += 1\n",
    "    \n",
    "    for i in range(countZeroes):\n",
    "        nums.append(0)\n",
    "    \n",
    "    return nums\n",
    "    \n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "335c5942",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 3, 12, 0, 0]"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [0,1,0,3,12]\n",
    "moveZeroes(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "ca0a621d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 0, 0]"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [0,0,1]\n",
    "moveZeroes(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f5b511c7",
   "metadata": {},
   "source": [
    "# 13. SubArray sum equals k\n",
    "\n",
    "https://leetcode.com/explore/interview/card/facebook/5/array-and-strings/3019/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "id": "fe5f29c2",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "def subarraySum(nums,k):\n",
    "    n = len(nums)\n",
    "        \n",
    "    count = 0\n",
    "    dict_cumsum = defaultdict(int) # hashtable for storing the cumsum we have seen so far\n",
    "    curr_sum = 0 # for cumulative sum at each index\n",
    "    for i in range(0,n): # upto the length of the nums array\n",
    "        curr_sum += nums[i] # cumulative sum in each index\n",
    "        if curr_sum == k: # if current cumsum is equal to target \n",
    "            count += 1\n",
    "        # if curr_sum - k in the dict, then let's say \n",
    "        # curr_sum - k = some_val. so, curr_sum = k + some_val, means \n",
    "        # if the some_val is already in the dictionary, then there \n",
    "        # exists a subarray whose sum is k that has lead us to this\n",
    "        # curr_sum. How lead us? by some_val + k = curr_sum\n",
    "        # now if some_val occurs more than 1 time, means you have\n",
    "        # that number of subarray to consider to the count\n",
    "        # So you need to add that number of occurence of curr_sum - k\n",
    "        # to the count\n",
    "        # think about this with example nums list in the solution \n",
    "        # [3,4,7,2,-3,1,4,2] and also with [3,4,7,2,-3,1,4,2, 1]\n",
    "        if curr_sum - k in dict_cumsum: \n",
    "            count += dict_cumsum[curr_sum - k]\n",
    "        # add the curr_sum entry to the hashtable\n",
    "        dict_cumsum[curr_sum] += 1\n",
    "    #print(dict_cumsum)\n",
    "    return count \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "id": "e0351ff0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 78,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [3,4,7,2,1,4,2]\n",
    "k = 7\n",
    "subarraySum(nums, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "id": "006015a3",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 79,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [1,2,3]\n",
    "k = 3\n",
    "subarraySum(nums, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "id": "261b43dc",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 80,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [1,1,1]\n",
    "k = 2\n",
    "subarraySum(nums, k)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fdc9a82e",
   "metadata": {},
   "source": [
    "# 14. Merge two Sorted linked list\n",
    "\n",
    "https://leetcode.com/explore/interview/card/facebook/6/linked-list/301/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "id": "e26841d0",
   "metadata": {},
   "outputs": [],
   "source": [
    "def mergeTwoLists(list1,list2):\n",
    "    if list1 is None:\n",
    "        return list2\n",
    "    elif list2 is None:\n",
    "        return list1\n",
    "    elif list1.val < list2.val:\n",
    "        list1.next = self.mergeTwoLists(list1.next, list2)\n",
    "        return list1\n",
    "    else:\n",
    "        list2.next = self.mergeTwoLists(list1, list2.next)\n",
    "        return list2\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "02866adb",
   "metadata": {},
   "source": [
    "# 15. Validate Binary Search tree\n",
    "\n",
    "https://leetcode.com/explore/interview/card/facebook/52/trees-and-graphs/266/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "id": "e09a1bc6",
   "metadata": {},
   "outputs": [],
   "source": [
    "def isValidBST(root):\n",
    "    def validate(node, low=-math.inf, high=math.inf):\n",
    "        if not node:\n",
    "            return True\n",
    "        if node.val <= low or node.val >= high:\n",
    "            return False\n",
    "        return validate(node.right, node.val, high) and validate(node.left, low, node.val)\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7b225eeb",
   "metadata": {},
   "source": [
    "# 16. Flatten Binary tree to Linked List\n",
    "\n",
    "https://leetcode.com/explore/interview/card/facebook/52/trees-and-graphs/322/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "id": "83403d7e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def flatten(root):\n",
    "    if not node:\n",
    "        return None\n",
    "    \n",
    "    if not node.left and not node.right:\n",
    "        return node\n",
    "    \n",
    "    leftTail = flatten(node.left)\n",
    "    \n",
    "    rightTail = flatten(node.right)\n",
    "    \n",
    "    if leftTail:\n",
    "        leftTail.right = node.right\n",
    "        node.right = node.left\n",
    "        node.left = None\n",
    "    \n",
    "    return rightTail if rightTail else leftTail"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ffeda561",
   "metadata": {},
   "source": [
    "# 17. Binary tree right side view\n",
    "\n",
    "https://leetcode.com/explore/interview/card/facebook/52/trees-and-graphs/3023/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "352940a8",
   "metadata": {},
   "outputs": [],
   "source": [
    "def rightSideView(root):\n",
    "    result = []\n",
    "    level = 0\n",
    "    return traversePreOrder(root, level, result)\n",
    "\n",
    "def traversePreOrder(node, level, result):\n",
    "    if not node:\n",
    "        return\n",
    "    \n",
    "    if level >= len(result):\n",
    "        result.append(node.val)\n",
    "    \n",
    "    if node.right is not None:\n",
    "        traversePreOrder(node.right, level + 1, result)\n",
    "        \n",
    "    if node.left is not None:\n",
    "        traversePreOrder(node.left, level + 1, result)\n",
    "    \n",
    "    return data"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5c090d94",
   "metadata": {},
   "source": [
    "# 18. Number of Islands\n",
    "\n",
    "https://leetcode.com/explore/interview/card/facebook/52/trees-and-graphs/274/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "85bcba3a",
   "metadata": {},
   "outputs": [],
   "source": [
    "def numIslands(grid):\n",
    "    islandCount = 0\n",
    "    directions = [[-1, 0], [0, 1], [1, 0], [0, -1]]\n",
    "    \n",
    "    if len(grid) == 0:\n",
    "        return 0\n",
    "    \n",
    "    for i in range(len(grid)):\n",
    "        for j in range(len(grid[0])):\n",
    "            if grid[i][j] == '1':\n",
    "                islandCount += 1\n",
    "                grid[i][j] = '0'\n",
    "                queue = []\n",
    "                queue.append([i, j])\n",
    "                while len(queue) > 0:\n",
    "                    currNode = queue.pop(0)\n",
    "                    currRow = currNode[0]\n",
    "                    currCol = currNode[1]\n",
    "                    \n",
    "                    for i in range(len(directions)):\n",
    "                        direction = directions[i]\n",
    "                        nextRow = currRow + direction[0]\n",
    "                        nextCol = currCol + direction[1]\n",
    "                        \n",
    "                        if nextRow < 0 or nextRow >= len(grid) or nextCol < 0 or nextCol >= len(grid[0]):\n",
    "                            continue\n",
    "                        \n",
    "                        if grid[nextRow][nextCol] == '1':\n",
    "                            queue.append([nextRow, nextCol])\n",
    "                            grid[nextRow][nextCol] = '0'\n",
    "    return islandCount"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "0c630e92",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 9,
     "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": "cabd1af2",
   "metadata": {},
   "source": [
    "# 19. Binary tree paths\n",
    "\n",
    "https://leetcode.com/explore/interview/card/facebook/52/trees-and-graphs/280/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "de3d5b64",
   "metadata": {},
   "outputs": [],
   "source": [
    "def binaryTreePaths(root):\n",
    "    if not root:\n",
    "        return []\n",
    "\n",
    "    paths = []\n",
    "    stack = [(root, str(root.val))]\n",
    "\n",
    "    while len(stack) > 0:\n",
    "        currNode, currPath = stack.pop(0)\n",
    "        if not currNode.left and not currNode.right:\n",
    "            paths.append(currPath)\n",
    "        if currNode.left:\n",
    "            stack.append((currNode.left, currPath + '->' + str(currNode.left.val)))\n",
    "        if currNode.right:\n",
    "            stack.append((currNode.right, currPath + '->' + str(currNode.right.val)))\n",
    "\n",
    "    return paths\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "51a7765a",
   "metadata": {},
   "source": [
    "# 20. Diameter of a Binary Tree\n",
    "\n",
    "https://leetcode.com/explore/interview/card/facebook/52/trees-and-graphs/291/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "831384e9",
   "metadata": {},
   "outputs": [],
   "source": [
    "def diameterOfBinaryTree(root):\n",
    "    diameter = 0\n",
    "    \n",
    "    def longest_path(node):\n",
    "        if not node:\n",
    "            return 0\n",
    "        \n",
    "        nonlocal diameter\n",
    "        left_path = longest_path(node.left)\n",
    "        right_path = longest_path(node.right)\n",
    "        \n",
    "        diameter = max(diameter, left_path + right_path)\n",
    "        \n",
    "        return max(left_path, right_path) + 1\n",
    "    \n",
    "    longest_path(root)\n",
    "    return diameter"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fadae20e",
   "metadata": {},
   "source": [
    "# 21. Binary Tree Vertical Order Traversal\n",
    "\n",
    "https://leetcode.com/explore/interview/card/facebook/52/trees-and-graphs/298/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "6ca9f96d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def verticalOrder(root):\n",
    "    result = defaultdict(list)\n",
    "    queue = []\n",
    "    queue.append([root, 0])\n",
    "\n",
    "    while len(queue) > 0:\n",
    "        currNode = queue.pop(0)\n",
    "        node = currNode[0]\n",
    "        column = currNode[1]\n",
    "\n",
    "        if node is not None:\n",
    "            result[column].append(node.val)\n",
    "            queue.append([node.left, column - 1])\n",
    "            queue.append([node.right, column + 1])\n",
    "\n",
    "\n",
    "    return [result[x] for x in sorted(result.keys())]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "da0cb0d3",
   "metadata": {},
   "source": [
    "\n",
    "# 22. Letter Combinations of a Phone Number\n",
    "\n",
    "https://leetcode.com/explore/interview/card/facebook/53/recursion-3/267/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "00025120",
   "metadata": {},
   "outputs": [],
   "source": [
    "def letterCombinations(digits):\n",
    "    \n",
    "    letter_map = {2: ['a', 'b', 'c'],\n",
    "                  3: ['d', 'e', 'f'],\n",
    "                  4: ['g', 'h', 'i'],\n",
    "                  5: ['j', 'k', 'l'],\n",
    "                  6: ['m', 'n', 'o'],\n",
    "                  7: ['p', 'q', 'r', 's'],\n",
    "                  8: ['t', 'u', 'v'],\n",
    "                  9: ['w', 'x', 'y', 'z']}\n",
    "    \n",
    "    \n",
    "    queue = letter_map[int(digits[0])]\n",
    "    \n",
    "    for i in range(1,len(digits)):\n",
    "        s = len(queue)\n",
    "        while s:\n",
    "            currLetter = queue.pop(0)\n",
    "            for j in letter_map[int(digits[i])]:\n",
    "                queue.append(currLetter + j)\n",
    "            s -= 1\n",
    "    return queue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "34742c32",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "digits = \"23\"\n",
    "\n",
    "letterCombinations(digits)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "0d517295",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['dg', 'dh', 'di', 'eg', 'eh', 'ei', 'fg', 'fh', 'fi']"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "digits = \"34\"\n",
    "\n",
    "letterCombinations(digits)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dc505f5f",
   "metadata": {},
   "source": [
    "# 23. Permutations\n",
    "\n",
    "https://leetcode.com/explore/interview/card/facebook/53/recursion-3/292/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "67ba101f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def permute(nums):\n",
    "    result = []\n",
    "    dfs(nums, [], result)\n",
    "    return result\n",
    "\n",
    "def dfs(nums, path, result):\n",
    "    if not nums:\n",
    "        result.append(path)\n",
    "    for i in range(len(nums)):\n",
    "        #path.append(nums[i])\n",
    "        # whenever it reaches the end, nums[:i] + nums[i+1:] return None. So it goes into if block\n",
    "        dfs(nums[:i] + nums[i+1:], path + [nums[i]], result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "b08a0d92",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [1,2,3]\n",
    "permute(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "522770b5",
   "metadata": {},
   "source": [
    "# 24. Permutations 2\n",
    "\n",
    "https://leetcode.com/explore/interview/card/facebook/53/recursion-3/293/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "761c581e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def permuteUnique(nums):\n",
    "    result = []\n",
    "    dfs(nums, [], result)\n",
    "    return result\n",
    "\n",
    "def dfs(nums, path, result):\n",
    "    if not nums and path not in result:\n",
    "        result.append(path)\n",
    "    \n",
    "    for i in range(len(nums)):\n",
    "        dfs(nums[:i] + nums[i+1:], path + [nums[i]], result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "39284e32",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 1, 2], [1, 2, 1], [2, 1, 1]]"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [1,1,2]\n",
    "permuteUnique(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e94bdf89",
   "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
}