leetcode.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "leetcode.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/Erickrus/leetcode/blob/master/leetcode.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "QnkifvS4Y7MF",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title leetcode\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "PK0J8c2-sR_Z",
        "colab_type": "code",
        "outputId": "797de330-84c9-46a8-8ff2-842bc4b8ede1",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 53
        }
      },
      "source": [
        "#@title 1. Two Sum\n",
        "# https://leetcode.com/problems/two-sum/description/\n",
        "\n",
        "class Solution:\n",
        "  def twoSum(self, nums, target):\n",
        "    \"\"\"\n",
        "    :type nums: List[int]\n",
        "    :type target: int\n",
        "    :rtype: List[int]\n",
        "    \"\"\"\n",
        "    for i in range(len(nums)):\n",
        "      for j in range(i, len(nums)):\n",
        "        if i != j and nums[i]+nums[j]==target:\n",
        "          return [i, j]\n",
        "    return None\n",
        "\n",
        "class Solution:\n",
        "  def twoSum(self, nums, target):\n",
        "    another = {}\n",
        "    for i in range(len(nums)):\n",
        "      another[target-nums[i]] = i\n",
        "    for i in range(len(nums)):\n",
        "      if nums[i] in another.keys() and i != another[nums[i]]:\n",
        "        return [i, another[nums[i]]]\n",
        "    return None\n",
        "Solution().twoSum([3,2,4], 6)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "{3: 0, 4: 1, 2: 2}\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[0, 0]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 4
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "xo_AZ1v8K-Ar",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title 2. Add Two Numbers\n",
        "# https://leetcode.com/problems/add-two-numbers/description/\n",
        "\n",
        "# Definition for singly-linked list.\n",
        "class ListNode:\n",
        "  def __init__(self, x):\n",
        "    self.val = x\n",
        "    self.next = None\n",
        "\n",
        "class Solution:\n",
        "  #def toStr(self, l):\n",
        "  #  vals = []\n",
        "  #  currNode = l\n",
        "  #  while currNode != None:\n",
        "  #    vals.append(str(currNode.val))\n",
        "  #    currNode = currNode.next\n",
        "  #  return \"(\" + \" -> \".join(vals) +\")\"\n",
        "    \n",
        "  def getNum(self, l):\n",
        "    if l == None:\n",
        "      return 0\n",
        "    \n",
        "    vals = []\n",
        "    currNode = l\n",
        "    while currNode != None:\n",
        "      vals.append(currNode.val)\n",
        "      currNode = currNode.next\n",
        "    res = 0\n",
        "    for n in reversed(vals):\n",
        "      res = res * 10 + n\n",
        "    return res\n",
        "\n",
        "  def getList(self, n):\n",
        "    t = str(n)\n",
        "    prevNode = None\n",
        "    rootNode = None\n",
        "    for i in reversed(range(len(t))):\n",
        "      currNode = ListNode(int(t[i]))\n",
        "      if rootNode == None:\n",
        "        rootNode = currNode\n",
        "      if prevNode != None:\n",
        "        prevNode.next = currNode\n",
        "      prevNode = currNode\n",
        "    return rootNode\n",
        "\n",
        "  def addTwoNumbers(self, l1, l2):\n",
        "    \"\"\"\n",
        "    :type l1: ListNode\n",
        "    :type l2: ListNode\n",
        "    :rtype: ListNode\n",
        "    \"\"\"\n",
        "    return self.getList(self.getNum(l1) +self.getNum(l2))\n",
        "  \n",
        "\n",
        "        "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "7OjiUeiRxGVL",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title 3. Longest Substring Without Repeating Characters\n",
        "# https://leetcode.com/problems/longest-substring-without-repeating-characters/\n",
        "\n",
        "class Solution:\n",
        "  def lengthOfLongestSubstring(self, s):\n",
        "    \"\"\"\n",
        "    :type s: str\n",
        "    :rtype: int\n",
        "    \"\"\"\n",
        "    if s == None or len(s) ==0:\n",
        "      return 0\n",
        "    longestLen, sub = 1, s[0:1]\n",
        "    for i in range(1, len(s)):\n",
        "      p = sub.find(s[i])\n",
        "      if p >=0:\n",
        "        sub = s[i-len(sub)+p+1:i] + s[i]\n",
        "      else:\n",
        "        sub += s[i]\n",
        "      longestLen = max(len(sub), longestLen)\n",
        "    return longestLen\n",
        "        \n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "GOm2IQRyj_da",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@ 4. Median of Two Sorted Arrays\n",
        "# https://leetcode.com/problems/median-of-two-sorted-arrays/description/\n",
        "\n",
        "class Solution:\n",
        "    def findMedianSortedArrays(self, nums1, nums2):\n",
        "        \"\"\"\n",
        "        :type nums1: List[int]\n",
        "        :type nums2: List[int]\n",
        "        :rtype: float\n",
        "        \"\"\"\n",
        "        allNums = []\n",
        "        if nums1 != None:\n",
        "            allNums.extend(nums1)\n",
        "        if nums2 != None:\n",
        "            allNums.extend(nums2)\n",
        "            \n",
        "        allNums = sorted(allNums)\n",
        "        \n",
        "        lenAllNum = len(allNums)\n",
        "        if lenAllNum == 0:\n",
        "            return 0\n",
        "        \n",
        "        if lenAllNum % 2 == 1:\n",
        "            return allNums[lenAllNum//2]\n",
        "        else:\n",
        "            return (allNums[lenAllNum//2-1] + allNums[lenAllNum//2])/2\n",
        "        "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "NnxAsXelkjs2",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title 5. Longest Palindromic Substring\n",
        "# https://leetcode.com/problems/longest-palindromic-substring/description/\n",
        "\n",
        "class Solution:\n",
        "  def getPalindrome(self, s, sLen):\n",
        "    if sLen == 1:\n",
        "      return sLen\n",
        "    if s == s[::-1]:\n",
        "      return sLen\n",
        "    else:\n",
        "      return -1\n",
        "    \n",
        "  def longestPalindrome(self, s):\n",
        "    if s == s[::-1]:\n",
        "      return s\n",
        "    iLongestPalindrome = 0\n",
        "    maxLongestPalindrome = \"\"\n",
        "    \n",
        "    sLen = len(s)\n",
        "    for i in range(sLen):\n",
        "      left, right = i, i\n",
        "      \n",
        "      while left>=0 and right<len(s):\n",
        "        subLen = right+1 - left\n",
        "        dist = s[left:right+1]\n",
        "        iPalindrome = self.getPalindrome(dist, subLen)\n",
        "        if iPalindrome <0:\n",
        "          break\n",
        "        if iPalindrome > iLongestPalindrome:\n",
        "          maxLongestPalindrome = dist\n",
        "          iLongestPalindrome = iPalindrome\n",
        "        left -=1\n",
        "        right +=1\n",
        "    for i in range(1, sLen+1):\n",
        "      left, right =i-1, i+1\n",
        "      while left>=0 and right<len(s)+1:\n",
        "        subLen = right - left\n",
        "        dist = s[left:right]\n",
        "        iPalindrome = self.getPalindrome(dist, subLen)\n",
        "        if iPalindrome <0:\n",
        "          break\n",
        "        if iPalindrome > iLongestPalindrome:\n",
        "          maxLongestPalindrome = dist\n",
        "          iLongestPalindrome = iPalindrome\n",
        "        left -=1\n",
        "        right +=1\n",
        "    return maxLongestPalindrome\n",
        "        \n",
        "\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "FLuh2vG1juYZ",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title 6. ZigZag Conversion\n",
        "# https://leetcode.com/problems/zigzag-conversion/description/\n",
        "class Solution(object):\n",
        "    def zigzag(self, i, numRows):\n",
        "        d, m = divmod(i, (numRows*2-2))\n",
        "        x = d * (numRows-1)\n",
        "        \n",
        "        if m < numRows:\n",
        "            y = m\n",
        "        else:\n",
        "            x += m - numRows + 1\n",
        "            y = numRows*2 - m - 2\n",
        "        return x, y\n",
        "            \n",
        "        \n",
        "    def convert(self, s, numRows):\n",
        "        if numRows<=1:\n",
        "            return s\n",
        "        zigzagArr = []\n",
        "        for i in range(len(s)):\n",
        "            x, y= self.zigzag(i, numRows)\n",
        "            #print(x,y)\n",
        "            zigzagArr.append([x, y, s[i]])\n",
        "        \n",
        "        zigzagArr.sort(key=lambda li: (li[1], li[0]))\n",
        "        #print(zigzagArr)\n",
        "        result = \"\"\n",
        "        for i in range(len(zigzagArr)):\n",
        "            result += zigzagArr[i][2]\n",
        "        #print(result)\n",
        "        return result"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2_KvnYjNjToV",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title 7. Reverse Integer\n",
        "# https://leetcode.com/problems/reverse-integer/description/\n",
        "class Solution:\n",
        "    def reverse(self, x):\n",
        "        sign = 1\n",
        "        if x<0:\n",
        "            sign = -1\n",
        "            x = sign*x\n",
        "        \n",
        "        num = []\n",
        "        while True:\n",
        "            d, n = divmod(x, 10)\n",
        "            if d == 0 and n == 0:\n",
        "                break\n",
        "            num.append(str(n))\n",
        "\n",
        "            x = x // 10\n",
        "        \n",
        "        try:\n",
        "            result = int(\"\".join(num))*sign\n",
        "            if result >= -2147483648 and result <= 2147483647:\n",
        "                return result\n",
        "            else:\n",
        "                return 0\n",
        "        except:\n",
        "            return 0"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "86YJExGOO9WD",
        "colab_type": "code",
        "outputId": "5f846b43-ba40-436a-8653-6727e5c12148",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 107
        }
      },
      "source": [
        "#@title 8. String to Integer (atoi)\n",
        "# https://leetcode.com/problems/string-to-integer-atoi/description/\n",
        "class Solution:\n",
        "  def myAtoi(self, str):\n",
        "    INT_MAX, INT_MIN = 2**31 -1, -1 *2**31\n",
        "    digits, signs, signSet = \"0123456789\", \"+-\", False\n",
        "    resSign, res, i =  1, 0, 0\n",
        "    s = str.strip()\n",
        "    for i in range(len(s)):\n",
        "      if s[i] in digits:\n",
        "        signSet = True\n",
        "        res = res*10 + int(s[i])\n",
        "      elif s[i] in signs:\n",
        "        if signSet:\n",
        "          break\n",
        "        if s[i] == \"-\":\n",
        "          resSign = -1\n",
        "          signSet = True\n",
        "        if s[i] == \"+\":\n",
        "          resSign = 1\n",
        "          signSet = True\n",
        "      else:\n",
        "        break\n",
        "    res = resSign * res\n",
        "    if res > INT_MAX:\n",
        "      return INT_MAX\n",
        "    if res < INT_MIN:\n",
        "      return INT_MIN\n",
        "    \n",
        "    return res\n"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "42\n",
            "-42\n",
            "4193\n",
            "0\n",
            "-2147483648\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "u6qWNQJfo07O",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@ 9. Palindrome Number\n",
        "# https://leetcode.com/problems/palindrome-number/description/\n",
        "class Solution:\n",
        "  def isPalindrome(self, x):\n",
        "    \"\"\"\n",
        "    :type x: int\n",
        "    :rtype: bool\n",
        "    \"\"\"\n",
        "    s = str(x)\n",
        "    return s == s[::-1]"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "VtlpP0-1qGhD",
        "colab_type": "code",
        "outputId": "37ef1e63-4a05-4dc1-c298-40c2e784442b",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 53
        }
      },
      "source": [
        "#@title 11. Container With Most Water\n",
        "# https://leetcode.com/problems/container-with-most-water/description/\n",
        "# O(n^2) solution doesnt work\n",
        "class Solution:\n",
        "  def maxArea(self, height):\n",
        "    I,J=0,0\n",
        "    heightLen = len(height)\n",
        "    maxAreaVal = (height[heightLen-1] - height[0]) * (heightLen-1)\n",
        "    for i in range(heightLen-1):\n",
        "      for j in range(i+1, heightLen):\n",
        "        area = min(height[i], height[j]) * (j-i)\n",
        "        if area> maxAreaVal:\n",
        "            maxAreaVal = area\n",
        "            I = i\n",
        "            J = j\n",
        "            \n",
        "    print(I,J,maxAreaVal)\n",
        "    return maxAreaVal\n",
        "\"\"\"\n",
        "# O(n) solution works\n",
        "class Solution:\n",
        "  def maxArea(self, height):\n",
        "    i, j = 0, len(height) - 1\n",
        "    water = 0\n",
        "    while i < j:\n",
        "      water = max(water, (j - i) * min(height[i], height[j]))\n",
        "      if height[i] < height[j]:\n",
        "        i += 1\n",
        "      else:\n",
        "        j -= 1\n",
        "    return water\n",
        "\"\"\"\n",
        "Solution().maxArea([28,342,418,485,719,670,878,752,662,994,654,504,929,660,424,855,922,744,600,229,728,33,371,863,561,772,271,178,455,449,426,835,143,845,321,214,867,199,967,881,193,973,386,122,633,810,330,907,906,282,136,986,315,860,849,229,632,473,759,87,922,185,922,418,382,243,632,250,795,599,131,988,924,869,463,558,680,145,465,938,427,954,925,94,814,126,323,798,599,434,885,874,620,159,292,354,755,924,956,550,876,88,890,800,309,705,358,989,850,176,280,629,130,205,724,296,331,399,94,283,186,331,157,806,490,801,512,597,725,469,499,601,909,390,754,218,447,112,560,298,640,840,279,122,397,355,418,80,755,864,363,293,195,872,451,38,673,963,635,751,432,487,352,341,229,458,912,676,923,472,326,563,312,606,686,709,313,456,789,420,321,505,713,868,377,164,258,403,128,246,154,912,733,858,606,962,317,518,990,240,990,317,803,302,275,841,363,588,650,504,9,323,9,74,191,387,239,450,790,367,48,944,279,781,802,885,743,471,755,85,711,745,402,867,399,29,708,762,970,710,267,331,33,276,405,577,15,644,379,157,363,427,453,995,208,608,232,303,79,988,388,791,733,143,658,133,524,718,247,846,429,514,529,814,143,935,743,510,931,122,668,647,901,473,642,461,81,874,764,513,214,505,304,948,0,314,433,876,384,680,75,165,547,604,980,42,891,75,552,823,198,572,822,451,46,816,913,479,42,29,992,257,886,648,557,238,962,990,115,699,22,190,864,921,794,196,315,686,272,868,861,822,792,35,273,190,851,186,670,893,568,662,150,454,311,59,693,625,49,808,324,424,350,189,697,496,737,13,534,9,881,747,831,25,782,457,216,985,643,886,879,211,900,381,18,211,441,711,837,842,871,513,618,573,702,316,69,440,329,956,801,562,703,633,587,486,90,803,471,85,41,702,649,942,436,19,505,877,730,342,71,953,856,690,526,910,6,947,702,335,903,504,249,607,489,836,445,931,992,268,368,33,971,369,327,407,388,833,636,470,527,59,423,735,749,301,646,107,249,700,794,504,556,43,111,397,232,908,328,224,177,49,609,500,418,937,259,159,770,247,629,297,306,405,33,408,706,31,867,955,83,662,460,640,57,923,37,289,832,718,865,361,119,475,213,537,412,472,48,534,71,678,183,377,83,568,137,141,599,5,449,35,19,261,675,76,184,64,366,368,134,583,81,253,58,294,143,822,118,191,356,189,221,892,919,656,460,56,798,412,61,247,447,80,508,474,509,44,538,227,765,673,810,846,278,869,493,421,43,611,613,752,153,834,644,72,491,456,128,641,868,542,888,315,974,748,141,483,144,32,710,909,705,873,108,983,94,601,757,137,564,370,241,69,556,885,141,47,694,622,688,562,516,928,230,490,28,371,326,173,403,388,82,460,613,542,796,707,495,553,197,412,275,438,481,831,676,623,231,370,597,271,284,113,200,514,955,228,238,633,753,993,374,188,806,987,730,602,695,226,507,892,638,782,330,471,965,358,94,196,728,43,468,365,508,20,879,464,600,469,449,354,463,823,542,621,811,624,223,506,850,82,750,840,216,432,312,181,791,758,730,871,802,550,236,310,570,468,126,522,289,576,228,104,751,122,725,562,747,300,420,949,382,170,790,950,603,454,132,746,564,214,969,366,764,206,29,686,26,507,208,315,435,789,420,187,911,145,101,658,446,522,608,180,692,750,131,647,556,615,393,120,181,363,839,945,921,220,983,299,727,543,614,515,332,386,54,244,884,155,254,682,29,214,862,722,964,345,721,520,960,467,993,141,182,832,438,455,52,421,754,131,317,720,646,649,107,52,245,343,208,500,25,589,714,239,311,31,585,385,903,897,852,896,391,386,728,181,841,780,955,595,264,272,315,262,921,774,315,167,117,875,19,494,464,733,86,128,116,671,513,20,920,717,916,663,103,997,845,944,129,800,891,393,72,558,656,345,333,971,512,802,846,883,649,662,617,735,790,733,406,655,105,678,372,374,342,827,371,187,123,500,339,14,246,411,573,902,108,258,225,973,60,423,856,709,85,473,444,876,559,202,531,16,233,256,390,575,83,761,114,559,614,453,573,860,216,498,114,324,756,339,649,169,762,506,230,199,979,27,427,890,581,311,259,814,567,649,389,2,763,855,561,377,660,487,589,228,337,703,905,446,42,554,615,156,60,197,707,392,576,135,282,158,446,541,324,365,543,66,367,306,921,281,35,582,768,624,810,457,327,715,903,721,270,870,229,682,68,936,74,996,423,709,154,221,250,479,586,145,545,306,451,818,587,486,400,707,462,563,164,789,630,420,862,252,290,443,935,358,732,9,355,155,718,861,729,321,692,315,466,237,973,270,56,560,108,808,619,571,723,136,712,354,556,927,958,846,370,893,557,454,255,264,610,325,477,339,998,170,6,817,759,980,87,815,892,547,976,864,470,51,0,183,405,908,462,716,754,184,961,663,639,216,927,249,894,405,940,892,927,298,709,686,630,148,854,523,696,830,387,166,881,739,701,639,647,163,707,401,348,668,417,987,237,344,588,131,101,880,375,28,178,85,67,161,233,921,684,929,103,423,448,984,162,149,975,809,665,682,562,13,703,979,352,940,676,940,423,777,172,798,158,702,883,225,863,469,498,899,750,601,322,198,937,484,348,265,293,365,299,856,378,2,187,82,294,863,374,717,993,546,516,151,248,751,728,464,220,578,363,971,179,686,169,116,522,869,381,168,234,681,376,964,35,563,46,330,427,420,47,420,318,915,923,919,667,3,383,239,581,98,562,760,136,732,228,659,953,962,827,540,995,203,856,30,118,903,712,545,675,112,317,994,27,240,913,46,243,648,638,824,746,200,936,883,284,165,894,590,127,721,130,474,276,986,504,394,241,217,292,269,329,609,263,708,202,528,107,797,176,745,974,274,945,910,157,582,427,403,172,906,124,302,380,752,640,885,499,234,454,791,503,135,752,118,843,954,646,302,104,174,47,78,800,345,988,310,927,416,713,99,322,838,753,55,942,745,940,441,979,746,584,482,881,337,952,76,643,598,379,747,124,778,825,925,123,166,235,402,934,948,853,608,138,606,663,81,704,955,874,683,701,459,518,934,148,470,363,791,421,94,891,545,872,68,822,348,234,57,102,168,358,956,129,496,914,792,929,618,748,804,654,801,263,524,736,411,994,451,554,767,545,797,313,769,866,487,117,452,545,572,973,903,528,102,751,442,246,681,413,994,485,67,148,100,591,236,863,937,687,417,705,232,567,370,353,433,857,823,237,754,395,210,9,923,664,113,717,911,794,482,257,631,549,405,83,492,641,946,782,328,715,839,912,282,561,266,715,418,89,305,525,484,515,534,759,532,999,476,443,793,959,700,776,860,106,859,705,99,805,839,428,873,678,692,155,239,958,223,9,399,528,886,235,395,773,994,927,772,823,722,566,134,423,694,346,881,554,403,332,711,242,760,584,272,805,740,863,763,315,873,515,843,759,750,238,884,745,518,657,568,240,575,54,15,269,400,248,175,804,581,887,398,693,823,671,498,915,534,262,230,759,129,425,871,879,664,755,624,534,412,544,774,987,950,790,257,351,390,784,507,971,671,905,665,847,928,163,762,463,777,345,574,906,770,445,786,786,201,762,320,965,659,95,953,609,237,562,312,979,346,819,951,370,77,616,569,357,131,331,820,909,28,747,167,799,192,953,585,745,68,906,711,727,353,16,688,942,930,1,921,628,172,224,350,601,192,919,959,324,251,131,585,279,878,752,430,423,58,16,168,126,274,231,205,979,247,893,921,177,246,194,158,419,419,508,20,963,428,331,639,31,463,224,662,341,329,93,764,739,461,285,217,735,516,422,714,764,667,987,293,914,533,451,685,304,960,57,268,740,389,907,771,852,484,433,545,165,878,310,904,339,947,121,426,463,895,492,579,914,831,873,828,365,676,865,21,988,923,289,728,312,549,851,516,385,637,61,550,515,723,806,207,670,927,985,134,174,478,713,88,309,938,269,26,615,134,48,955,409,689,684,721,590,887,589,975,524,651,877,392,726,683,599,397,962,584,883,136,414,948,577,724,239,846,102,206,332,150,161,742,192,197,815,782,85,405,758,609,408,635,353,134,671,952,883,633,889,118,122,655,419,699,731,658,897,834,216,229,336,377,323,528,927,139,311,12,896,69,973,304,56,679,790,727,631,674,361,872,792,483,528,563,534,259,221,431,445,437,12,782,167,336,310,94,827,621,458,723,42,783,379,99,462,169,826,446,843,539,670,988,374,550,551,908,162,125,691,607,914,704,389,81,392,52,527,571,673,337,294,716,473,25,167,935,194,993,733,38,885,404,378,259,306,281,168,468,406,211,76,321,915,817,754,659,869,634,230,895,323,876,611,796,253,778,84,448,123,817,838,8,573,216,268,880,849,788,348,256,999,776,929,267,594,683,278,815,669,861,710,993,89,673,789,343,803,225,791,927,43,981,287,968,549,907,848,398,47,549,654,47,325,583,666,271,619,944,439,640,805,149,633,895,175,775,590,978,0,381,257,395,714,545,364,263,804,564,661,852,113,668,899,791,603,917,414,222,861,205,863,19,355,848,914,530,623,856,860,976,237,118,371,303,15,87,566,819,652,579,671,117,247,922,260,851,839,27,425,53,232,640,72,587,489,338,469,464,194,682,440,783,800,812,86,167,899,652,986,903,231,10,21,831,284,281,682,476,308,107,529,893,748,601,832,589,939,302,53,485,336,494,268,136,658,354,303,909,358,641,813,941,651,186,772,288,467,454,764,128,914,293,21,14,246,853,603,537,507,656,22,843,502,290,331,160,996,986,70,706,628,235,647,631,421,420,919,888,226,35,368,492,328,741,506,926,947,461,463,806,118,485,2,972,127,685,133,475,672,555,181,652,790,181,635,211,953,555,451,179,942,820,24,271,913,530,197,212,992,13,19,462,850,373,434,330,58,919,805,82,474,339,734,264,872,370,475,825,277,927,4,219,99,380,842,364,911,392,577,255,405,948,69,255,321,855,585,731,775,743,814,601,434,548,866,306,270,693,131,547,620,487,119,71,868,961,436,131,705,365,738,110,313,159,366,986,14,303,717,141,398,883,743,832,432,961,138,54,654,621,954,627,109,73,698,329,386,486,812,92,851,550,554,516,709,920,502,75,576,572,217,974,455,312,807,239,273,297,646,927,919,600,906,380,25,957,61,763,443,873,207,647,423,762,163,484,34,18,559,610,942,128,937,749,440,96,341,65,393,987,993,664,587,251,396,964,208,457,727,652,330,935,651,105,697,166,589,731,536,501,694,478,981,631,580,422,727,921,839,472,908,832,137,847,84,533,811,644,991,538,296,673,825,299,779,522,466,720,606,2,221,300,833,203,283,413,977,362,334,816,834,594,1,323,441,437,209,604,81,552,142,730,225,968,29,4,842,847,77,448,850,298,100,35,853,735,448,182,97,134,351,284,728,704,959,521,493,168,125,926,720,619,8,946,939,390,302,782,237,731,582,439,30,35,474,235,770,922,770,220,408,473,856,136,529,815,9,374,984,486,300,704,106,661,2,45,51,657,179,640,388,114,80,770,149,554,358,271,829,480,843,237,953,699,726,834,515,735,208,851,222,508,555,680,521,910,77,572,919,609,213,307,723,293,430,872,199,788,495,28,268,339,618,573,38,344,407,905,431,615,756,5,475,664,685,997,574,115,921,493,724,134,152,447,779,582,671,331,370,518,359,990,857,329,563,248,673,322,153,105,289,262,462,765,926,500,114,852,615,35,345,691,522,849,490,653,432,513,984,154,31,696,145,889,25,60,489,51,383,642,508,672,904,970,789,182,470,255,34,437,643,731,128,165,581,618,170,13,483,155,519,515,203,664,756,228,77,245,631,812,239,139,836,496,110,978,678,932,233,713,722,876,796,850,41,377,821,564,742,304,719,262,171,274,278,927,502,355,524,486,519,764,625,356,612,87,334,642,20,567,707,742,444,504,944,837,881,117,401,624,774,472,238,945,746,516,225,601,224,749,87,743,513,64,99,477,152,785,120,524,705,827,266,501,331,562,338,213,32,92,189,806,916,427,103,15,295,328,968,519,78,407,263,943,471,714,421,623,852,541,147,557,368,765,58,700,680,748,265,712,192,454,870,109,233,973,476,528,302,444,48,380,851,663,323,674,729,744,650,581,637,149,490,6,267,548,58,947,297,323,11,841,129,881,950,362,206,778,890,508,222,290,240,425,305,916,100,387,660,102,320,298,251,811,656,518,711,714,817,360,37,828,202,518,61,504,880,268,283,122,128,857,765,369,283,422,637,735,809,297,189,482,947,440,645,955,959,356,669,776,69,58,957,271,576,18,127,808,638,410,931,119,268,48,840,903,470,477,990,632,126,179,114,426,971,759,381,930,467,403,59,536,813,16,159,742,386,287,550,377,49,833,496,317,881,688,572,352,165,914,336,291,445,450,69,417,561,451,699,380,206,110,917,19,478,428,761,217,715,664,594,765,497,442,434,379,130,359,83,647,625,419,290,423,221,360,192,134,163,891,514,369,2,783,740,832,564,854,49,279,518,643,396,15,437,183,746,919,894,829,566,519,600,857,294,173,217,486,307,380,378,174,101,732,309,841,916,873,695,966,505,213,961,253,229,399,788,975,318,682,157,885,554,109,742,848,283,311,335,942,691,65,468,792,149,778,985,65,3,681,31,860,894,345,466,475,744,254,803,62,289,312,299,843,421,393,43,56,704,730,999,747,147,467,891,648,597,877,714,953,558,97,813,804,442,279,632,538,534,787,953,823,99,252,18,872,998,413,929,702,496,280,802,643,747,693,292,697,570,358,650,128,807,463,285,602,95,917,140,629,704,445,804,155,50,174,27,48,939,308,750,435,588,904,431,688,598,723,385,168,433,35,649,592,850,934,194,945,203,687,926,907,132,730,414,182,256,793,582,196,102,685,983,690,589,414,378,187,489,115,356,922,150,357,867,1,291,61,946,494,100,873,753,585,955,167,119,564,312,702,760,414,387,95,457,976,510,187,516,999,303,224,274,453,581,141,806,872,554,105,718,655,978,471,592,285,990,711,849,302,765,961,69,504,57,526,833,567,713,349,918,368,573,192,174,154,333,980,378,888,85,96,895,415,919,487,701,261,550,902,915,668,216,984,172,273,862,5,192,928,706,462,296,279,655,470,785,340,451,163,580,888,611,827,304,882,314,357,143,217,611,59,237,827,395,409,100,258,767,644,186,473,107,482,105,114,305,890,806,756,406,387,996,17,214,300,900,881,9,43,450,621,454,687,448,850,96,901,460,215,897,646,689,356,480,794,470,785,36,277,893,442,16,890,460,230,542,712,111,904,107,913,525,562,600,973,764,49,226,224,264,124,222,953,480,54,99,303,192,136,580,437,578,948,679,390,178,222,102,642,478,210,555,3,772,156,328,888,557,907,464,821,31,38,775,863,444,226,166,636,362,98,74,293,46,753,683,577,327,786,219,157,996,126,160,120,634,841,360,191,748,824,13,131,862,140,994,306,718,513,295,81,611,721,726,10,826,409,587,506,547,158,663,543,284,824,15,919,17,375,462,765,199,475,896,413,967,242,72,686,755,367,119,367,440,845,729,266,606,316,772,154,474,436,697,110,612,65,29,629,440,844,746,992,319,994,405,639,236,829,677,992,548,796,711,988,993,440,255,599,108,27,105,934,815,155,44,427,220,74,408,660,918,154,652,589,148,410,580,737,239,257,729,788,405,792,776,750,584,383,702,692,763,807,626,578,962,670,358,182,96,766,195,366,273,199,308,421,609,240,158,201,850,239,341,255,31,469,6,967,853,60,659,616,867,637,546,182,660,904,364,108,671,911,475,944,111,135,717,72,375,228,273,225,819,614,833,203,84,191,170,289,251,830,905,470,819,803,652,479,708,369,588,731,280,415,27,743,902,744,816,277,324,441,855,144,56,40,347,492,583,869,781,834,51,38,656,871,841,309,350,549,678,290,632,310,705,659,406,607,756,222,237,80,15,444,576,423,484,275,915,419,145,48,253,196,86,909,67,280,570,770,181,600,60,814,263,118,473,669,725,229,243,314,662,258,758,238,682,594,514,597,13,659,998,618,207,436,880,275,716,802,45,250,403,457,64,666,575,889,335,301,471,930,967,133,188,726,723,870,672,237,820,38,248,818,656,456,606,536,83,323,339,128,925,94,937,989,112,513,230,799,166,701,729,133,186,917,211,910,788,884,499,960,922,748,130,930,556,736,819,639,411,510,119,336,604,56,677,716,569,908,515,87,961,244,221,500,513,784,410,653,20,909,613,294,9,743,225,565,480,44,204,891,906,323,580,510,732,257,578,653,517,445,741,479,41,314,979,554,98,741,208,471,2,173,765,12,917,990,577,749,386,134,992,292,809,572,154,541,830,84,195,347,529,288,178,570,602,509,477,52,250,685,523,253,858,641,265,127,631,194,876,370,680,869,14,490,441,169,383,623,253,930,971,135,218,149,705,820,659,534,225,261,219,100,514,430,741,131,909,373,678,138,95,358,7,109,200,800,630,936,424,236,866,747,371,85,248,428,257,259,963,482,521,534,583,387,316,324,871,226,49,549,364,496,259,723,958,812,875,588,748,651,176,614,398,547,51,999,328,309,258,291,143,131,825,726,871,494,403,94,72,804,995,436,301,254,511,611,418,738,199,518,390,376,133,140,275,184,139,603,845,750,246,989,233,424,67,456,918,470,550,990,627,545,778,280,152,641,891,570,379,90,89,121,818,574,262,446,110,753,401,956,855,648,945,441,424,12,249,694,835,800,684,462,697,814,742,849,807,633,772,538,75,213,660,246,787,274,44,249,379,445,205,587,445,502,380,869,867,629,563,54,429,599,868,479,765,610,328,572,595,452,463,22,665,123,620,804,749,664,54,480,110,611,67,907,466,447,129,685,77,692,739,858,644,607,337,761,569,18,686,516,470,149,538,136,624,159,292,373,175,698,853,285,310,273,545,128,720,674,165,149,718,904,8,714,863,345,476,784,715,162,300,186,311,190,674,287,701,966,660,877,665,865,514,327,138,59,807,211,733,972,360,804,876,720,518,91,418,994,875,133,508,175,319,819,717,993,458,419,312,470,296,977,336,810,656,826,870,463,389,955,435,750,759,311,470,630,754,888,624,629,374,133,156,693,304,873,39,763,292,351,233,940,680,921,751,336,100,973,799,489,280,234,239,392,545,62,22,299,302,998,280,676,483,436,722,788,309,761,903,954,464,488,894,144,410,997,480,510,970,279,351,603,513,591,995,410,5,369,61,659,367,341,688,851,129,410,991,438,523,894,744,987,382,639,131,144,988,611,6,311,242,358,914,755,301,261,517,306,630,578,317,349,919,5,552,48,415,543,838,290,789,935,277,524,926,760,668,914,371,675,225,965,33,491,72,686,752,589,992,734,167,661,436,438,667,988,838,434,884,29,725,673,964,354,197,242,115,218,156,838,893,734,804,278,225,876,964,330,466,308,416,985,969,852,776,988,841,614,775,725,995,500,750,311,854,948,553,969,166,62,808,411,796,964,41,373,840,357,703,658,17,120,996,338,324,772,327,165,738,102,242,86,954,993,397,160,293,303,130,459,365,290,222,513,606,615,886,446,972,942,457,989,414,453,327,738,577,6,904,315,460,498,401,414,491,151,575,784,454,57,595,819,699,169,332,305,784,570,103,108,512,560,449,926,365,777,665,942,135,921,610,596,419,11,362,911,514,289,47,968,698,643,787,397,164,471,54,949,42,158,57,906,70,507,833,788,636,850,730,123,123,692,71,542,56,434,805,570,75,853,539,774,848,678,171,12,150,578,313,544,736,723,802,158,230,987,946,218,837,29,693,960,721,765,855,777,199,660,348,274,865,239,400,713,917,924,78,419,502,391,315,590,114,118,748,696,105,47,266,295,428,960,255,149,725,110,279,924,123,979,550,988,218,951,702,135,875,780,907,729,523,222,319,638,340,419,686,798,466,953,93,894,913,700,396,638,163,675,914,286,654,816,274,224,119,328,359,994,460,618,75,984,841,394,974,533,166,660,331,984,613,776,879,526,477,627,516,992,654,430,278,660,599,904,884,718,233,595,65,45,214,140,29,407,887,3,940,53,16,624,37,629,752,268,508,581,895,376,573,901,807,851,561,406,756,445,124,341,393,541,386,607,682,768,14,569,123,306,622,139,282,11,121,35,280,981,616,527,357,190,429,164,393,342,922,149,788,399,842,181,940,229,140,974,997,506,543,120,812,517,612,95,881,733,130,161,714,746,40,71,288,469,588,682,164,862,183,952,613,26,485,906,607,977,880,604,483,776,76,295,645,40,742,526,125,872,39,839,971,80,263,611,901,203,293,65,417,829,369,383,855,206,289,462,183,521,418,18,649,846,314,295,887,408,173,12,633,213,204,604,645,819,567,898,374,213,316,143,42,685,526,897,244,815,711,427,689,481,446,338,327,112,633,566,520,159,931,153,724,487,109,721,306,677,619,32,242,935,175,284,973,54,181,217,869,244,996,910,725,442,249,52,906,234,971,779,393,902,932,469,389,394,190,47,423,810,431,665,97,958,949,70,12,482,639,234,726,636,144,451,430,393,855,337,628,826,116,373,80,400,843,469,794,33,868,569,195,299,234,293,258,183,715,622,17,355,856,743,991,1,546,421,394,402,110,374,228,226,748,309,979,943,130,773,976,351,695,524,2,929,817,612,465,884,235,482,239,91,226,582,92,772,4,839,526,466,213,107,45,313,768,24,256,250,149,585,601,844,109,604,774,278,216,239,162,803,73,402,895,299,984,339,424,340,178,302,159,744,409,204,57,177,228,666,428,729,251,381,574,360,985,700,990,554,291,152,357,364,906,604,16,243,944,792,583,474,94,94,570,504,298,980,33,526,646,813,608,249,195,182,961,532,882,951,438,525,103,796,889,10,752,905,253,696,49,188,523,144,635,93,0,933,425,385,812,71,551,420,320,746,602,281,630,836,584,69,361,688,217,602,50,969,860,655,18,909,195,541,405,830,986,757,764,412,143,928,835,694,348,508,792,302,141,422,490,726,491,851,766,708,805,816,30,665,823,48,927,370,941,332,201,279,90,317,43,585,245,879,279,945,387,71,247,880,845,737,606,689,940,372,749,97,540,779,115,363,179,42,86,120,374,287,400,816,956,443,401,553,674,32,498,413,455,97,294,301,186,900,990,478,625,91,575,165,871,690,881,50,732,967,523,459,606,923,627,914,718,29,467,393,413,317,158,869,766,452])"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "9 4972 4913370\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "4913370"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 43
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "MZvW-sdDr9Oh",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title 12. Integer to Roman\n",
        "# https://leetcode.com/problems/integer-to-roman/description/\n",
        "class Solution:\n",
        "  def __init__(self):\n",
        "    self.romanChar = \"IVXLCDM\"\n",
        "    self.romanNum = [1,5,10,50,100,500,1000]\n",
        "  \n",
        "  def repeat(self, ch, num):\n",
        "    res = \"\"\n",
        "    for i in range(num):\n",
        "      res += ch\n",
        "    return res\n",
        "  \n",
        "  def baseToRoman(self, num, level):\n",
        "    if num in [1,2,3]:\n",
        "      ch1 = self.romanChar[level*2]\n",
        "      return self.repeat(ch1, num)\n",
        "    if num in [4]:\n",
        "      ch1 = self.romanChar[level*2]\n",
        "      ch2 = self.romanChar[level*2 + 1]\n",
        "      return ch1 + ch2\n",
        "    if num in [5]:\n",
        "      ch2 = self.romanChar[level*2 + 1]\n",
        "      return ch2\n",
        "    if num in [6,7,8]:\n",
        "      ch1 = self.romanChar[level*2]\n",
        "      ch2 = self.romanChar[level*2 + 1]\n",
        "      return ch2 + self.repeat(ch1, num-5)\n",
        "    if num in [9]:\n",
        "      ch1 = self.romanChar[level*2]\n",
        "      ch3 = self.romanChar[level*2 + 2]\n",
        "      return ch1 + ch3\n",
        "    \n",
        "  def intToRoman(self, num):\n",
        "    res, level = \"\", 0\n",
        "    iNum = str(num)\n",
        "    for i in reversed(range(len(iNum))):\n",
        "      ch = iNum[i]\n",
        "      if ch =='0':\n",
        "        pass\n",
        "      else:\n",
        "        res = self.baseToRoman(int(ch), level) + res\n",
        "        \n",
        "      level += 1\n",
        "    return res\n",
        "        "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "7iVJMe321UUy",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title 13. Roman to Integer\n",
        "# https://leetcode.com/problems/roman-to-integer/\n",
        "class Solution:\n",
        "  def __init__(self):\n",
        "    self.romanTrans = [\n",
        "      {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M':1000}, \n",
        "      {'II': 2, 'IV': 4, 'VI': 6, 'IX': 9, 'XX': 20, 'XL': 40, 'LX': 60, 'XC': 90, 'CC': 200, 'CD': 400, 'DC': 600, 'CM': 900}, \n",
        "      {'III': 3, 'VII': 7, 'XXX': 30, 'LXX': 70, 'CCC': 300, 'DCC': 700}, \n",
        "      {'VIII': 8, 'LXXX': 80, 'DCCC': 800}]\n",
        "    \n",
        "  def romanToInt(self, s):\n",
        "    num = s\n",
        "    for l in reversed(range(4)):\n",
        "      for k in self.romanTrans[l].keys():\n",
        "        num = num.replace(k, str(self.romanTrans[l][k])+\"+\")\n",
        "    return eval(num[:-1])\n",
        "  "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tZA9xfOyGDa_",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title 14. Longest Common Prefix\n",
        "# https://leetcode.com/problems/longest-common-prefix/description/\n",
        "class Solution:\n",
        "  def longestCommonPrefix(self, strs):\n",
        "    \n",
        "    \"\"\"\n",
        "    :type strs: List[str]\n",
        "    :rtype: str\n",
        "    \"\"\"\n",
        "    if strs == []:\n",
        "      return \"\"\n",
        "    minLen = 9999\n",
        "    for i in range(len(strs)):\n",
        "      strLen = len(strs[i])\n",
        "      if strLen < minLen:\n",
        "        minLen = strLen\n",
        "        \n",
        "    commonPrefix = \"\"\n",
        "    for j in range(minLen):\n",
        "      c = strs[0][j]\n",
        "      equal = True\n",
        "      for i in range(1, len(strs)):\n",
        "        if c != strs[i][j]:\n",
        "          equal = False\n",
        "          break\n",
        "      if not equal:\n",
        "        break\n",
        "      commonPrefix += c\n",
        "    return commonPrefix\n",
        "Solution().longestCommonPrefix([\"flower\",\"flow\",\"flight\"])"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "VtpzUJQTAEgY",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title 15. 3Sum\n",
        "# https://leetcode.com/problems/3sum/description/\n",
        "class Solution:\n",
        "\n",
        "  # bubble sort for 3 values, simply 3 conditional value swap\n",
        "  def threeBubbleSort(self, c1, c2, c3):\n",
        "    if c1> c2:\n",
        "      tmp = c2\n",
        "      c2 = c1\n",
        "      c1 = tmp\n",
        "    if c2> c3:\n",
        "      tmp = c3\n",
        "      c3 = c2\n",
        "      c2 = tmp\n",
        "    if c1> c2:\n",
        "      tmp = c2\n",
        "      c2 = c1\n",
        "      c1 = tmp\n",
        "    return [c1, c2, c3]\n",
        "\n",
        "  # user defined hash with a larger prime value 9791\n",
        "  def hash(self, nums):\n",
        "    max3 = 9791\n",
        "    return max3**2*nums[0] + max3*nums[1] + nums[0]\n",
        "\n",
        "  def threeSum(self, nums):\n",
        "    # solution in O(n^2) complexicity\n",
        "    # skip incorrect input\n",
        "    if nums==None or len(nums) ==0 :\n",
        "      return []\n",
        "\n",
        "    # preprocess and dedup\n",
        "    d, num2, counter, prev = {}, [], 0, -9999\n",
        "    numLen = len(nums)\n",
        "    nums.sort()\n",
        "    max3, min3 = nums[numLen-1], nums[0]\n",
        "    \n",
        "    # only keep 3 continuous equal-values\n",
        "    for n in nums:\n",
        "      if n == prev:\n",
        "        counter += 1\n",
        "      else:\n",
        "        counter = 1\n",
        "      if (n==0 and counter <=3) or (n!=0 and counter<=2):\n",
        "        num2.append(n)\n",
        "      prev = n\n",
        "    nums = num2    \n",
        "    numLen = len(nums)\n",
        "    \n",
        "    # put the item in dictionary and value as index\n",
        "    # index will be used in the later step\n",
        "    for i in range(numLen):\n",
        "      d[nums[i]] = i\n",
        "    \n",
        "    # res, resKey is used to store and lookup the value\n",
        "    # resKey used a user-defined hash function to store the sorted list\n",
        "    res, resKey = [], {}\n",
        "    \n",
        "    # generate the combination of 2 variables along numLen axis\n",
        "    for i in range(numLen-1):\n",
        "      for j in range(i+1, numLen):\n",
        "        key = -nums[i] -nums[j]\n",
        "        # skip for those will too large or too small ones\n",
        "        if key>max3 or key<min3:\n",
        "          continue\n",
        "        \n",
        "        # if the value is in the dictionary\n",
        "        # and index value not equals to either i or j\n",
        "        # because, duplicating the index may cause error in return values\n",
        "        if key in d:\n",
        "          if d[key] != i and d[key] != j:\n",
        "            # create a list n with a sorted values\n",
        "            n = self.threeBubbleSort(key, nums[i], nums[j])\n",
        "            # generate hash value nHash for the list, in case there're duplicated value\n",
        "            nHash = self.hash(n)\n",
        "            if not nHash in resKey:\n",
        "              resKey[nHash] = nHash\n",
        "              res.append(n)\n",
        "    return res\n",
        "  \n",
        "#Solution().threeSum([-1,0,1,2,-1,-4])\n",
        "Solution().threeSum([82597,-9243,62390,83030,-97960,-26521,-61011,83390,-38677,12333,75987,46091,83794,19355,-71037,-6242,-28801,324,1202,-90885,-2989,-95597,-34333,35528,5680,89093,-90606,50360,-29393,-27012,53313,65213,99818,-82405,-41661,-3333,-51952,72135,-1523,26377,74685,96992,92263,15929,5467,-99555,-43348,-41689,-60383,-3990,32165,65265,-72973,-58372,12741,-48568,-46596,72419,-1859,34153,62937,81310,-61823,-96770,-54944,8845,-91184,24208,-29078,31495,65258,14198,85395,70506,-40908,56740,-12228,-40072,32429,93001,68445,-73927,25731,-91859,-24150,10093,-60271,-81683,-18126,51055,48189,-6468,25057,81194,-58628,74042,66158,-14452,-49851,-43667,11092,39189,-17025,-79173,13606,83172,92647,-59741,19343,-26644,-57607,82908,-20655,1637,80060,98994,39331,-31274,-61523,91225,-72953,13211,-75116,-98421,-41571,-69074,99587,39345,42151,-2460,98236,15690,-52507,-95803,-48935,-46492,-45606,-79254,-99851,52533,73486,39948,-7240,71815,-585,-96252,90990,-93815,93340,-71848,58733,-14859,-83082,-75794,-82082,-24871,-15206,91207,-56469,-93618,67131,-8682,75719,87429,-98757,-7535,-24890,-94160,85003,33928,75538,97456,-66424,-60074,-8527,-28697,-22308,2246,-70134,-82319,-10184,87081,-34949,-28645,-47352,-83966,-60418,-15293,-53067,-25921,55172,75064,95859,48049,34311,-86931,-38586,33686,-36714,96922,76713,-22165,-80585,-34503,-44516,39217,-28457,47227,-94036,43457,24626,-87359,26898,-70819,30528,-32397,-69486,84912,-1187,-98986,-32958,4280,-79129,-65604,9344,58964,50584,71128,-55480,24986,15086,-62360,-42977,-49482,-77256,-36895,-74818,20,3063,-49426,28152,-97329,6086,86035,-88743,35241,44249,19927,-10660,89404,24179,-26621,-6511,57745,-28750,96340,-97160,-97822,-49979,52307,79462,94273,-24808,77104,9255,-83057,77655,21361,55956,-9096,48599,-40490,-55107,2689,29608,20497,66834,-34678,23553,-81400,-66630,-96321,-34499,-12957,-20564,25610,-4322,-58462,20801,53700,71527,24669,-54534,57879,-3221,33636,3900,97832,-27688,-98715,5992,24520,-55401,-57613,-69926,57377,-77610,20123,52174,860,60429,-91994,-62403,-6218,-90610,-37263,-15052,62069,-96465,44254,89892,-3406,19121,-41842,-87783,-64125,-56120,73904,-22797,-58118,-4866,5356,75318,46119,21276,-19246,-9241,-97425,57333,-15802,93149,25689,-5532,95716,39209,-87672,-29470,-16324,-15331,27632,-39454,56530,-16000,29853,46475,78242,-46602,83192,-73440,-15816,50964,-36601,89758,38375,-40007,-36675,-94030,67576,46811,-64919,45595,76530,40398,35845,41791,67697,-30439,-82944,63115,33447,-36046,-50122,-34789,43003,-78947,-38763,-89210,32756,-20389,-31358,-90526,-81607,88741,86643,98422,47389,-75189,13091,95993,-15501,94260,-25584,-1483,-67261,-70753,25160,89614,-90620,-48542,83889,-12388,-9642,-37043,-67663,28794,-8801,13621,12241,55379,84290,21692,-95906,-85617,-17341,-63767,80183,-4942,-51478,30997,-13658,8838,17452,-82869,-39897,68449,31964,98158,-49489,62283,-62209,-92792,-59342,55146,-38533,20496,62667,62593,36095,-12470,5453,-50451,74716,-17902,3302,-16760,-71642,-34819,96459,-72860,21638,47342,-69897,-40180,44466,76496,84659,13848,-91600,-90887,-63742,-2156,-84981,-99280,94326,-33854,92029,-50811,98711,-36459,-75555,79110,-88164,-97397,-84217,97457,64387,30513,-53190,-83215,252,2344,-27177,-92945,-89010,82662,-11670,86069,53417,42702,97082,3695,-14530,-46334,17910,77999,28009,-12374,15498,-46941,97088,-35030,95040,92095,-59469,-24761,46491,67357,-66658,37446,-65130,-50416,99197,30925,27308,54122,-44719,12582,-99525,-38446,-69050,-22352,94757,-56062,33684,-40199,-46399,96842,-50881,-22380,-65021,40582,53623,-76034,77018,-97074,-84838,-22953,-74205,79715,-33920,-35794,-91369,73421,-82492,63680,-14915,-33295,37145,76852,-69442,60125,-74166,74308,-1900,-30195,-16267,-60781,-27760,5852,38917,25742,-3765,49097,-63541,98612,-92865,-30248,9612,-8798,53262,95781,-42278,-36529,7252,-27394,-5021,59178,80934,-48480,-75131,-54439,-19145,-48140,98457,-6601,-51616,-89730,78028,32083,-48904,16822,-81153,-8832,48720,-80728,-45133,-86647,-4259,-40453,2590,28613,50523,-4105,-27790,-74579,-17223,63721,33489,-47921,97628,-97691,-14782,-65644,18008,-93651,-71266,80990,-76732,-47104,35368,28632,59818,-86269,-89753,34557,-92230,-5933,-3487,-73557,-13174,-43981,-43630,-55171,30254,-83710,-99583,-13500,71787,5017,-25117,-78586,86941,-3251,-23867,-36315,75973,86272,-45575,77462,-98836,-10859,70168,-32971,-38739,-12761,93410,14014,-30706,-77356,-85965,-62316,63918,-59914,-64088,1591,-10957,38004,15129,-83602,-51791,34381,-89382,-26056,8942,5465,71458,-73805,-87445,-19921,-80784,69150,-34168,28301,-68955,18041,6059,82342,9947,39795,44047,-57313,48569,81936,-2863,-80932,32976,-86454,-84207,33033,32867,9104,-16580,-25727,80157,-70169,53741,86522,84651,68480,84018,61932,7332,-61322,-69663,76370,41206,12326,-34689,17016,82975,-23386,39417,72793,44774,-96259,3213,79952,29265,-61492,-49337,14162,65886,3342,-41622,-62659,-90402,-24751,88511,54739,-21383,-40161,-96610,-24944,-602,-76842,-21856,69964,43994,-15121,-85530,12718,13170,-13547,69222,62417,-75305,-81446,-38786,-52075,-23110,97681,-82800,-53178,11474,35857,94197,-58148,-23689,32506,92154,-64536,-73930,-77138,97446,-83459,70963,22452,68472,-3728,-25059,-49405,95129,-6167,12808,99918,30113,-12641,-26665,86362,-33505,50661,26714,33701,89012,-91540,40517,-12716,-57185,-87230,29914,-59560,13200,-72723,58272,23913,-45586,-96593,-26265,-2141,31087,81399,92511,-34049,20577,2803,26003,8940,42117,40887,-82715,38269,40969,-50022,72088,21291,-67280,-16523,90535,18669,94342,-39568,-88080,-99486,-20716,23108,-28037,63342,36863,-29420,-44016,75135,73415,16059,-4899,86893,43136,-7041,33483,-67612,25327,40830,6184,61805,4247,81119,-22854,-26104,-63466,63093,-63685,60369,51023,51644,-16350,74438,-83514,99083,10079,-58451,-79621,48471,67131,-86940,99093,11855,-22272,-67683,-44371,9541,18123,37766,-70922,80385,-57513,-76021,-47890,36154,72935,84387,-92681,-88303,-7810,59902,-90,-64704,-28396,-66403,8860,13343,33882,85680,7228,28160,-14003,54369,-58893,92606,-63492,-10101,64714,58486,29948,-44679,-22763,10151,-56695,4031,-18242,-36232,86168,-14263,9883,47124,47271,92761,-24958,-73263,-79661,-69147,-18874,29546,-92588,-85771,26451,-86650,-43306,-59094,-47492,-34821,-91763,-47670,33537,22843,67417,-759,92159,63075,94065,-26988,55276,65903,30414,-67129,-99508,-83092,-91493,-50426,14349,-83216,-76090,32742,-5306,-93310,-60750,-60620,-45484,-21108,-58341,-28048,-52803,69735,78906,81649,32565,-86804,-83202,-65688,-1760,89707,93322,-72750,84134,71900,-37720,19450,-78018,22001,-23604,26276,-21498,65892,-72117,-89834,-23867,55817,-77963,42518,93123,-83916,63260,-2243,-97108,85442,-36775,17984,-58810,99664,-19082,93075,-69329,87061,79713,16296,70996,13483,-74582,49900,-27669,-40562,1209,-20572,34660,83193,75579,7344,64925,88361,60969,3114,44611,-27445,53049,-16085,-92851,-53306,13859,-33532,86622,-75666,-18159,-98256,51875,-42251,-27977,-18080,23772,38160,41779,9147,94175,99905,-85755,62535,-88412,-52038,-68171,93255,-44684,-11242,-104,31796,62346,-54931,-55790,-70032,46221,56541,-91947,90592,93503,4071,20646,4856,-63598,15396,-50708,32138,-85164,38528,-89959,53852,57915,-42421,-88916,-75072,67030,-29066,49542,-71591,61708,-53985,-43051,28483,46991,-83216,80991,-46254,-48716,39356,-8270,-47763,-34410,874,-1186,-7049,28846,11276,21960,-13304,-11433,-4913,55754,79616,70423,-27523,64803,49277,14906,-97401,-92390,91075,70736,21971,-3303,55333,-93996,76538,54603,-75899,98801,46887,35041,48302,-52318,55439,24574,14079,-24889,83440,14961,34312,-89260,-22293,-81271,-2586,-71059,-10640,-93095,-5453,-70041,66543,74012,-11662,-52477,-37597,-70919,92971,-17452,-67306,-80418,7225,-89296,24296,86547,37154,-10696,74436,-63959,58860,33590,-88925,-97814,-83664,85484,-8385,-50879,57729,-74728,-87852,-15524,-91120,22062,28134,80917,32026,49707,-54252,-44319,-35139,13777,44660,85274,25043,58781,-89035,-76274,6364,-63625,72855,43242,-35033,12820,-27460,77372,-47578,-61162,-70758,-1343,-4159,64935,56024,-2151,43770,19758,-30186,-86040,24666,-62332,-67542,73180,-25821,-27826,-45504,-36858,-12041,20017,-24066,-56625,-52097,-47239,-90694,8959,7712,-14258,-5860,55349,61808,-4423,-93703,64681,-98641,-25222,46999,-83831,-54714,19997,-68477,66073,51801,-66491,52061,-52866,79907,-39736,-68331,68937,91464,98892,910,93501,31295,-85873,27036,-57340,50412,21,-2445,29471,71317,82093,-94823,-54458,-97410,39560,-7628,66452,39701,54029,37906,46773,58296,60370,-61090,85501,-86874,71443,-72702,-72047,14848,34102,77975,-66294,-36576,31349,52493,-70833,-80287,94435,39745,-98291,84524,-18942,10236,93448,50846,94023,-6939,47999,14740,30165,81048,84935,-19177,-13594,32289,62628,-90612,-542,-66627,64255,71199,-83841,-82943,-73885,8623,-67214,-9474,-35249,62254,-14087,-90969,21515,-83303,94377,-91619,19956,-98810,96727,-91939,29119,-85473,-82153,-69008,44850,74299,-76459,-86464,8315,-49912,-28665,59052,-69708,76024,-92738,50098,18683,-91438,18096,-19335,35659,91826,15779,-73070,67873,-12458,-71440,-46721,54856,97212,-81875,35805,36952,68498,81627,-34231,81712,27100,-9741,-82612,18766,-36392,2759,41728,69743,26825,48355,-17790,17165,56558,3295,-24375,55669,-16109,24079,73414,48990,-11931,-78214,90745,19878,35673,-15317,-89086,94675,-92513,88410,-93248,-19475,-74041,-19165,32329,-26266,-46828,-18747,45328,8990,-78219,-25874,-74801,-44956,-54577,-29756,-99822,-35731,-18348,-68915,-83518,-53451,95471,-2954,-13706,-8763,-21642,-37210,16814,-60070,-42743,27697,-36333,-42362,11576,85742,-82536,68767,-56103,-63012,71396,-78464,-68101,-15917,-11113,-3596,77626,-60191,-30585,-73584,6214,-84303,18403,23618,-15619,-89755,-59515,-59103,-74308,-63725,-29364,-52376,-96130,70894,-12609,50845,-2314,42264,-70825,64481,55752,4460,-68603,-88701,4713,-50441,-51333,-77907,97412,-66616,-49430,60489,-85262,-97621,-18980,44727,-69321,-57730,66287,-92566,-64427,-14270,11515,-92612,-87645,61557,24197,-81923,-39831,-10301,-23640,-76219,-68025,92761,-76493,68554,-77734,-95620,-11753,-51700,98234,-68544,-61838,29467,46603,-18221,-35441,74537,40327,-58293,75755,-57301,-7532,-94163,18179,-14388,-22258,-46417,-48285,18242,-77551,82620,250,-20060,-79568,-77259,82052,-98897,-75464,48773,-79040,-11293,45941,-67876,-69204,-46477,-46107,792,60546,-34573,-12879,-94562,20356,-48004,-62429,96242,40594,2099,99494,25724,-39394,-2388,-18563,-56510,-83570,-29214,3015,74454,74197,76678,-46597,60630,-76093,37578,-82045,-24077,62082,-87787,-74936,58687,12200,-98952,70155,-77370,21710,-84625,-60556,-84128,925,65474,-15741,-94619,88377,89334,44749,22002,-45750,-93081,-14600,-83447,46691,85040,-66447,-80085,56308,44310,24979,-29694,57991,4675,-71273,-44508,13615,-54710,23552,-78253,-34637,50497,68706,81543,-88408,-21405,6001,-33834,-21570,-46692,-25344,20310,71258,-97680,11721,59977,59247,-48949,98955,-50276,-80844,-27935,-76102,55858,-33492,40680,66691,-33188,8284,64893,-7528,6019,-85523,8434,-64366,-56663,26862,30008,-7611,-12179,-70076,21426,-11261,-36864,-61937,-59677,929,-21052,3848,-20888,-16065,98995,-32293,-86121,-54564,77831,68602,74977,31658,40699,29755,98424,80358,-69337,26339,13213,-46016,-18331,64713,-46883,-58451,-70024,-92393,-4088,70628,-51185,71164,-75791,-1636,-29102,-16929,-87650,-84589,-24229,-42137,-15653,94825,13042,88499,-47100,-90358,-7180,29754,-65727,-42659,-85560,-9037,-52459,20997,-47425,17318,21122,20472,-23037,65216,-63625,-7877,-91907,24100,-72516,22903,-85247,-8938,73878,54953,87480,-31466,-99524,35369,-78376,89984,-15982,94045,-7269,23319,-80456,-37653,-76756,2909,81936,54958,-12393,60560,-84664,-82413,66941,-26573,-97532,64460,18593,-85789,-38820,-92575,-43663,-89435,83272,-50585,13616,-71541,-53156,727,-27644,16538,34049,57745,34348,35009,16634,-18791,23271,-63844,95817,21781,16590,59669,15966,-6864,48050,-36143,97427,-59390,96931,78939,-1958,50777,43338,-51149,39235,-27054,-43492,67457,-83616,37179,10390,85818,2391,73635,87579,-49127,-81264,-79023,-81590,53554,-74972,-83940,-13726,-39095,29174,78072,76104,47778,25797,-29515,-6493,-92793,22481,-36197,-65560,42342,15750,97556,99634,-56048,-35688,13501,63969,-74291,50911,39225,93702,-3490,-59461,-30105,-46761,-80113,92906,-68487,50742,36152,-90240,-83631,24597,-50566,-15477,18470,77038,40223,-80364,-98676,70957,-63647,99537,13041,31679,86631,37633,-16866,13686,-71565,21652,-46053,-80578,-61382,68487,-6417,4656,20811,67013,-30868,-11219,46,74944,14627,56965,42275,-52480,52162,-84883,-52579,-90331,92792,42184,-73422,-58440,65308,-25069,5475,-57996,59557,-17561,2826,-56939,14996,-94855,-53707,99159,43645,-67719,-1331,21412,41704,31612,32622,1919,-69333,-69828,22422,-78842,57896,-17363,27979,-76897,35008,46482,-75289,65799,20057,7170,41326,-76069,90840,-81253,-50749,3649,-42315,45238,-33924,62101,96906,58884,-7617,-28689,-66578,62458,50876,-57553,6739,41014,-64040,-34916,37940,13048,-97478,-11318,-89440,-31933,-40357,-59737,-76718,-14104,-31774,28001,4103,41702,-25120,-31654,63085,-3642,84870,-83896,-76422,-61520,12900,88678,85547,33132,-88627,52820,63915,-27472,78867,-51439,33005,-23447,-3271,-39308,39726,-74260,-31874,-36893,93656,910,-98362,60450,-88048,99308,13947,83996,-90415,-35117,70858,-55332,-31721,97528,82982,-86218,6822,25227,36946,97077,-4257,-41526,56795,89870,75860,-70802,21779,14184,-16511,-89156,-31422,71470,69600,-78498,74079,-19410,40311,28501,26397,-67574,-32518,68510,38615,19355,-6088,-97159,-29255,-92523,3023,-42536,-88681,64255,41206,44119,52208,39522,-52108,91276,-70514,83436,63289,-79741,9623,99559,12642,85950,83735,-21156,-67208,98088,-7341,-27763,-30048,-44099,-14866,-45504,-91704,19369,13700,10481,-49344,-85686,33994,19672,36028,60842,66564,-24919,33950,-93616,-47430,-35391,-28279,56806,74690,39284,-96683,-7642,-75232,37657,-14531,-86870,-9274,-26173,98640,88652,64257,46457,37814,-19370,9337,-22556,-41525,39105,-28719,51611,-93252,98044,-90996,21710,-47605,-64259,-32727,53611,-31918,-3555,33316,-66472,21274,-37731,-2919,15016,48779,-88868,1897,41728,46344,-89667,37848,68092,-44011,85354,-43776,38739,-31423,-66330,65167,-22016,59405,34328,-60042,87660,-67698,-59174,-1408,-46809,-43485,-88807,-60489,13974,22319,55836,-62995,-37375,-4185,32687,-36551,-75237,58280,26942,-73756,71756,78775,-40573,14367,-71622,-77338,24112,23414,-7679,-51721,87492,85066,-21612,57045,10673,-96836,52461,-62218,-9310,65862,-22748,89906,-96987,-98698,26956,-43428,46141,47456,28095,55952,67323,-36455,-60202,-43302,-82932,42020,77036,10142,60406,70331,63836,58850,-66752,52109,21395,-10238,-98647,-41962,27778,69060,98535,-28680,-52263,-56679,66103,-42426,27203,80021,10153,58678,36398,63112,34911,20515,62082,-15659,-40785,27054,43767,-20289,65838,-6954,-60228,-72226,52236,-35464,25209,-15462,-79617,-41668,-84083,62404,-69062,18913,46545,20757,13805,24717,-18461,-47009,-25779,68834,64824,34473,39576,31570,14861,-15114,-41233,95509,68232,67846,84902,-83060,17642,-18422,73688,77671,-26930,64484,-99637,73875,6428,21034,-73471,19664,-68031,15922,-27028,48137,54955,-82793,-41144,-10218,-24921,-28299,-2288,68518,-54452,15686,-41814,66165,-72207,-61986,80020,50544,-99500,16244,78998,40989,14525,-56061,-24692,-94790,21111,37296,-90794,72100,70550,-31757,17708,-74290,61910,78039,-78629,-25033,73172,-91953,10052,64502,99585,-1741,90324,-73723,68942,28149,30218,24422,16659,10710,-62594,94249,96588,46192,34251,73500,-65995,-81168,41412,-98724,-63710,-54696,-52407,19746,45869,27821,-94866,-76705,-13417,-61995,-71560,43450,67384,-8838,-80293,-28937,23330,-89694,-40586,46918,80429,-5475,78013,25309,-34162,37236,-77577,86744,26281,-29033,-91813,35347,13033,-13631,-24459,3325,-71078,-75359,81311,19700,47678,-74680,-84113,45192,35502,37675,19553,76522,-51098,-18211,89717,4508,-82946,27749,85995,89912,-53678,-64727,-14778,32075,-63412,-40524,86440,-2707,-36821,63850,-30883,67294,-99468,-23708,34932,34386,98899,29239,-23385,5897,54882,98660,49098,70275,17718,88533,52161,63340,50061,-89457,19491,-99156,24873,-17008,64610,-55543,50495,17056,-10400,-56678,-29073,-42960,-76418,98562,-88104,-96255,10159,-90724,54011,12052,45871,-90933,-69420,67039,37202,78051,-52197,-40278,-58425,65414,-23394,-1415,6912,-53447,7352,17307,-78147,63727,98905,55412,-57658,-32884,-44878,22755,39730,3638,35111,39777,74193,38736,-11829,-61188,-92757,55946,-71232,-63032,-83947,39147,-96684,-99233,25131,-32197,24406,-55428,-61941,25874,-69453,64483,-19644,-68441,12783,87338,-48676,66451,-447,-61590,50932,-11270,29035,65698,-63544,10029,80499,-9461,86368,91365,-81810,-71914,-52056,-13782,44240,-30093,-2437,24007,67581,-17365,-69164,-8420,-69289,-29370,48010,90439,13141,69243,50668,39328,61731,78266,-81313,17921,-38196,55261,9948,-24970,75712,-72106,28696,7461,31621,61047,51476,56512,11839,-96916,-82739,28924,-99927,58449,37280,69357,11219,-32119,-62050,-48745,-83486,-52376,42668,82659,68882,38773,46269,-96005,97630,25009,-2951,-67811,99801,81587,-79793,-18547,-83086,69512,33127,-92145,-88497,47703,59527,1909,88785,-88882,69188,-46131,-5589,-15086,36255,-53238,-33009,82664,53901,35939,-42946,-25571,33298,69291,53199,74746,-40127,-39050,91033,51717,-98048,87240,36172,65453,-94425,-63694,-30027,59004,88660,3649,-20267,-52565,-67321,34037,4320,91515,-56753,60115,27134,68617,-61395,-26503,-98929,-8849,-63318,10709,-16151,61905,-95785,5262,23670,-25277,90206,-19391,45735,37208,-31992,-92450,18516,-90452,-58870,-58602,93383,14333,17994,82411,-54126,-32576,35440,-60526,-78764,-25069,-9022,-394,92186,-38057,55328,-61569,67780,77169,19546,-92664,-94948,44484,-13439,83529,27518,-48333,72998,38342,-90553,-98578,-76906,81515,-16464,78439,92529,35225,-39968,-10130,-7845,-32245,-74955,-74996,67731,-13897,-82493,33407,93619,59560,-24404,-57553,19486,-45341,34098,-24978,-33612,79058,71847,76713,-95422,6421,-96075,-59130,-28976,-16922,-62203,69970,68331,21874,40551,89650,51908,58181,66480,-68177,34323,-3046,-49656,-59758,43564,-10960,-30796,15473,-20216,46085,-85355,41515,-30669,-87498,57711,56067,63199,-83805,62042,91213,-14606,4394,-562,74913,10406,96810,-61595,32564,31640,-9732,42058,98052,-7908,-72330,1558,-80301,34878,32900,3939,-8824,88316,20937,21566,-3218,-66080,-31620,86859,54289,90476,-42889,-15016,-18838,75456,30159,-67101,42328,-92703,85850,-5475,23470,-80806,68206,17764,88235,46421,-41578,74005,-81142,80545,20868,-1560,64017,83784,68863,-97516,-13016,-72223,79630,-55692,82255,88467,28007,-34686,-69049,-41677,88535,-8217,68060,-51280,28971,49088,49235,26905,-81117,-44888,40623,74337,-24662,97476,79542,-72082,-35093,98175,-61761,-68169,59697,-62542,-72965,59883,-64026,-37656,-92392,-12113,-73495,98258,68379,-21545,64607,-70957,-92254,-97460,-63436,-8853,-19357,-51965,-76582,12687,-49712,45413,-60043,33496,31539,-57347,41837,67280,-68813,52088,-13155,-86430,-15239,-45030,96041,18749,-23992,46048,35243,-79450,85425,-58524,88781,-39454,53073,-48864,-82289,39086,82540,-11555,25014,-5431,-39585,-89526,2705,31953,-81611,36985,-56022,68684,-27101,11422,64655,-26965,-63081,-13840,-91003,-78147,-8966,41488,1988,99021,-61575,-47060,65260,-23844,-21781,-91865,-19607,44808,2890,63692,-88663,-58272,15970,-65195,-45416,-48444,-78226,-65332,-24568,42833,-1806,-71595,80002,-52250,30952,48452,-90106,31015,-22073,62339,63318,78391,28699,77900,-4026,-76870,-45943,33665,9174,-84360,-22684,-16832,-67949,-38077,-38987,-32847,51443,-53580,-13505,9344,-92337,26585,70458,-52764,-67471,-68411,-1119,-2072,-93476,67981,40887,-89304,-12235,41488,1454,5355,-34855,-72080,24514,-58305,3340,34331,8731,77451,-64983,-57876,82874,62481,-32754,-39902,22451,-79095,-23904,78409,-7418,77916]) \n",
        "\n",
        "#Solution().threeSum([6,-5,-6,-1,-2,8,-1,4,-10,-8,-10,-2,-4,-1,-8,-2,8,9,-5,-2,-8,-9,-3,-5])\n",
        "\n",
        "\n",
        "       "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ciJUM8AkdTeY",
        "colab_type": "code",
        "outputId": "d07acf4d-1bdb-450e-ef99-9bb2fdf11919",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "#@title 16. 3Sum Closest\n",
        "# https://leetcode.com/problems/3sum-closest/description/\n",
        "\n",
        "# hash code doesnt work in this way O(n^3)\n",
        "class Solution:\n",
        "  def threeSumClosest(self, nums, target):\n",
        "    \"\"\"\n",
        "    :type nums: List[int]\n",
        "    :type target: int\n",
        "    :rtype: int\n",
        "    \"\"\"\n",
        "    if nums==None or len(nums) ==0 :\n",
        "      return []\n",
        "    \n",
        "    # preprocess and dedup\n",
        "    d, num2, counter, prev = {}, [], 0, -9999\n",
        "    numLen = len(nums)\n",
        "    nums.sort()\n",
        "    max3, min3 = nums[numLen-1], nums[0]\n",
        "    ans = nums[0] + nums[1] + nums[numLen-1]\n",
        "    \n",
        "    # only keep 3 continuous equal-values\n",
        "    for n in nums:\n",
        "      if n == prev:\n",
        "        counter += 1\n",
        "      else:\n",
        "        counter = 1\n",
        "      if (counter <=3):\n",
        "        num2.append(n)\n",
        "      prev = n\n",
        "    nums = num2    \n",
        "    numLen = len(nums)\n",
        "    print(numLen)\n",
        "    \n",
        "    calc = 0\n",
        "\n",
        "    # put the item in dictionary and value as index\n",
        "    # index will be used in the later step\n",
        "    for i in range(numLen):\n",
        "      d[nums[i]] = i\n",
        "    \n",
        "    # generate the combination of 2 variables along numLen axis\n",
        "    for i in range(numLen-1):\n",
        "      for j in range(i+1, numLen):\n",
        "        \n",
        "        key = -nums[i] -nums[j] +target\n",
        "        found = False\n",
        "        searchRange = abs(target-ans)\n",
        "        \n",
        "        #print(\"i[%d]=%d, j[%d]=%d, s=+-%d\" % (i, nums[i], j, nums[j], searchRange))\n",
        "        for k in range(searchRange):\n",
        "          if k ==0:\n",
        "            zSet = [1]\n",
        "          else:\n",
        "            zSet = [-1,1]\n",
        "          for z in zSet:\n",
        "            newKey = key + z*k\n",
        "            if newKey in d and d[newKey] != i and d[newKey] != j:\n",
        "              #if abs(nums[i] + nums[j] + newKey - target) < abs(ans - target):\n",
        "              ans = nums[i] + nums[j] + newKey\n",
        "              found = True\n",
        "              break\n",
        "          if found:\n",
        "            break\n",
        "            \n",
        "        # early stop   \n",
        "        if ans == target:\n",
        "          return ans\n",
        "    return ans\n",
        "\n",
        "# kind of greedy search for 2 dimensions O(n^2)\n",
        "class Solution:\n",
        "  def threeSumClosest(self, nums, target):\n",
        "    \n",
        "    nums.sort()\n",
        "    minDiff, numsLen, ans =100000, len(nums), 0\n",
        "\n",
        "    for i in range(numsLen):\n",
        "      left, right = i+1, numsLen-1\n",
        "      while left < right:\n",
        "        sumVal = nums[i] + nums[left] + nums[right]\n",
        "        # early stop\n",
        "        if sumVal==target:\n",
        "          return sumVal\n",
        "        \n",
        "        diff = abs(sumVal - target)\n",
        "        if diff<minDiff:\n",
        "          minDiff = diff\n",
        "          ans = sumVal\n",
        "\n",
        "        if sumVal<target:\n",
        "          left += 1\n",
        "        else:\n",
        "          right -= 1\n",
        "    return ans\n",
        "#Solution().threeSumClosest([1,1,1,0],100)\n",
        "#Solution().threeSumClosest([-1, 2, 1, -4],1)\n",
        "#Solution().threeSumClosest([1,1,-1,-1,3],3)\n",
        "#Solution().threeSumClosest([0,5,-1,-2,4,-1,0,-3,4,-5],1)\n",
        "Solution().threeSumClosest([82,-16,-60,-48,32,-30,0,-89,70,-46,-82,-58,66,41,-96,-55,-49,-87,-33,-65,9,14,81,-11,80,-93,79,-63,-61,-16,22,-31,75,12,17,-6,37,-2,-89,-66,3,-95,-74,58,-95,22,11,-20,-36,60,-75,46,-52,-61,-28,7,-50,-45,93,-91,-43,35,-99,-39,53,-54,-98,-4,13,-90,23,-4,-65,29,85,-76,-64,81,32,-97,51,12,-82,-31,81,-2,-83,-9,89,-37,-23,-66,-91,-15,-98,-74,94,30,-2,-70,13,19,-77,-42,33,-70,25,77,47,-70,-70,60,-63,-4,83,13,-78,-23,28,-86,-11,-16,-57,-84,51,-48,-63,-15,29,56,-25,73,-69,23,28,90,96,41,65,-22,-43,-68,-77,31,69,-84,23,-63,-18,20,-93,-17,-48,-73,14,-95,98,-64,-12,-45,14,7,51,-61,89,-48,-23,2,-56,84,-2,27,74,-39,-18,-65,79,-36,-76,-30,44,78,-76,37,88,0,32,55,-51,23,-9,68,26,15,66,66,-56,-42,56,28,33,-32,-23,-36,-12,-76,-12,42,12,40,69,54,82,-22,-7,46,-46],270)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "270"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 84
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BPvrndBV1wpM",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title 17. Letter Combinations of a Phone Number\n",
        "# https://leetcode.com/problems/letter-combinations-of-a-phone-number/\n",
        "class Solution:\n",
        "  def __init__(self):\n",
        "    self.digitsTab = {\n",
        "        2:\"abc\", 3:\"def\",\n",
        "        4:\"ghi\", 5:\"jkl\", 6:\"mno\",\n",
        "        7:\"pqrs\", 8:\"tuv\", 9:\"wxyz\"\n",
        "    }\n",
        "    \n",
        "  def letterCombinations(self, digits):\n",
        "    res = []\n",
        "    for i in range(len(digits)):\n",
        "      digit = digits[i]\n",
        "      currRes = []\n",
        "      candidates = self.digitsTab[int(digit)]\n",
        "      if i == 0:\n",
        "        for j in range(len(candidates)):\n",
        "          currRes.append(candidates[j])\n",
        "      else:\n",
        "        for j in range(len(candidates)):\n",
        "          for k in range(len(res)):\n",
        "            currRes.append(res[k]+candidates[j])\n",
        "      res = currRes\n",
        "    return res\n",
        "Solution().letterCombinations(\"23\")"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gfH-sysu0OFV",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title 19. Remove Nth Node From End of List\n",
        "# https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/\n",
        "\n",
        "# Definition for singly-linked list.\n",
        "class ListNode:\n",
        "  def __init__(self, x):\n",
        "    self.val = x\n",
        "    self.next = None\n",
        "\n",
        "class Solution:\n",
        "  def removeNthFromEnd(self, head, n):\n",
        "    if head == None:\n",
        "      return None\n",
        "    nodes = []\n",
        "    currNode = head\n",
        "    while currNode != None:\n",
        "      nodes.append(currNode)\n",
        "      print(currNode.val)\n",
        "      currNode = currNode.next\n",
        "\n",
        "    nodesLen = len(nodes)\n",
        "    if nodesLen == 1 and n==1:\n",
        "      return None\n",
        "    \n",
        "    if nodesLen - n < 0:\n",
        "      return None\n",
        "    if nodesLen - n == 0:\n",
        "      return head.next\n",
        "    \n",
        "    nodes[nodesLen - n - 1].next = nodes[nodesLen - n].next\n",
        "    return head\n",
        "  \n",
        "\n",
        "def display(head):\n",
        "  res = []\n",
        "  currNode = head\n",
        "  while currNode!=None:\n",
        "    res.append(currNode.val)\n",
        "    currNode = currNode.next\n",
        "  print(res)\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "a4-33uAzwyCQ",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title 20. Valid Parentheses\n",
        "# https://leetcode.com/problems/valid-parentheses/description/\n",
        "class Solution:\n",
        "  def isValid(self, s):    \n",
        "    parenthesesEnter = {\n",
        "      '(':0, '{':1, '[':2\n",
        "    }\n",
        "    parenthesesLeave = {\n",
        "      ')':0, '}':1, ']':2\n",
        "    }\n",
        "    status = []\n",
        "    currStatus = -1\n",
        "    for ch in s:\n",
        "      if ch in ['(', '{', '[']:\n",
        "        currStatus = parenthesesEnter[ch]\n",
        "        status.append(currStatus)\n",
        "        \n",
        "      if ch in [')', '}', ']']:\n",
        "        if len(status) >=1:\n",
        "          if parenthesesLeave[ch] == currStatus:\n",
        "            status.pop()\n",
        "            if len(status)>0:\n",
        "              currStatus = status[len(status)-1]\n",
        "            else:\n",
        "              currStatus = -1\n",
        "          else:\n",
        "            return False\n",
        "        else:\n",
        "          return False\n",
        "        \n",
        "    return len(status) == 0\n",
        "\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y4sOY6397TCB",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title 21. Merge Two Sorted Lists\n",
        "# https://leetcode.com/problems/merge-two-sorted-lists/description/\n",
        "\n",
        "# Definition for singly-linked list.\n",
        "# class ListNode:\n",
        "#   def __init__(self, x):\n",
        "#     self.val = x\n",
        "#     self.next = None\n",
        "\n",
        "class Solution:\n",
        "  def mergeTwoLists(self, l1, l2):\n",
        "    currNode1, currNode2 = l1, l2\n",
        "    \n",
        "    # perform early stop\n",
        "    if currNode1 == None:\n",
        "      return currNode2\n",
        "    if currNode2 == None:\n",
        "      return currNode1\n",
        "    \n",
        "    # decide the first node\n",
        "    firstNode = None\n",
        "    if currNode1.val > currNode2.val:\n",
        "      firstNode = currNode2\n",
        "      currNode2 = currNode2.next\n",
        "    else:\n",
        "      firstNode = currNode1\n",
        "      currNode1 = currNode1.next\n",
        "    \n",
        "    currNode = firstNode\n",
        "    while currNode1!=None or currNode2 != None:\n",
        "      # just for simplicity of the logic operator\n",
        "      none1 = currNode1 == None\n",
        "      none2 = currNode2 == None\n",
        "      # either currNode2 is not none or currNode2 has less value\n",
        "      if (none1 and not none2) or (not none1 and not none2 and currNode1.val > currNode2.val):\n",
        "        currNode.next = currNode2\n",
        "        currNode = currNode2\n",
        "        currNode2 = currNode2.next\n",
        "      # either currNode1 is not none or currNode1 has less value\n",
        "      elif none2 and not none1 or (not none1 and not none2 and currNode1.val <= currNode2.val):\n",
        "        currNode.next = currNode1\n",
        "        currNode = currNode1\n",
        "        currNode1 = currNode1.next\n",
        "        \n",
        "    return firstNode\n",
        "    \n",
        "        "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "XLYzdbjMCDsG",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title 22. Generate Parentheses\n",
        "# https://leetcode.com/problems/generate-parentheses/description/\n",
        "\n",
        "class Solution:\n",
        "  def generateParenthesis(self, n):\n",
        "    if n == 1:\n",
        "      return [\"()\"]\n",
        "    \n",
        "    res = {}\n",
        "    candidates = self.generateParenthesis(n-1)\n",
        "    for cand in candidates:\n",
        "      for i in range((n-1)*2+1):\n",
        "        if i == 0:\n",
        "          key = \"()\"+cand\n",
        "        elif i == (n-1)*2:\n",
        "          key = cand + \"()\"\n",
        "        else:\n",
        "          key = cand[:i] + \"()\" + cand[i:]\n",
        "        res[key] = 1\n",
        "    return list(res.keys())\n",
        "\n",
        "  "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lnBMjAIzG2W5",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title 23. Merge k Sorted Lists\n",
        "# https://leetcode.com/problems/merge-k-sorted-lists/description/\n",
        "\n",
        "class Solution:\n",
        "    def mergeKLists(self, lists):\n",
        "      values = []\n",
        "      for aList in lists:\n",
        "        currNode = aList\n",
        "        while currNode != None:\n",
        "          values.append(currNode.val)\n",
        "          currNode = currNode.next\n",
        "          \n",
        "      values.sort()\n",
        "      if len(values) >=1:\n",
        "        currNode = ListNode(values[0])\n",
        "      else:\n",
        "        return []\n",
        "      firstNode = currNode\n",
        "      for i in range(1, len(values)):\n",
        "        currNode.next = ListNode(values[i])\n",
        "        currNode = currNode.next\n",
        "      return firstNode"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "GOKrCvBpqPBk",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title 24. Swap Nodes in Pairs\n",
        "# https://leetcode.com/problems/swap-nodes-in-pairs/description/\n",
        "\n",
        "class Solution:\n",
        "  def swapPairs(self, head):\n",
        "    firstNode, lastNode, currNode = None, None, head\n",
        "    if head == None:\n",
        "      return None\n",
        "    \n",
        "    while currNode != None:\n",
        "      node1 = currNode\n",
        "      node2 = currNode.next\n",
        "\n",
        "      # exiting\n",
        "      if node2 == None:\n",
        "        if lastNode == None:\n",
        "          return head\n",
        "        else:\n",
        "          return firstNode\n",
        "\n",
        "      if firstNode == None:\n",
        "        firstNode = node2\n",
        "      else:\n",
        "        lastNode.next = node2\n",
        "    \n",
        "      # swap node\n",
        "      currNode = node2.next\n",
        "      node2.next = node1\n",
        "      node1.next = currNode\n",
        "        \n",
        "      # keep last\n",
        "      lastNode = node1\n",
        "\n",
        "    return firstNode        \n",
        "      "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tlGglrK3OnL8",
        "colab_type": "code",
        "outputId": "4ed8ed86-1f9f-451e-b17c-8d6593fb525b",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "#@title 25. Reverse Nodes in k-Group\n",
        "# https://leetcode.com/problems/reverse-nodes-in-k-group/description/\n",
        "class Solution:\n",
        "  def reverseKGroup(self, head, k):\n",
        "    if k == 1:\n",
        "      return head\n",
        "\n",
        "    nodes = [None] * k\n",
        "    \n",
        "    firstNode, lastNode, currNode = None, None, head\n",
        "    if head == None:\n",
        "      return None\n",
        "    \n",
        "    while currNode != None:\n",
        "      iterNode = currNode\n",
        "      for i in range(k):\n",
        "        if iterNode == None:\n",
        "          if lastNode == None:\n",
        "            return head\n",
        "          else:\n",
        "            return firstNode\n",
        "        \n",
        "        nodes[i] = iterNode\n",
        "        iterNode = iterNode.next\n",
        "        \n",
        "        \n",
        "\n",
        "      if firstNode == None:\n",
        "        firstNode = nodes[k-1]\n",
        "      else:\n",
        "        lastNode.next = nodes[k-1]\n",
        "    \n",
        "      # swap node\n",
        "      currNode = nodes[k-1].next\n",
        "      for i in reversed(range(1,k)):\n",
        "        nodes[i].next = nodes[i-1]\n",
        "      nodes[0].next = currNode\n",
        "        \n",
        "      # keep last\n",
        "      lastNode = nodes[0]\n",
        "\n",
        "    return firstNode"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[1, 1, 6]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 8
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "rfME0qYmLAFv",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title 26. Remove Duplicates from Sorted Array\n",
        "# https://leetcode.com/problems/remove-duplicates-from-sorted-array/description/\n",
        "\n",
        "class Solution:\n",
        "  def removeDuplicates(self, nums):\n",
        "    lenNums = len(nums)\n",
        "    if lenNums ==0:\n",
        "      return 0\n",
        "        \n",
        "    val, counter, p = nums[0], 1, 1\n",
        "    for i in range(1,lenNums):\n",
        "      if val<nums[p]:\n",
        "        counter += 1\n",
        "        val = nums[p]\n",
        "        p += 1\n",
        "      else:\n",
        "        del nums[p]\n",
        "    return counter"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "TvrUkyvR3uFH",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title 27. Remove Element\n",
        "# https://leetcode.com/problems/remove-element/description/\n",
        "class Solution:\n",
        "  def removeElement(self, nums, val):\n",
        "    \"\"\"\n",
        "    :type nums: List[int]\n",
        "    :type val: int\n",
        "    :rtype: int\n",
        "    \"\"\"\n",
        "    p = 0\n",
        "    while p<len(nums):\n",
        "      if nums[p] == val:\n",
        "        del nums[p]\n",
        "      else:\n",
        "        p += 1\n",
        "    return len(nums)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ALGc3sBi26o_",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title 28. Implement strStr()\n",
        "# https://leetcode.com/problems/implement-strstr/description/\n",
        "class Solution:\n",
        "  def strStr(self, haystack, needle):\n",
        "    \"\"\"\n",
        "    :type haystack: str\n",
        "    :type needle: str\n",
        "    :rtype: int\n",
        "    \"\"\"\n",
        "    lenHaystack = len(haystack)\n",
        "    lenNeedle = len(needle)\n",
        "    for i in range(lenHaystack-lenNeedle+1):\n",
        "      if haystack[i:i+lenNeedle] == needle:\n",
        "        return i\n",
        "    return -1"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "w-rkZhPg4VUH",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title 29. Divide Two Integers\n",
        "# https://leetcode.com/problems/divide-two-integers/description/\n",
        "class Solution:\n",
        "  def divide(self, dividend, divisor):\n",
        "    \"\"\"\n",
        "    :type dividend: int\n",
        "    :type divisor: int\n",
        "    :rtype: int\n",
        "    \"\"\"\n",
        "          \n",
        "    sign = True\n",
        "    if dividend<0:\n",
        "      sign = False\n",
        "      dividend = -dividend\n",
        "    if divisor<0:\n",
        "      sign = not sign\n",
        "      divisor = -divisor\n",
        "      \n",
        "    result = 0\n",
        "    while dividend >= divisor:\n",
        "      dividend -= divisor\n",
        "      result += 1\n",
        "\n",
        "    if sign:\n",
        "      return result\n",
        "    else:\n",
        "      return -result\n",
        "class Solution:\n",
        "  def divide(self, dividend, divisor):\n",
        "    \"\"\"\n",
        "    :type dividend: int\n",
        "    :type divisor: int\n",
        "    :rtype: int\n",
        "    \"\"\"    \n",
        "    if (dividend>0)==(divisor>0):\n",
        "      sign=1\n",
        "    else:\n",
        "      sign=0\n",
        "        \n",
        "    if dividend<=0:\n",
        "      dividend=-dividend\n",
        "    if divisor<=0:\n",
        "      divisor=-divisor\n",
        "\n",
        "    mult=[divisor]\n",
        "    c=divisor\n",
        "    \n",
        "    while c+c<=dividend:\n",
        "      c+=c\n",
        "      mult.append(c)\n",
        "    \n",
        "    i, res =0, 0\n",
        "    while dividend>=divisor:\n",
        "      i += 1\n",
        "      res += res\n",
        "      if dividend>=mult[-i]:\n",
        "        dividend=dividend-mult[-i]\n",
        "        res += 1\n",
        "    \n",
        "    while i<len(mult):\n",
        "      res += res\n",
        "      i += 1\n",
        "    \n",
        "    if not sign:\n",
        "      res=-res\n",
        "        \n",
        "    if res>2147483647 or res<-2147483648:\n",
        "      return 2147483647\n",
        "    else:\n",
        "      return res\n",
        "        "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "_QeLlnDYjiqT",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title 37. Sudoku Solver\n",
        "# https://leetcode.com/problems/sudoku-solver/description/\n",
        "class Solution:\n",
        "    def __init__(self):\n",
        "        self.boardList = '123456789'\n",
        "        self.rows = []\n",
        "        self.cols = []\n",
        "        self.blks = []\n",
        "        self.done = False\n",
        "        for i in range(9):\n",
        "            currRow = []\n",
        "            currCol = []\n",
        "            for j in range(9):\n",
        "                currRow.append(False)\n",
        "                currCol.append(False)                    \n",
        "            self.rows.append(currRow)\n",
        "            self.cols.append(currCol)\n",
        "        \n",
        "        for i in range(3):\n",
        "            currBlk1 = []\n",
        "            for j in range(3):\n",
        "                currBlk2 = []\n",
        "                for k in range(9):\n",
        "                    currBlk2.append(False)\n",
        "                currBlk1.append(currBlk2)\n",
        "            self.blks.append(currBlk1)\n",
        "    \n",
        "    \n",
        "    def solve(self, board, r, c):\n",
        "        if (self.done):\n",
        "            return\n",
        "        \n",
        "        if (r == 9):\n",
        "            self.done = True\n",
        "            return\n",
        "\n",
        "\n",
        "        nextr = r;\n",
        "        nextc = c + 1;\n",
        "        if (nextc == 9):\n",
        "            nextr += 1\n",
        "            nextc = 0\n",
        "        \n",
        "\n",
        "        if (board[r][c] == '.'):\n",
        "            for i in range(9):\n",
        "            \n",
        "                if (not self.rows[r][i] and \n",
        "                    not self.cols[c][i] and \n",
        "                    not self.blks[r // 3][c // 3][i]):\n",
        "                    self.rows[r][i] = True\n",
        "                    self.cols[c][i] = True\n",
        "                    self.blks[r // 3][c // 3][i] = True\n",
        "                    board[r][c] = self.boardList[i]\n",
        "\n",
        "                    self.solve(board, nextr, nextc)\n",
        "\n",
        "                    if (not self.done):\n",
        "                        board[r][c] = '.'\n",
        "                        self.rows[r][i] = False\n",
        "                        self.cols[c][i] = False\n",
        "                        self.blks[r // 3][c // 3][i] = False\n",
        "\n",
        "        else:\n",
        "            self.solve(board, nextr, nextc)\n",
        "        \n",
        "    \n",
        "    \n",
        "    def solveSudoku(self, board):\n",
        "        for i in range(9):\n",
        "            for j in range(9):\n",
        "                if board[i][j] != '.':\n",
        "                    ch = self.boardList.find(board[i][j])\n",
        "                    self.rows[i][ch] = True\n",
        "                    self.cols[j][ch] = True\n",
        "                    self.blks[i // 3][j // 3][ch] = True\n",
        "        \n",
        "        self.solve(board, 0, 0)\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "XYL1aQ-WCDTM",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title 38. Count and Say\n",
        "# https://leetcode.com/problems/count-and-say/description/\n",
        "\n",
        "# The description is confusing\n",
        "# https://oeis.org/A005150\n",
        "class Solution:\n",
        "  def countAndSay(self, n):\n",
        "    p = \"1\"\n",
        "    seq = [1]\n",
        "    while (n > 1):\n",
        "      q = ''\n",
        "      idx = 0 # Index\n",
        "      l = len(p) # Length\n",
        "      while idx < l:\n",
        "        start = idx\n",
        "        idx = idx + 1\n",
        "        while idx < l and p[idx] == p[start]:\n",
        "          idx = idx + 1\n",
        "        q = q + str(idx-start) + p[start]\n",
        "      n, p = n - 1, q\n",
        "      seq.append(str(p))\n",
        "    return str(seq[len(seq)-1])\n",
        "\n",
        "for i in range(1,20+1):\n",
        "  print(i, Solution().countAndSay(i))\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "U9rRQbK51a-h",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title 48. Rotate Image\n",
        "# https://leetcode.com/problems/rotate-image/description/\n",
        "class Solution:\n",
        "  def rotate(self, matrix):\n",
        "    m = len(matrix)\n",
        "    if m <= 1:\n",
        "      return\n",
        "\n",
        "    # transpose\n",
        "    for i in range(m-1):\n",
        "      for j in range(i+1,m):\n",
        "        i1, j1 = i, j\n",
        "        i2, j2 = j, i\n",
        "        if not(i1==i2 and j1==j2):\n",
        "          tmp = matrix[i1][j1]\n",
        "          matrix[i1][j1] = matrix[i2][j2]\n",
        "          matrix[i2][j2] = tmp\n",
        "    \n",
        "    # flip\n",
        "    for i in range(m):\n",
        "      for j in range(m//2):\n",
        "        i1, j1 = i, j\n",
        "        i2, j2 = i, m-1-j\n",
        "        if j1 != j2:\n",
        "          tmp = matrix[i1][j1]\n",
        "          matrix[i1][j1] = matrix[i2][j2]\n",
        "          matrix[i2][j2] = tmp\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "yJTl9SJnl6mj",
        "colab_type": "code",
        "outputId": "bf940e55-77d8-48d2-a0fa-2c20cd82b584",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "#@title 93. Restore IP Addresses\n",
        "# https://leetcode.com/problems/restore-ip-addresses/\n",
        "import copy\n",
        "\n",
        "class Solution:\n",
        "  \n",
        "  def isValidDigits(self, s):\n",
        "    if len(s) > 0 and len(s) <= 3:\n",
        "      if int(s) >= 0 and int(s) < 256 and str(int(s)) == s:\n",
        "        return True\n",
        "    return False\n",
        "    \n",
        "  def restoreIpAddresses(self, s: str):\n",
        "    candidates = [[s]]\n",
        "\n",
        "    for level in range(4):\n",
        "      nextCandidates = []\n",
        "      for candidate in candidates:\n",
        "        lastIPBlocks = candidate[-1]\n",
        "        for numLen in range(1, 4):\n",
        "          cutIPBlock = lastIPBlocks[0:numLen]\n",
        "          if self.isValidDigits(cutIPBlock):\n",
        "            newCandidate = copy.deepcopy(candidate)\n",
        "            newCandidate[-1] = cutIPBlock\n",
        "            newCandidate.append(lastIPBlocks[numLen:])\n",
        "            if level == 3:\n",
        "              if len(newCandidate[-1]) == 0:\n",
        "                #print(newCandidate[-1], newCandidate)\n",
        "                nextCandidates.append(\".\".join(newCandidate[0:4]))\n",
        "              else:\n",
        "                pass\n",
        "            else:\n",
        "              nextCandidates.append(newCandidate)\n",
        "            \n",
        "      candidates = nextCandidates\n",
        "    \n",
        "    return list(set(candidates))\n",
        "  \n",
        "#Solution().restoreIpAddresses(\"0000\")\n",
        "Solution().restoreIpAddresses(\"010010\")\n",
        "\n",
        "#Solution().restoreIpAddresses(\"25525511135\")"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "['0.10.0.10', '0.100.1.0']"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 24
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2oBf62YEkJpp",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title 112. Path Sum\n",
        "# https://leetcode.com/problems/path-sum/description/\n",
        "\n",
        "# Definition for a binary tree node.\n",
        "# class TreeNode(object):\n",
        "#     def __init__(self, x):\n",
        "#         self.val = x\n",
        "#         self.left = None\n",
        "#         self.right = None\n",
        "\n",
        "class Solution(object):\n",
        "    def hasPathSum(self, root, sum):\n",
        "        if root ==None:\n",
        "            return False\n",
        "\n",
        "        result = self._getPathSums(root, 0)\n",
        "\n",
        "        for i in range(len(result)):\n",
        "            if result[i] == sum:\n",
        "                return True\n",
        "        return False\n",
        "    \n",
        "    \n",
        "    def _getPathSums(self, root, prevSum):\n",
        "\n",
        "        \n",
        "        # leaf node\n",
        "        if root == None:\n",
        "            return [prevSum]\n",
        "        if root.left == None and root.right == None:\n",
        "            return [prevSum + root.val]\n",
        "        else:\n",
        "            result = []\n",
        "            if root.left != None:\n",
        "                l = self._getPathSums(root.left, prevSum+root.val)\n",
        "                for i in range(len(l)):\n",
        "                    result.append(l[i])\n",
        "            if root.right != None:\n",
        "                l = self._getPathSums(root.right, prevSum+root.val)\n",
        "                for i in range(len(l)):\n",
        "                    result.append(l[i])\n",
        "                \n",
        "            return result\n",
        "            \n",
        "        "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "A9Pf6kJEj7ul",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title 128. Longest Consecutive Sequence\n",
        "# https://leetcode.com/problems/longest-consecutive-sequence/description/\n",
        "\n",
        "class DoubleLink(object):\n",
        "    def __init__(self, val):\n",
        "        self.val = val\n",
        "        self.left = None\n",
        "        self.right = None\n",
        "        \n",
        "class Solution(object):\n",
        "    def __init__(self):\n",
        "        self.cache = {}\n",
        "    \n",
        "    def getLength(self, node):\n",
        "        result = 0\n",
        "        currNode = node\n",
        "        while currNode !=None:\n",
        "            result += 1\n",
        "            currNode = currNode.right\n",
        "        return result\n",
        "    \n",
        "    def longestConsecutive(self, nums):\n",
        "        for i in nums:\n",
        "            node = DoubleLink(i)\n",
        "            self.cache[i] = node\n",
        "            if i-1 in self.cache:\n",
        "                self.cache[i-1].right = node\n",
        "                self.cache[i].left = self.cache[i-1]\n",
        "            if i+1 in self.cache:\n",
        "                self.cache[i+1].left = node\n",
        "                self.cache[i].right = self.cache[i+1]\n",
        "        \n",
        "        maxLength = 0\n",
        "        for i in nums:\n",
        "            if self.cache[i].left == None:\n",
        "                currLength = self.getLength(self.cache[i])\n",
        "                if currLength > maxLength:\n",
        "                    maxLength = currLength\n",
        "        return maxLength\n",
        "        "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "we554o30Iwx_",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title 133. Clone Graph\n",
        "# https://leetcode.com/problems/clone-graph/description/\n",
        "  \n",
        "# Definition for a undirected graph node\n",
        "# class UndirectedGraphNode:\n",
        "#   def __init__(self, x):\n",
        "#     self.label = x\n",
        "#     self.neighbors = []\n",
        "\n",
        "class Solution:\n",
        "  # param node, a undirected graph node\n",
        "  # return a undirected graph node\n",
        "  def __init__(self):\n",
        "    self.visited = {}\n",
        "    self.cloned = {}\n",
        "        \n",
        "  def cloneNode(self, node):\n",
        "    if node.label in self.visited:\n",
        "      return self.cloned[node.label]\n",
        "\n",
        "    newNode = UndirectedGraphNode(node.label)  \n",
        "    self.visited[node.label] = True\n",
        "    self.cloned[newNode.label] = newNode\n",
        "    for i in range(len(node.neighbors)):\n",
        "      newNode.neighbors.append(self.cloneNode(node.neighbors[i]))\n",
        "      \n",
        "    return newNode\n",
        "        \n",
        "  def cloneGraph(self, node):\n",
        "    if node==None:\n",
        "      return None\n",
        "    if node=={}:\n",
        "      return {}\n",
        "       \n",
        "    return self.cloneNode(node)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8RtMuh53wzde",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title 136. Single Number\n",
        "# https://leetcode.com/problems/single-number/\n",
        "class Solution:\n",
        "  def singleNumber(self, nums):\n",
        "    res = {}\n",
        "    iRes = 0\n",
        "    for i in nums:\n",
        "      if not i in res:\n",
        "        res[i] = 1\n",
        "        iRes += i\n",
        "      else:\n",
        "        iRes -= i\n",
        "    return iRes"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "cMw6cg89yUcu",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title 138. Copy List with Random Pointer\n",
        "# https://leetcode.com/problems/copy-list-with-random-pointer/description/\n",
        "\n",
        "# Definition for singly-linked list with a random pointer.\n",
        "# class RandomListNode(object):\n",
        "#   def __init__(self, x):\n",
        "#     self.label = x\n",
        "#     self.next = None\n",
        "#     self.random = None\n",
        "\n",
        "class Solution(object):\n",
        "  def copyRandomList(self, head):\n",
        "    \"\"\"\n",
        "    :type head: RandomListNode\n",
        "    :rtype: RandomListNode\n",
        "    \"\"\"\n",
        "    currNode = head\n",
        "    if head == None:\n",
        "      return None\n",
        "    \n",
        "    clonedNodes = {}\n",
        "    clonedArray = []\n",
        "    currNode = head\n",
        "    while True:\n",
        "      nodeId = id(currNode)\n",
        "      clonedNode = RandomListNode(currNode.label)\n",
        "      if currNode.random != None:\n",
        "        clonedNode.random = id(currNode.random)\n",
        "      else:\n",
        "        clonedNode.random = None\n",
        "    \n",
        "      clonedNodes[nodeId] = clonedNode\n",
        "      clonedArray.append(clonedNode)\n",
        "      if currNode.next == None:\n",
        "        break\n",
        "      currNode = currNode.next\n",
        "        \n",
        "    for i in range(len(clonedArray)):\n",
        "      currNode = clonedArray[i]\n",
        "      if i < len(clonedArray)-1:\n",
        "        currNode.next = clonedArray[i+1]\n",
        "      if currNode.random != None:\n",
        "        currNode.random = clonedNodes[currNode.random]\n",
        "        \n",
        "    return clonedArray[0]"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "paysSjH4kd4R",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title 141. Linked List Cycle\n",
        "# https://leetcode.com/problems/linked-list-cycle/description/\n",
        "\n",
        "# Definition for singly-linked list.\n",
        "# class ListNode(object):\n",
        "#     def __init__(self, x):\n",
        "#         self.val = x\n",
        "#         self.next = None\n",
        "\n",
        "class Solution(object):\n",
        "    def __init__(self):\n",
        "        self.visited = {}\n",
        "        \n",
        "    def hasCycle(self, head):\n",
        "        if head == None:\n",
        "            return False\n",
        "        if id(head) in self.visited:\n",
        "            return True\n",
        "        else:\n",
        "            self.visited[id(head)] = id(head)\n",
        "            return self.hasCycle(head.next)\n",
        "        "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "yLLzCcWDkVlt",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title 142. Linked List Cycle II\n",
        "# https://leetcode.com/problems/linked-list-cycle-ii/description/\n",
        "\n",
        "# Definition for singly-linked list.\n",
        "# class ListNode(object):\n",
        "#     def __init__(self, x):\n",
        "#         self.val = x\n",
        "#         self.next = None\n",
        "\n",
        "class Solution(object):\n",
        "    def __init__(self):\n",
        "        self.visited = {}\n",
        "        \n",
        "    def detectCycle(self, head):\n",
        "        if head == None:\n",
        "            return None\n",
        "        else:\n",
        "            if id(head) in self.visited:\n",
        "                return head\n",
        "            else:\n",
        "                self.visited[id(head)] = id(head)\n",
        "                return self.detectCycle(head.next)\n",
        "\n",
        "            "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Qe3IovVHyH1G",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title 187. Repeated DNA Sequences\n",
        "# https://leetcode.com/problems/repeated-dna-sequences/\n",
        "\n",
        "class Solution:\n",
        "  def findRepeatedDnaSequences(self, s: str) -> List[str]:\n",
        "    occurrences, dup = {}, {}\n",
        "    for i in range(9, len(s)):\n",
        "      currSeq = s[i-9:i+1]\n",
        "      if currSeq in occurrences:\n",
        "        dup[currSeq] = 1\n",
        "      else:\n",
        "        occurrences[currSeq] = 1 \n",
        "    return list(dup.keys())"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "CQ-RurvpKEJx",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title 189. Rotate Array\n",
        "# https://leetcode.com/problems/rotate-array/description/\n",
        "class Solution(object):\n",
        "  def rotate(self, nums, k):\n",
        "    k = k % len(nums)\n",
        "    beginPart = nums[-k:]\n",
        "    endPart = nums[:-k]\n",
        "    p = 0\n",
        "    for i in range(len(beginPart)):\n",
        "      nums[p] = beginPart[i]\n",
        "      p+=1\n",
        "    for i in range(len(endPart)):\n",
        "      nums[p] = endPart[i]\n",
        "      p+=1\n",
        "      "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "1AowgIFci-OF",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title 200. Number of Islands\n",
        "# https://leetcode.com/problems/number-of-islands/description/\n",
        "\n",
        "class Solution:\n",
        "\n",
        "    def numIslands(self, grid):\n",
        "        islandId = 0\n",
        "        islands = {}\n",
        "        for y in range(len(grid)):\n",
        "            line = grid[y]\n",
        "            for x in range(len(line)):\n",
        "                if grid[y][x] == \"1\":\n",
        "                    upLink = (y >= 1 and grid[y - 1][x] != \"0\")\n",
        "                    leftLink = (x >= 1 and grid[y][x - 1] != \"0\")\n",
        "                    \n",
        "                    if not upLink and not leftLink:\n",
        "                        islandId += 1\n",
        "                        islands[islandId] = [(x,y)]\n",
        "                        grid[y][x] = islandId\n",
        "                    else:\n",
        "                        upLinkVal, leftLinkVal = 0, 0\n",
        "                        if upLink:\n",
        "                            upLinkVal = grid[y-1][x]\n",
        "                        if leftLink:\n",
        "                            leftLinkVal = grid[y][x-1]\n",
        "                        \n",
        "                        if upLink and not leftLink:\n",
        "                            grid[y][x] = grid[y-1][x]\n",
        "                            #print(x,y)\n",
        "                            #print(grid)\n",
        "                            islands[grid[y][x]].append((x,y))\n",
        "                            \n",
        "                        if leftLink and not upLink:\n",
        "                            grid[y][x] = grid[y][x-1]\n",
        "                            islands[grid[y][x]].append((x,y))\n",
        "                        \n",
        "                        if leftLink and upLink:\n",
        "                            if leftLinkVal == upLinkVal:\n",
        "                                grid[y][x] = grid[y-1][x]\n",
        "                                islands[grid[y][x]].append((x,y))\n",
        "                            else:\n",
        "                                # merge process\n",
        "                                grid[y][x] = leftLinkVal\n",
        "                                for p in islands[upLinkVal]:\n",
        "                                    grid[p[1]][p[0]] = leftLinkVal\n",
        "                                        \n",
        "                                islands[leftLinkVal].extend(islands[upLinkVal])\n",
        "                                islands[leftLinkVal].append((x,y))\n",
        "                                del islands[upLinkVal]\n",
        "\n",
        "        return len(islands.keys())"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "GE7Ddw2yDTvD",
        "colab_type": "code",
        "outputId": "583ec344-f56f-49d2-85b7-b1f3dc7412c0",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "#@title 202. Happy Number\n",
        "#https://leetcode.com/problems/happy-number/description/\n",
        "\n",
        "class Solution(object):\n",
        "    \n",
        "  def isHappy(self, n):\n",
        "    seen = []\n",
        "    while n != 1:\n",
        "      _sum = 0\n",
        "      while n != 0:\n",
        "        _sum += (n%10) * (n%10)\n",
        "        n = n/10\n",
        "      n = _sum;\n",
        "      if n in seen:\n",
        "        return False\n",
        "      seen.append(n)\n",
        "    return True"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "0"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 3
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tq32RBnfImQE",
        "colab_type": "code",
        "outputId": "1a4df253-632d-4ecc-e51a-c5f78f2c9e77",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "#@title 221. Maximal Square\n",
        "# https://leetcode.com/problems/maximal-square/\n",
        "class Solution:\n",
        "  def maximalSquare(self, matrix):\n",
        "    \n",
        "    possiblePos = []\n",
        "    maxSquare = 1\n",
        "    for i in range(len(matrix)):\n",
        "      row = matrix[i]\n",
        "      for j in range(len(row)):\n",
        "        if int(matrix[i][j]) == 1:\n",
        "          possiblePos.append([i,j])\n",
        "    if len(possiblePos) == 0:\n",
        "        return 0\n",
        "          \n",
        "    while len(possiblePos) >0:\n",
        "      nextPossiblePos = []\n",
        "      for pos in possiblePos:\n",
        "        sum = maxSquare ** 2\n",
        "        try:\n",
        "          for i in range(maxSquare+1):\n",
        "            sum += int(matrix[pos[0]+maxSquare][pos[1]+i])\n",
        "          for i in range(maxSquare+1):\n",
        "            sum += int(matrix[pos[0]+i][pos[1]+maxSquare])\n",
        "          sum -= int(matrix[pos[0]+maxSquare][pos[1]+maxSquare])\n",
        "        except:\n",
        "          pass\n",
        "        if sum == (maxSquare+1) ** 2:\n",
        "          nextPossiblePos.append(pos)\n",
        "          \n",
        "      possiblePos = nextPossiblePos\n",
        "      if len(nextPossiblePos) >0:\n",
        "        maxSquare += 1\n",
        "    return maxSquare**2\n",
        "m = [\n",
        "[1,1,1,1,1],\n",
        "[1,1,1,1,1],\n",
        "[1,1,1,1,1],\n",
        "[1,1,1,1,1],\n",
        "[1,1,1,1,1]]\n",
        "Solution().maximalSquare(m)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "25"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 24
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ZUUpF4NFZQjG",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title 403. Frog Jump\n",
        "\n",
        "# https://leetcode.com/problems/frog-jump/description/\n",
        "\n",
        "class Solution:\n",
        "  def __init__(self):\n",
        "    self.memory = {}\n",
        "    \n",
        "  def canCross(self, stones):\n",
        "    return self._canCross(stones,0,0)\n",
        "    \n",
        "  def _canCross(self, stones, start, k):\n",
        "    if (start, k) in self.memory:\n",
        "      return self.memory[(start, k)]\n",
        "    \n",
        "    if start == len(stones)-1:\n",
        "      self.memory[(start, k)] = True\n",
        "      return True\n",
        "  \n",
        "    candidates = []\n",
        "    for i in range(start+1, len(stones)):\n",
        "      jumpLen = stones[i] - stones[start]\n",
        "      if jumpLen > k + 1:\n",
        "        break;\n",
        "      else:\n",
        "        if abs(jumpLen - k) <= 1:\n",
        "          candidates.append([i, jumpLen])\n",
        "\n",
        "    if len(candidates) == 0:\n",
        "      self.memory[(start, k)] = False\n",
        "      return False\n",
        "    \n",
        "    candidates = list(reversed(candidates))\n",
        "    #print(start, len(candidates))\n",
        "    res = False\n",
        "    for candidate in candidates:\n",
        "      if self._canCross(stones, candidate[0], candidate[1]):\n",
        "        res = True\n",
        "        break\n",
        "    \n",
        "    self.memory[(start, k)] = res\n",
        "    return res\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "CmkDDfjGres0",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title 412. Fizz Buzz\n",
        "# https://leetcode.com/problems/fizz-buzz/description/\n",
        "\n",
        "class Solution:\n",
        "  def fizzBuzz(self, n):\n",
        "    \"\"\"\n",
        "    :type n: int\n",
        "    :rtype: List[str]\n",
        "    \"\"\"\n",
        "    ans = []\n",
        "    for i in range(1,n+1):\n",
        "      res = \"\"\n",
        "      if i % 3 == 0:\n",
        "        res += \"Fizz\"\n",
        "      if i % 5 == 0:\n",
        "        res += \"Buzz\"\n",
        "      if res == \"\":\n",
        "        res = str(i)\n",
        "      ans.append(res)\n",
        "    return ans\n",
        "        "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tzn-oHOeUiOX",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title 417. Pacific Atlantic Water Flow\n",
        "# https://leetcode.com/problems/pacific-atlantic-water-flow/description/\n",
        "\n",
        "class Solution:\n",
        "  def __init__(self):\n",
        "    self.PAC = 1\n",
        "    self.ATL = 2\n",
        "    self.BTH = 3\n",
        "    self.NA = 0\n",
        "    self.landmap = []\n",
        "    self.blockmap = []\n",
        "    self.blocks = {}\n",
        "    self.reorderedBlocks = {}\n",
        "    self.result = {}\n",
        "    \n",
        "  def connected(self, i, j, matrix):\n",
        "    res = []\n",
        "    if i>0 and matrix[i][j] == matrix[i-1][j]:\n",
        "      res.append(self.blockmap[i-1][j])\n",
        "    if j>0 and matrix[i][j] == matrix[i][j-1]:\n",
        "      res.append(self.blockmap[i][j-1])\n",
        "    return list(set(res))\n",
        "      \n",
        "  \n",
        "  def init(self, matrix):\n",
        "    res = []\n",
        "    m, n = len(matrix), len(matrix[0])\n",
        "    \n",
        "    for i in range(m):\n",
        "      row = []\n",
        "      row2 = []\n",
        "      for j in range(n):\n",
        "        if (i==0 and j==n-1) or (i==m-1 and j==0):\n",
        "          row.append(self.BTH)\n",
        "          self.result[str(i)+\"_\"+str(j)] = [i,j]\n",
        "        elif i==0 or j==0:\n",
        "          row.append(self.PAC)\n",
        "        elif i==m-1 or j==n-1:\n",
        "          row.append(self.ATL)\n",
        "        else:\n",
        "          row.append(self.NA)\n",
        "        row2.append(0)\n",
        "         \n",
        "      res.append(row)\n",
        "      self.blockmap.append(row2)\n",
        "      \n",
        "    self.landmap = res\n",
        "    \n",
        "    blockId = 0\n",
        "    for i in range(m):\n",
        "      row = []\n",
        "      for j in range(n):\n",
        "        blockIds = self.connected(i,j, matrix)\n",
        "        blockNum = len(blockIds)\n",
        "        if blockNum == 0:\n",
        "          # newblock\n",
        "          blockId += 1\n",
        "          self.blocks[blockId] = [matrix[i][j], [i,j]]\n",
        "          self.blockmap[i][j] = blockId\n",
        "        elif blockNum == 1:\n",
        "          # append\n",
        "          self.blocks[blockIds[0]].append([i,j])\n",
        "          self.blockmap[i][j] = blockIds[0]\n",
        "        elif blockNum > 1:\n",
        "          # merge and set\n",
        "          self.blockmap[i][j] = blockIds[0]\n",
        "          self.blocks[blockIds[0]].append([i,j])\n",
        "          \n",
        "          for j in range(1, len(blockIds)):\n",
        "            self.blocks[blockIds[0]].extend(self.blocks[blockIds[j]][1:])\n",
        "            currBlockId = blockIds[j]\n",
        "            \n",
        "            for k in range(1, len(self.blocks[currBlockId])):\n",
        "              currCoordinate = self.blocks[currBlockId][k]\n",
        "              self.blockmap[currCoordinate[0]][currCoordinate[1]] = blockIds[0]\n",
        "            self.blocks.pop(blockIds[j])\n",
        "    \n",
        "  def checkSurrounding(self, coordinate, matrix):\n",
        "    m, n = len(self.landmap), len(self.landmap[0])\n",
        "    \n",
        "    res = []\n",
        "    x, y = coordinate[0], coordinate[1]\n",
        "    if x>0 and self.landmap[x-1][y]>0 and matrix[x][y] >= matrix[x-1][y]:\n",
        "      res.append(self.landmap[x-1][y])\n",
        "      \n",
        "    if y>0 and self.landmap[x][y-1]>0 and matrix[x][y] >= matrix[x][y-1]:\n",
        "      res.append(self.landmap[x][y-1])\n",
        "    \n",
        "    if x<m-1 and self.landmap[x+1][y]>0 and matrix[x][y] >= matrix[x+1][y]:\n",
        "      res.append(self.landmap[x+1][y])\n",
        "    \n",
        "    if y<n-1 and self.landmap[x][y+1]>0 and matrix[x][y] >= matrix[x][y+1]:\n",
        "      res.append(self.landmap[x][y+1])\n",
        "    \n",
        "    return list(set(res))\n",
        "      \n",
        "  \n",
        "  def pacificAtlantic(self, matrix):\n",
        "    if matrix == []:\n",
        "      return []\n",
        "\n",
        "    m, n = len(matrix), len(matrix[0])\n",
        "    if m==1 or n==1:\n",
        "      res = []\n",
        "      for i in range(m):\n",
        "        for j in range(n):\n",
        "          res.append([i,j])\n",
        "      return res\n",
        "    \n",
        "    self.init(matrix)\n",
        "    self.reorderedBlocks = {}\n",
        "    \n",
        "    for key in self.blocks.keys():\n",
        "      height = self.blocks[key][0]\n",
        "      if height in self.reorderedBlocks:\n",
        "        self.reorderedBlocks[height].append(self.blocks[key][1:])\n",
        "      else:\n",
        "        self.reorderedBlocks[height]= [self.blocks[key][1:]]\n",
        "    \n",
        "    \n",
        "    self.blocks = self.reorderedBlocks\n",
        "    heights = sorted(self.blocks.keys())\n",
        "    \n",
        "    for height in heights:\n",
        "      \n",
        "      currBlocks = self.blocks[height]\n",
        "      for block in currBlocks:\n",
        "        pacific = self.NA\n",
        "        atlantic = self.NA\n",
        "        \n",
        "        for coordinate in block:\n",
        "          \n",
        "          surroundings = self.checkSurrounding(coordinate, matrix)\n",
        "          \n",
        "          if self.landmap[coordinate[0]][coordinate[1]] == self.ATL or self.ATL in surroundings:\n",
        "            atlantic = self.ATL\n",
        "          if self.landmap[coordinate[0]][coordinate[1]] == self.PAC or self.PAC in surroundings:\n",
        "            pacific = self.PAC\n",
        "          if self.landmap[coordinate[0]][coordinate[1]] == self.BTH or self.BTH in surroundings:\n",
        "            atlantic = self.ATL\n",
        "            pacific = self.PAC\n",
        "\n",
        "          \n",
        "        for coordinate in block:\n",
        "          self.landmap[coordinate[0]][coordinate[1]] = atlantic+pacific\n",
        "          if atlantic+pacific==self.BTH:\n",
        "            self.result[str(coordinate[0])+\"_\"+str(coordinate[1])] = coordinate\n",
        "            #self.result.append(coordinate)\n",
        "\n",
        "    return list(self.result.values())\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "NqZmJwdYUiRO",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title 443. String Compression\n",
        "# https://leetcode.com/problems/string-compression/\n",
        "\n",
        "class Solution:\n",
        "  def compress(self, chars):\n",
        "    print(chars)\n",
        "    res = []\n",
        "    prevCh = \"\"\n",
        "    counter = 0\n",
        "    marked = False\n",
        "    for i in range(len(chars)):\n",
        "      ch = chars[i]\n",
        "      if ch == prevCh:\n",
        "        counter += 1\n",
        "        marked = True\n",
        "        if counter==2:\n",
        "          res.append(str(counter))\n",
        "        else:\n",
        "          res[-1] = str(counter)\n",
        "      else:\n",
        "        counter = 1\n",
        "        res.append(ch)\n",
        "        marked = False\n",
        "      prevCh = ch\n",
        "    if counter>1 and not marked:\n",
        "      if counter==2:\n",
        "        res.append(str(counter))\n",
        "      else:\n",
        "        res[-1] = str(counter)\n",
        "\n",
        "    res = \"\".join(res)\n",
        "    return len(res)\n",
        "    "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "_t9GvN_khoOa",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title 488. Zuma Game\n",
        "# https://leetcode.com/problems/zuma-game/description/\n",
        "\n",
        "class Solution:\n",
        "    def __init__(self):\n",
        "      self.memory = {}\n",
        "      self.simplifiedMemory = {}\n",
        "      self.perm = []\n",
        "      self.EXTRA_LARGE = 9999\n",
        "      \n",
        "    def findMinStep(self, board, hand):\n",
        "\n",
        "      self.perm = []\n",
        "      self.permutations(hand)\n",
        "      self.perm = list(set(self.perm))\n",
        "      \n",
        "      \n",
        "      minStep = self.EXTRA_LARGE\n",
        "      for i in range(len(self.perm)):\n",
        "        currHandOrder = self.perm[i]\n",
        "\n",
        "        res = self._findMinStep(board, currHandOrder, 0)\n",
        "        if res > 0:\n",
        "          minStep = min(minStep, res)\n",
        "          \n",
        "      if minStep == self.EXTRA_LARGE:\n",
        "        return -1\n",
        "      return minStep\n",
        "          \n",
        "\n",
        "          \n",
        "    def _findMinStep(self, board, currHandOrder, currLen):\n",
        "      if len(board) == 0:\n",
        "        return currLen\n",
        "      \n",
        "      if len(board) >0 and len(currHandOrder)==0:\n",
        "        return -1\n",
        "      \n",
        "      #currHandOrderKey = \"\".join(sorted(list(currHandOrder)))\n",
        "      \n",
        "      currHandOrderKey = currHandOrder\n",
        "      \n",
        "      currKey = board + \"_\"+ currHandOrderKey\n",
        "      if currKey in self.memory:\n",
        "        return self.memory[currKey]\n",
        "      \n",
        "      currHand = currHandOrder[0]\n",
        "      localMinStep = self.EXTRA_LARGE\n",
        "      for k in range(len(board)+1):        \n",
        "        newBoard = board[:k] + currHand + board[k:]\n",
        "        simplified, newBoard2 = self.simplify(newBoard)\n",
        "          \n",
        "        #if simplified:\n",
        "        if len(newBoard2) == 0:\n",
        "          localMinStep = min(localMinStep, currLen + 1)            \n",
        "        else:\n",
        "          res = self._findMinStep(newBoard2, currHandOrder[1:], currLen + 1)\n",
        "          if res > 0:\n",
        "            localMinStep = min(localMinStep, res)\n",
        "        #else:\n",
        "        #  if len(list(set(newBoard))) == 1:\n",
        "        #    res = self._findMinStep(newBoard2, currHandOrder[1:], currLen + 1)\n",
        "        #    localMinStep = min(localMinStep, res)\n",
        "\n",
        "      if localMinStep!= self.EXTRA_LARGE and localMinStep > 0:\n",
        "        self.memory[currKey] = localMinStep\n",
        "        return localMinStep\n",
        "      \n",
        "      self.memory[currKey] = -1\n",
        "      return -1\n",
        "    \n",
        "    def _simplify(self, board):\n",
        "      if board == \"\":\n",
        "        return (False, \"\")\n",
        "      \n",
        "      simplified = False\n",
        "      boardLen = len(board)\n",
        "      newBoard = board\n",
        "      for i in range(boardLen):\n",
        "        sameColor = 1\n",
        "        color = board[i]\n",
        "        for j in range(i+1, boardLen):\n",
        "          if color == board[j]:\n",
        "            sameColor += 1\n",
        "          else:\n",
        "            break\n",
        "\n",
        "        if sameColor >= 3:\n",
        "          newBoard = board[0:i] + board[i+sameColor:]\n",
        "          simplified = True\n",
        "          break\n",
        "          \n",
        "      if simplified:\n",
        "        return (True, newBoard)\n",
        "      else:\n",
        "        return (False, board)\n",
        "      \n",
        "    def simplify(self, board):\n",
        "      if board == \"\":\n",
        "        return False, board\n",
        "      if board in self.simplifiedMemory:\n",
        "        return self.simplifiedMemory[board]\n",
        "      \n",
        "      #board = board.replace(\"[\",\"\").replace(\"]\",\"\")\n",
        "      simplified = False\n",
        "      newBoard = board\n",
        "      while True:\n",
        "        simpifiedRes, newBoard = self._simplify(newBoard)\n",
        "        if simpifiedRes:\n",
        "          simplified = True\n",
        "        if not simpifiedRes:\n",
        "          break\n",
        "\n",
        "      self.simplifiedMemory[board] = (simplified, newBoard)\n",
        "      return simplified, newBoard\n",
        "\n",
        "    def permutations(self, head, tail=''):\n",
        "      if len(head) == 0:\n",
        "        self.perm.append(tail)\n",
        "      else:\n",
        "        for i in range(len(head)):\n",
        "          self.permutations(head[0:i] + head[i+1:], tail+head[i])\n",
        "            \n",
        "print(Solution().findMinStep(\"GYYRRWRRG\", \"GWWGY\"))\n",
        "\n",
        "\n",
        "\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "isQNqZpozhAJ",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title 551. Student Attendance Record I\n",
        "# https://leetcode.com/problems/student-attendance-record-i/description/\n",
        "\n",
        "class Solution:\n",
        "    def checkRecord(self, s):\n",
        "        aCount, lCount = 0, 0\n",
        "        for i in range(len(s)):\n",
        "            if s[i] == 'A':\n",
        "                aCount += 1\n",
        "            if s[i] == 'L':\n",
        "                lCount += 1\n",
        "            else:\n",
        "                lCount = 0\n",
        "            if aCount >1 or lCount >2:\n",
        "                return False\n",
        "        return True\n",
        "        \n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "pT9hRexDn1c3",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title 609. Find Duplicate File in System\n",
        "# https://leetcode.com/problems/find-duplicate-file-in-system/description/\n",
        "\n",
        "\n",
        "class Solution:\n",
        "  def __init__(self):\n",
        "    self.cache = {}\n",
        "    \n",
        "  def parse(self, path):\n",
        "    items = path.split(\" \")\n",
        "    root = items[0]\n",
        "    for i in range(1, len(items)):\n",
        "      bracket = items[i].find(\"(\")\n",
        "      filename = root + \"/\" + items[i][:bracket]\n",
        "      content = items[i][bracket+1:-1]\n",
        "      if content in self.cache:\n",
        "        self.cache[content].append(filename)\n",
        "      else:\n",
        "        self.cache[content] = [filename]\n",
        "      \n",
        "  def findDuplicate(self, paths):\n",
        "    res = []\n",
        "    for path in paths:\n",
        "      self.parse(path)\n",
        "      \n",
        "    for key in self.cache.keys():\n",
        "      if len(self.cache[key])>1:\n",
        "        res.append(self.cache[key])\n",
        "    return res\n",
        "        "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2OmywG04NnCS",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title 690. Employee Importance\n",
        "# https://leetcode.com/problems/employee-importance/description/\n",
        "\n",
        "\"\"\"\n",
        "# Employee info\n",
        "class Employee:\n",
        "  def __init__(self, id, importance, subordinates):\n",
        "    # It's the unique id of each node.\n",
        "    # unique id of this employee\n",
        "    self.id = id\n",
        "    # the importance value of this employee\n",
        "    self.importance = importance\n",
        "    # the id of direct subordinates\n",
        "    self.subordinates = subordinates\n",
        "\n",
        "  def __repr__(self):\n",
        "    return \"{\\\"id:\\\":%d, \\\"importance\\\":%d, \\\"subordinates\\\":%s}\" % (\n",
        "        self.id, self.importance, str(self.subordinates))\n",
        "\"\"\"\n",
        "\n",
        "class Solution:\n",
        "  def __init__(self):\n",
        "    self.employees = {}\n",
        "  def _getImportance(self, id):\n",
        "    importance = self.employees[id].importance\n",
        "    subImportance = 0\n",
        "    for subordinate in self.employees[id].subordinates:\n",
        "      subImportance += self._getImportance(self.employees[subordinate].id)\n",
        "    \n",
        "    return importance + subImportance\n",
        "    \n",
        "  def getImportance(self, employees, id):\n",
        "    for employee in employees:\n",
        "      self.employees[employee.id] = employee\n",
        "    return self._getImportance(id)\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "TUYYXhnGj43l",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title 735. Asteroid Collision\n",
        "# https://leetcode.com/problems/asteroid-collision/description/\n",
        "\n",
        "class Solution:\n",
        "    def asteroidCollision(self, asteroids):\n",
        "      \n",
        "      collided, currAsteroids = True, asteroids.copy()\n",
        "       \n",
        "      while collided:\n",
        "        collided, currAsteroids = self.iterate(currAsteroids)\n",
        "      \n",
        "      return currAsteroids\n",
        "        \n",
        "    def iterate(self, asteroids):\n",
        "      collided = False\n",
        "      \n",
        "      # left pass\n",
        "      for i in range(1, len(asteroids)):\n",
        "        if asteroids[i]<0 and asteroids[i-1]>0:\n",
        "          if abs(asteroids[i]) > abs(asteroids[i-1]):\n",
        "            asteroids[i-1] = 0\n",
        "            collided = True\n",
        "          elif abs(asteroids[i]) == abs(asteroids[i-1]):\n",
        "            asteroids[i-1] = 0\n",
        "            asteroids[i] = 0\n",
        "            collided = True\n",
        "          elif abs(asteroids[i]) < abs(asteroids[i-1]):\n",
        "            asteroids[i] = 0\n",
        "            collided = True\n",
        "        \n",
        "      asteroids2 = []\n",
        "      for i in range(len(asteroids)):\n",
        "        if asteroids[i] != 0:\n",
        "          asteroids2.append(asteroids[i])\n",
        "      asteroids = asteroids2\n",
        "      \n",
        "      # right pass\n",
        "      for i in reversed(range(len(asteroids)-1)):\n",
        "        if asteroids[i]>0 and asteroids[i+1]<0:\n",
        "          if abs(asteroids[i]) > abs(asteroids[i+1]):\n",
        "            asteroids[i+1] = 0\n",
        "            collided = True\n",
        "          elif abs(asteroids[i]) == abs(asteroids[i+1]):\n",
        "            asteroids[i+1] = 0\n",
        "            asteroids[i] = 0\n",
        "            collided = True\n",
        "          elif abs(asteroids[i]) < abs(asteroids[i+1]):\n",
        "            asteroids[i] = 0\n",
        "            collided = True\n",
        "          \n",
        "      asteroids2 = []\n",
        "      for i in range(len(asteroids)):\n",
        "        if asteroids[i] != 0:\n",
        "          asteroids2.append(asteroids[i])\n",
        "      asteroids = asteroids2\n",
        "\n",
        "      return collided, asteroids\n",
        "    \n",
        "    \n",
        "    \n",
        "Solution().asteroidCollision([-2,1,1,-2])"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "7UG8zJU4XEUj",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title 739. Daily Temperatures\n",
        "# https://leetcode.com/problems/daily-temperatures/description/\n",
        "\n",
        "class Solution:\n",
        "  def dailyTemperatures(self, temperatures):\n",
        "    res = list(range(len(temperatures)))\n",
        "    for i in range(len(temperatures)):\n",
        "      res[i] = 0\n",
        "    \n",
        "    i = len(temperatures)-1\n",
        "    while i>=0:\n",
        "      j = i - 1\n",
        "      while j>=0:\n",
        "        if temperatures[i] > temperatures[j]:\n",
        "          res[j] = i - j\n",
        "        else:\n",
        "          break\n",
        "        j -= 1\n",
        "      i -= 1\n",
        "      \n",
        "    return res\n",
        "          "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "K01vVRLylHdC",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title 824. Goat Latin\n",
        "\n",
        "# https://leetcode.com/problems/goat-latin/description/\n",
        "class Solution:\n",
        "  def toGoatLatinWord(self, word):\n",
        "    vowels = [\"a\", \"e\", \"i\", \"o\", \"u\", ]\n",
        "    startsWithVowels = word[0].lower() in vowels\n",
        "    if not startsWithVowels:\n",
        "      return word[1:] + word[0] + \"ma\"\n",
        "    else:\n",
        "      return word + \"ma\"\n",
        "    \n",
        "  def toGoatLatin(self, S):\n",
        "    words = S.split(\" \")\n",
        "    suffix = \"\"\n",
        "    for i in range(len(words)):\n",
        "      suffix += \"a\"\n",
        "      words[i] = self.toGoatLatinWord(words[i]) + suffix\n",
        "      \n",
        "    return \" \".join(words)\n",
        "    \n",
        "\n",
        "          \n",
        "        "
      ],
      "execution_count": 0,
      "outputs": []
    }
  ]
}