LeetCode_Problems_1.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/DaudAhmad0303/LeetCode-Problems-Solution-colab/blob/master/LeetCode_Problems_1.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "t6NchOFC-O-7"
      },
      "source": [
        "# **Random Practise Codes**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "uuvafrr0-EyH",
        "outputId": "8affabcf-63ff-46d2-cc36-b6b78866e712"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "['Orange', 'Apple', 'Grapes', 'Papya', 'Banana']\n",
            "['Orange', 'Apple', 'Grapes', 'Papya', 'Banana']\n"
          ]
        }
      ],
      "source": [
        "myList = [\"Orange\", \"Apple\",\"Grapes\",\"Papya\"]\n",
        "def addItem(myTempList):\n",
        "    myTempList.append(\"Banana\")\n",
        "    print(myTempList)\n",
        "# Print the original list\n",
        "addItem(myList)\n",
        "print(myList)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "nGfulzWSzE8f",
        "outputId": "75542a41-803e-426b-d983-bfd89b2247b9"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "10\n",
            "5\n"
          ]
        }
      ],
      "source": [
        "temp = 5\n",
        "def change(my_temp):\n",
        "  my_temp = 10\n",
        "  print(my_temp)\n",
        "\n",
        "change(temp)\n",
        "print(temp)\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "iO3ulso7f8AV"
      },
      "source": [
        "# **Random Questions Solved**"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "2MAqI9Mng6E2"
      },
      "source": [
        "## **1556. Thousand Separator**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "kK-tFGBkgCiW",
        "outputId": "d0aefe2f-e7ec-4801-d692-ef977b4832bc"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "123.487.979.897\n"
          ]
        }
      ],
      "source": [
        "n = 123487979897\n",
        "val = f'{n:,}'.replace(',','.')\n",
        "print(val)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "1pwI9SDLRBqW"
      },
      "source": [
        "## **66. Plus One**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "j9Aw9PE0RHJ2",
        "outputId": "667c0520-6e6e-4d05-bb01-ce4c9ece3a2a"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "['1', '0']\n"
          ]
        }
      ],
      "source": [
        "digits = [9]\n",
        "def int_val(lst = []):\n",
        "  val = 0\n",
        "  mul = 1\n",
        "  for i in range(len(lst)-1,-1,-1):\n",
        "    val += lst[i] * mul\n",
        "    mul *= 10\n",
        "  return val + 1\n",
        "ret = int_val(digits)\n",
        "ret = list(str(ret))\n",
        "print(ret)\n",
        "\n",
        "# join doesn't working, because it only works for string values in list;\n",
        "# So we've implemented our own function for it\n",
        "# val = \"\".join(digits)\n",
        "# val = int(val) + 1\n",
        "# print(val, type(val))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "kdg3517iOJZn"
      },
      "source": [
        "## **70. Climbing Stairs**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "TUU4tMdKPoWH"
      },
      "outputs": [],
      "source": [
        "class Solution:\n",
        "    def climbStairs(self, n: int) -> int:\n",
        "        if n <= 2:\n",
        "            return n\n",
        "        x = 1\n",
        "        y = 2\n",
        "        for i in range(2, n):\n",
        "            temp = x + y\n",
        "            x = y\n",
        "            y = temp\n",
        "        return y"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "fJ7OYOfaPtWn",
        "outputId": "19a10a45-d0e7-4ae2-ce67-a6bdad4cd3ea"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "3\n"
          ]
        }
      ],
      "source": [
        "obj = Solution()\n",
        "print(obj.climbStairs(3))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "3QTK-SBzYul_"
      },
      "source": [
        "## **946. Validate Stack Sequences**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "ZmvRrV1EYxkV"
      },
      "outputs": [],
      "source": [
        "class Solution:\n",
        "    def validateStackSequences(self, pushed, popped) -> bool:        \n",
        "        stack = []\n",
        "        popped.reverse()\n",
        "        for i in pushed:\n",
        "            stack.append(i)\n",
        "            while len(stack)!=0 and len(popped)!=0 and stack[-1] == popped[-1]:\n",
        "                stack.pop()\n",
        "                popped.pop()\n",
        "        return len(stack)==0\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "jA1X_0aOY8Mt",
        "outputId": "6840f442-e0d1-4e2d-f972-fcdec7c7c830"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "True\n"
          ]
        }
      ],
      "source": [
        "pushed = [1,2,3,4,5]; popped = [4,5,3,2,1]\n",
        "obj = Solution()\n",
        "print(obj.validateStackSequences(pushed, popped))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "d5jK0e-8QzAo"
      },
      "source": [
        "## **7. Reverse Integer**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "YqPo2boAP0eY"
      },
      "outputs": [],
      "source": [
        "class Solution:\n",
        "    def reverse(self, x: int) -> int:\n",
        "        def clamp(no):\n",
        "            if no >= (2**31 - 1) or no <= (-2**31):\n",
        "                return 0\n",
        "            else: return no\n",
        "        sign = 1\n",
        "        if x < 0:   \n",
        "            sign = -1\n",
        "            \n",
        "        s = str(abs(x))[::-1]\n",
        "        x = int(s)\n",
        "        x = clamp(sign * x)\n",
        "        return x"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "jC-6Qme7P1gk",
        "outputId": "62015622-b186-4710-c1a9-e96177ce903b"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "21\n",
            "21\n"
          ]
        }
      ],
      "source": [
        "obj = Solution()\n",
        "print(obj.reverse(120))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "6W-eFCM6HmU-"
      },
      "source": [
        "## **50. Pow(x, n)**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "VaOnidxOHqTe"
      },
      "outputs": [],
      "source": [
        "class Solution:\n",
        "    def myPow(self, x: float, n: int) -> float:\n",
        "        ans = 1\n",
        "        for i in range(abs(n)):\n",
        "            ans = ans * x\n",
        "        if n < 0:   return 1 / ans\n",
        "        return ans"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "0czn_8DxLBMw"
      },
      "outputs": [],
      "source": [
        "class Solution:\n",
        "    def myPow(self, x: float, n: int) -> float:\n",
        "        ans = 1\n",
        "        p = n\n",
        "        n = abs(n)\n",
        "        while n > 0:\n",
        "            if n % 2 == 0:\n",
        "                n = n / 2\n",
        "                x *= x\n",
        "            else:\n",
        "                ans = ans * x\n",
        "                n -= 1\n",
        "        if p < 0:\n",
        "            return 1/ans\n",
        "        return ans"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "-x0u6BJoJGRp",
        "outputId": "239b6feb-f24f-477c-dd9c-f34e62729e8d"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "0.0\n",
            "CPU times: user 1.21 ms, sys: 42 µs, total: 1.25 ms\n",
            "Wall time: 5.21 ms\n"
          ]
        }
      ],
      "source": [
        "obj = Solution()\n",
        "%time print(obj.myPow(0.00001,2147483647))"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "d3i4pRi7KG4k",
        "outputId": "802cba1a-bd44-4113-9ab7-475ba83f5837"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "helllo\n",
            "CPU times: user 124 µs, sys: 0 ns, total: 124 µs\n",
            "Wall time: 107 µs\n"
          ]
        }
      ],
      "source": [
        "%%time\n",
        "print('helllo')"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "3-aN6P8MRpW0"
      },
      "source": [
        "## **150. Evaluate Reverse Polish Notation**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "ckxgGpTYRp9U"
      },
      "outputs": [],
      "source": [
        "class Solution:\n",
        "    def evalRPN(self, tokens) -> int:\n",
        "        def isOperator(s):\n",
        "            if s == '+' or s == '-' or s == '*' or s == '/':\n",
        "                return True\n",
        "            else:\n",
        "                return False\n",
        "        \n",
        "        def calculate(op1, op2, opr):\n",
        "            if opr == '+':\n",
        "                return op1 + op2\n",
        "            if opr == '-':\n",
        "                return op1 - op2\n",
        "            if opr == '*':\n",
        "                return op1 * op2\n",
        "            elif opr == '/':\n",
        "                return int(op1 / op2)\n",
        "            else: \n",
        "                return 0\n",
        "        stack = []\n",
        "        i = 0\n",
        "        for i in tokens:\n",
        "            if isOperator(i):\n",
        "                op2 = stack.pop()\n",
        "                op1 = stack.pop()\n",
        "                result = calculate(op1, op2, i)\n",
        "                stack.append(result)               \n",
        "            else:\n",
        "                stack.append(int(i))\n",
        "        return stack.pop()"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "wD5rPU9QRq4h",
        "outputId": "ef06f3a2-f29a-4a3c-a89f-4cd5bb9459d1"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "9\n",
            "None [1, 2, 3, 5, 6, 9]\n"
          ]
        }
      ],
      "source": [
        "obj = Solution()\n",
        "print(obj.evalRPN(tokens = [\"2\",\"1\",\"+\",\"3\",\"*\"]))\n",
        "tokens = [3,5,6,2,9,1]"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "KvWWSQqYZ6_r"
      },
      "source": [
        "## **148. Sort List**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "J37jVLEwZ_7L"
      },
      "outputs": [],
      "source": [
        "# Definition for singly-linked list.\n",
        "class ListNode:\n",
        "    def __init__(self, val=0, next=None):\n",
        "        self.val = val\n",
        "        self.next = next\n",
        "class Solution:\n",
        "    def sortList(self, head: ListNode) -> ListNode:\n",
        "        lst = []\n",
        "        temp = head\n",
        "        while temp:\n",
        "            val = temp.val\n",
        "            temp = temp.next\n",
        "            lst.append(val)\n",
        "        lst.sort()\n",
        "        i = 0\n",
        "        temp2 = head\n",
        "        while temp2:\n",
        "            temp2.val = lst[i]\n",
        "            temp2 = temp2.next\n",
        "            i += 1\n",
        "        return head"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "folz_5lMaL50",
        "outputId": "8855da3f-9fac-41c6-f34d-08ee25f65951"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "<class '__main__.ListNode'>\n"
          ]
        }
      ],
      "source": [
        "obj = Solution()\n",
        "obj1 = ListNode()\n",
        "print(type(obj1))\n",
        "head = obj1\n",
        "obj1.val = 4      #head = [4,2,1,3]\n",
        "obj1 = obj1.next\n",
        "# obj1.val = 2\n",
        "# obj1 = obj1.next\n",
        "# obj1.val = 1 \n",
        "# obj1 = obj1.next\n",
        "# obj1.val = 3\n",
        "# print(obj.sortList(head))"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Ng_8p2sV-4pN",
        "outputId": "ae36e031-5f11-45e5-ff91-9e19a6bfa9fb"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "4\n"
          ]
        }
      ],
      "source": [
        "val = str(9999)\n",
        "print(len(val))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "uoKy6Y0lA1Cm"
      },
      "source": [
        "## **415. Add Strings**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "Qej6ebBfA3Du"
      },
      "outputs": [],
      "source": [
        "class Solution:\n",
        "    def addStrings(self, num1: str, num2: str) -> str:\n",
        "        def convert_to_int(s):\n",
        "            num = {\n",
        "            '0':0, '1':1, '2':2, '3':3, '4':4, '5':5, '6':6, '7':7, '8':8, '9':9\n",
        "            }\n",
        "            val = num[s[0]]\n",
        "            for i in range(1, len(s)):\n",
        "                val = val * 10 + num[s[i]]\n",
        "            return val\n",
        "        \n",
        "        return str(convert_to_int(num1) + convert_to_int(num2))"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "gSns7K4EA5JI",
        "outputId": "cbfaaf5a-7694-497f-f4ce-745990ccab7f"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Result is 134\n"
          ]
        }
      ],
      "source": [
        "obj = Solution()\n",
        "print('Result is',obj.addStrings(num1 = \"11\", num2 = \"123\"))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0sOrfkLmARo1"
      },
      "source": [
        "## **989. Add to Array-Form of Integer**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "-Aha-BdRAQHH"
      },
      "outputs": [],
      "source": [
        "class Solution:\n",
        "    def addToArrayForm(self, num, k: int):\n",
        "        val = 0\n",
        "        for i in range(len(num)):\n",
        "            val = val * 10 + num[i]\n",
        "        val += k\n",
        "        num = []\n",
        "        str_val = str(val)\n",
        "        l = len(str_val)\n",
        "        for i in range(l):\n",
        "            num.append(int(str_val[i]))\n",
        "        return num"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "3NG8V0iRAW2j",
        "outputId": "f4511a60-aa58-4206-b761-e3c4bfa39b16"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "[1, 2, 3, 4]\n"
          ]
        }
      ],
      "source": [
        "obj = Solution()\n",
        "print(obj.addToArrayForm(num = [1,2,0,0], k = 34))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GgMMxxoaYSUU"
      },
      "source": [
        "## **338. Counting Bits**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "g7c7kDbVYXI7",
        "outputId": "12743326-9e65-4d17-e81a-75c196c9e690"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "<class 'str'>\n",
            "2\n"
          ]
        }
      ],
      "source": [
        "i = bin(5)\n",
        "# s = str(i)\n",
        "print(type(i))\n",
        "# print(count('1',s))\n",
        "print('1001'.count('1'))"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "OJOzWVIlaHZb"
      },
      "outputs": [],
      "source": [
        "class Solution:\n",
        "    def countBits(self, n: int):\n",
        "        extra = n\n",
        "        lst = []\n",
        "        for i in range(n+1):\n",
        "            s = bin(i)[2:]\n",
        "            lst.append(s.count('1'))\n",
        "        return lst"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "e_7hM5t1aIec",
        "outputId": "956b3a7b-3a8d-4f5e-9f7a-5770796ff561"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "[0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3]\n"
          ]
        }
      ],
      "source": [
        "obj = Solution()\n",
        "print(obj.countBits(98))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "DPDRh0wRchFy"
      },
      "source": [
        "## **191. Number of 1 Bits**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "xszS1kXmckNq",
        "outputId": "c75d0843-43b9-42d3-b845-09c61b0f44ed"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "3\n",
            "<class 'str'>\n"
          ]
        }
      ],
      "source": [
        "n = 0b00000000000000000000000000001011\n",
        "n = int(n)\n",
        "n = bin(n)[2:]\n",
        "n = str(n)\n",
        "# val = str(n)\n",
        "print(n.count('1'))\n",
        "print(type(n))"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "x2lsl2aAePpa",
        "outputId": "5308ac9a-ef57-494c-b051-855327dbf6d7"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "3\n"
          ]
        }
      ],
      "source": [
        "class Solution:\n",
        "    def hammingWeight(self, n: int) -> int:\n",
        "        n = int(n)\n",
        "        n = bin(n)[2:]\n",
        "        return n.count('1')\n",
        "obj = Solution()\n",
        "print(obj.hammingWeight(0b00000000000000000000000000001011))"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## **14. Longest Common Prefix**"
      ],
      "metadata": {
        "id": "PxR3wVpJpwH0"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# print(max([\"flower\",\"flow\",\"flight\"]))\n",
        "strs = [\"flower\",\"flow\",\"flight\"]\n",
        "m = max([\"flower\",\"flow\",\"flight\"])\n",
        "strs.remove(m)\n",
        "val = ''\n",
        "for i in range(len(m)):\n",
        "    pass\n",
        "    "
      ],
      "metadata": {
        "id": "7o8qxfvEhndO"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "class Solution:\n",
        "    def longestCommonPrefix(self, strs: List[str]) -> str:\n",
        "        l = list(zip(*strs))\n",
        "        print(l)\n",
        "        prefix = \"\"\n",
        "        for i in l:\n",
        "            if len(set(i))==1:\n",
        "                prefix += i[0]\n",
        "            else:\n",
        "                break\n",
        "        return prefix\n",
        "obj = Solution()\n",
        "print(obj.longestCommonPrefix(strs = [\"flower\",\"flow\",\"flight\"]))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "puq1eT5NpO_t",
        "outputId": "377f54cd-f506-40a4-eecf-7e778865dc95"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[('f', 'f', 'f'), ('l', 'l', 'l'), ('o', 'o', 'i'), ('w', 'w', 'g')]\n",
            "fl\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## **1598. Crawler Log Folder**"
      ],
      "metadata": {
        "id": "RtxBgMOhtOEz"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "class Solution:\n",
        "    def minOperations(self, logs: List[str]) -> int:\n",
        "        c = 0\n",
        "        for i in range(len(logs)):\n",
        "            if logs[i] == '../':\n",
        "                if c > 0:\n",
        "                    c -= 1\n",
        "            elif logs[i] == './':\n",
        "                pass\n",
        "            else:\n",
        "                 c += 1\n",
        "        return c\n",
        "obj = Solution()\n",
        "print(obj.minOperations([\"./\",\"wz4/\",\"../\",\"mj2/\",\"../\",\"../\",\"ik0/\",\"il7/\"]))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "zBVVhhF3tUoK",
        "outputId": "8284f1cb-874f-4d3b-be6f-e0064596db6d"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "2\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## **28. Implement strStr()**"
      ],
      "metadata": {
        "id": "cX5fCWG6p77K"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "class Solution:\n",
        "    def strStr(self, haystack: str, needle: str) -> int:\n",
        "        if needle not in haystack:\n",
        "            return -1\n",
        "        if needle == \"\":\n",
        "            return 0\n",
        "        ret = 0\n",
        "        return haystack.index(needle)\n",
        "\n",
        "obj = Solution()\n",
        "haystack = \"hello\"; needle = \"ll\"\n",
        "print(obj.strStr(haystack,needle))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "RBKsgBJmp5JT",
        "outputId": "8119d857-6d6e-4608-f0e2-606dba84dc16"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "2\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "class Solution:\n",
        "    def strStr(self, haystack: str, needle: str) -> int:\n",
        "        n = len(needle)\n",
        "        h = len(haystack)\n",
        "        t = h-n+1\n",
        "        if n == 0:\n",
        "            return 0\n",
        "        for i in range(t):\n",
        "            if haystack[i:n+i] == needle:\n",
        "                return i\n",
        "        return -1\n",
        "\n",
        "obj = Solution()\n",
        "haystack = \"hello\"; needle = \"ll\"\n",
        "print(obj.strStr(haystack,needle))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "kX0_cdhgqe5p",
        "outputId": "20fc6fef-f17c-4d46-c408-ff17667786db"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "2\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "32tbW0w-8_-i"
      },
      "source": [
        "# **Daily Coding Challenge**\n",
        "\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## ***Jan 1:* 312. Burst Balloons**"
      ],
      "metadata": {
        "id": "EFaNIAA3lkCq"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "class Solution:\n",
        "    def maxCoins(self, nums) -> int:\n",
        "        nums = [1] + nums + [1]  # add the dummy head and tail, both are left till end and DO NOT burst them.\n",
        "        dp = [[0] * len(nums) for _ in nums]\n",
        "        for i in range(len(nums) - 3, -1, -1):\n",
        "            for j in range(i + 2, len(nums)):\n",
        "                dp[i][j] = max([dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j] for k in range(i + 1, j)])\n",
        "        return dp[0][len(nums) - 1]\n",
        "obj = Solution()\n",
        "print(obj.maxCoins(nums = [3,1,5,8]))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "0WK4DFSLmGvT",
        "outputId": "dedffcfc-682c-4bc0-c2b1-362d8528170a"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "167\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "-tVYnypZ9S00"
      },
      "source": [
        "## ***Jan 2:*1010. Pairs of Songs With Total Durations Divisible by 60**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "42NQ-QktWcHo"
      },
      "outputs": [],
      "source": [
        "class Solution:\n",
        "    def numPairsDivisibleBy60(self, time) -> int:\n",
        "        c = [0] * 60\n",
        "        res = 0\n",
        "        for t in time:\n",
        "            res += c[-t % 60]     # here getting result from the below ones stored in 'c' list\n",
        "            c[t % 60] += 1        # here updating record for next moves\n",
        "        return res"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "lNhqFfNhWetU",
        "outputId": "55821c45-91f2-48c0-f99d-7872c78e76e4"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "3\n"
          ]
        }
      ],
      "source": [
        "obj1 = Solution()\n",
        "lst = [30,20,150,100,40]\n",
        "print(obj1.numPairsDivisibleBy60(time = lst))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "fzoL61LoD68i"
      },
      "source": [
        "## ***Jan 3:* 997. Find the Town Judge**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "bbc0dSp-EBO7"
      },
      "outputs": [],
      "source": [
        "class Solution:\n",
        "    def findJudge(self, n: int, trust) -> int:\n",
        "        val = trust[0][1]\n",
        "        trusting = 0\n",
        "        for i in range(len(trust)):\n",
        "            if trust[i][1] != val:\n",
        "                return -1\n",
        "            elif trust[0][1] == val:\n",
        "                trusting += 1\n",
        "        return trusting"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "NLBS-GNHEFZK",
        "outputId": "7241af71-ffee-4e7d-b0a5-6352dac767d6"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "-1\n"
          ]
        }
      ],
      "source": [
        "n = 2; trust = [[1,2]]\n",
        "trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]\n",
        "obj1 = Solution()\n",
        "print(obj1.findJudge(n, trust))"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "503rPrTJKJ5E",
        "outputId": "2651d8a8-d9b9-4c46-9904-729eba9e349e"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "1\n",
            "1\n",
            "2\n",
            "2\n",
            "4\n",
            "[1, 4]\n"
          ]
        }
      ],
      "source": [
        "for i in range(len(trust)):\n",
        "  print(trust[i][0])\n",
        "print(trust[0:][1])"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Lq4w0hrGJPHD"
      },
      "source": [
        "## ***Jan 4:* 1009. Complement of Base 10 Integer**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "dxXiuz-DJ0VU"
      },
      "outputs": [],
      "source": [
        "class Solution:\n",
        "    def bitwiseComplement(self, n: int) -> int:\n",
        "        binary_no = bin(n)\n",
        "        binary = []\n",
        "        for i in range(2, len(binary_no)):\n",
        "          if binary_no[i] == '0':\n",
        "            binary.append('1')\n",
        "          elif binary_no[i] == '1':\n",
        "            binary.append('0')\n",
        "        val = '0b'+''.join(map(str, binary))\n",
        "        return int(val, 2)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "YdRvGSCKKOos",
        "outputId": "8936a569-c377-4c23-e01d-f92d66faf494"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "2\n"
          ]
        }
      ],
      "source": [
        "obj1 = Solution()\n",
        "print(obj1.bitwiseComplement(5))"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "JuJ3pcuNLQUd",
        "outputId": "db86c35f-6baa-475c-945b-c74d6d73a390"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "0b100110\n",
            "38\n"
          ]
        }
      ],
      "source": [
        "lst = [1,0,0,1,1,0]\n",
        "val = '0b'+''.join(map(str, lst))\n",
        "print(val)\n",
        "print(int(val, 2))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "SWPIPmApUrxj"
      },
      "source": [
        "## ***Jan 5:* 131. Palindrome Partitioning**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "-1qn7Z7dVF1j",
        "outputId": "35e8e864-50dc-4e80-898c-66eb6abd4f5f"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "['a', 'aa', 'aab', 'a', 'ab', 'b']\n",
            "[['a', 'a', 'b']]\n",
            "[['a', 'a', 'b']]\n",
            "[['a', 'a', 'b']]\n"
          ]
        }
      ],
      "source": [
        "# test_str = \"aab\"\n",
        "# res = [test_str[i: j] for i in range(len(test_str)) for j in range(i + 1, len(test_str) + 1)]\n",
        "# print(res)\n",
        "s = \"aab\"\n",
        "res = []\n",
        "for i in range(len(s)):\n",
        "  for j in range(i + 1, len(s) + 1):\n",
        "    res.append(s[i: j])\n",
        "    # print(f'{i}-{j}')\n",
        "print(res)\n",
        "str_to_return = []\n",
        "str_to_return.append(list(s))\n",
        "print(str_to_return)\n",
        "# while True:\n",
        "\n",
        "for i in range(len(s)+1):  \n",
        "  new_partition = []\n",
        "  new_partition.append(str_to_return[0][i])\n",
        "  for j in range(len(res)):\n",
        "    is_palin = s[i+1:]\n",
        "    if is_palin == is_palin[::-1]:\n",
        "      pass\n",
        "\n",
        "print(new_partition)\n",
        "print(str_to_return)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "UCgbZdzK0TMc",
        "outputId": "cc164112-b19a-48ed-d9d5-82a2e19195a5"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "['g', 'e', 'ee', 'eee', 'e', 'ee', 'e', 'k', 's', 'f', 'o', 'r', 'g', 'e', 'ee', 'eee', 'e', 'ee', 'e', 'k', 's']\n",
            "1\n"
          ]
        }
      ],
      "source": [
        "s = \"geeeksforgeeeks\"\n",
        "# s = \"aba\"\n",
        "res = []\n",
        "for i in range(len(s)):\n",
        "  for j in range(i + 1, len(s) + 1):\n",
        "    val = s[i:j]\n",
        "    if val == val[::-1]:\n",
        "      res.append(val)\n",
        "    # print(f'{i}-{j}')\n",
        "print(res)\n",
        "result = []\n",
        "temp_s = s\n",
        "for i in range(len(res)):\n",
        "  temp_lst = []\n",
        "  # if res[i]\n",
        "\n",
        "\n",
        "# [a,a,b,b],[a, a, bb], [aa, b, b],[aa,bb]   -----> s = \"aabb\"         ['a', 'aa', 'a', 'b', 'bb', 'b']\n",
        "# [a,b,b],[a, bb]                            -----> s = \"abb\"          ['a', 'b', 'bb', 'b']\n",
        "# [a,b,b],[a, bb]                            -----> s = \"aab\"          ['a', 'aa', 'a', 'b']\n",
        "# [a,b,a],[aba]                            -----> s = \"aba\"          ['a', 'aba', 'b', 'a']\n",
        "# [g,e,e,k,s,f,o,r,g,e,e,k,s],[g,ee,k,s,f,o,r,g,e,e,k,s], [g,e,e,k,s,f,o,r,g,ee,k,s],[g,ee,k,s,f,o,r,g,ee,k,s]\n",
        "#                                          -----> s = \"geeksforgeeks\"         ['g', 'e', 'ee', 'e', 'k', 's', 'f', 'o', 'r', 'g', 'e', 'ee', 'e', 'k', 's']\n",
        "print(s.find(res[1]))"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "haJsQ1t6KtIe"
      },
      "outputs": [],
      "source": [
        "# Correct and final solution ***jo k uthaya he ;)'\n",
        "class Solution:\n",
        "    # cache  # the memory trick can save some time\n",
        "    def partition(self, s):\n",
        "        if not s: return [[]]\n",
        "        ans = []\n",
        "        for i in range(1, len(s) + 1):\n",
        "            if s[:i] == s[:i][::-1]:  # prefix is a palindrome\n",
        "                for suf in self.partition(s[i:]):  # process suffix recursively\n",
        "                    ans.append([s[:i]] + suf)\n",
        "        return ans"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "5CVDZc-BKuHY",
        "outputId": "dcae6d4a-bdf4-4aba-d6e8-8b2da5441bc1"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "[['g', 'e', 'e', 'k', 's', 'f', 'o', 'r', 'g', 'e', 'e', 'k', 's'], ['g', 'e', 'e', 'k', 's', 'f', 'o', 'r', 'g', 'ee', 'k', 's'], ['g', 'ee', 'k', 's', 'f', 'o', 'r', 'g', 'e', 'e', 'k', 's'], ['g', 'ee', 'k', 's', 'f', 'o', 'r', 'g', 'ee', 'k', 's']]\n"
          ]
        }
      ],
      "source": [
        "obj1 = Solution()\n",
        "val = \"geeksforgeeks\"\n",
        "print(obj1.partition(val))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "7BwRRpCdxyrC"
      },
      "source": [
        "## ***Jan 6:* 1094. Car Pooling**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "JuVCiC84OB7i"
      },
      "outputs": [],
      "source": [
        "class Solution:\n",
        "    def carPooling(self, l, cap: int) -> bool:\n",
        "        \n",
        "        Passenger_record=[0]*1001\n",
        "        \n",
        "        for i in l:\n",
        "            passenger, start, end = i[0], i[1], i[2]\n",
        "            Passenger_record[start] += passenger\n",
        "            Passenger_record[end] -= passenger\n",
        "        \n",
        "        total = 0\n",
        "        for i in Passenger_record:\n",
        "            total += i\n",
        "            if total > cap:\n",
        "                return False\n",
        "        return True"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "RRYpBtTkH077",
        "outputId": "05a7aa95-1ae0-423c-939e-4e1846f79a00"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "False\n"
          ]
        }
      ],
      "source": [
        "trips = [[2,1,5],[3,3,7]]; capacity = 4\n",
        "obj1 = Solution()\n",
        "print(obj1.carPooling(trips, capacity))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9zWvDp7H12j2"
      },
      "source": [
        "## ***Jan 7:* 382. Linked List Random Node**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "X0--j2GI2PkH"
      },
      "outputs": [],
      "source": [
        "class Solution:\n",
        "\n",
        "    def __init__(self, head):\n",
        "        # store nodes' value in an array \n",
        "        self.array = []\n",
        "        curr = head\n",
        "        while curr:\n",
        "            self.array.append(curr.val)\n",
        "            curr = curr.next\n",
        "            \n",
        "    def getRandom(self) -> int:\n",
        "        num = int(random.random() * len(self.array))\n",
        "        return self.array[num]"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "HfFvPXol3H5G"
      },
      "outputs": [],
      "source": [
        "obj = Solution ()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "hZzxW9bEGvbG"
      },
      "source": [
        "## ***Jan 8:* 1463. Cherry Pickup II**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "zASa8JVzG6Ac"
      },
      "outputs": [],
      "source": [
        "# Very Hard to Understand *Copy Paste Work*\n",
        "class Solution:\n",
        "\tdef cherryPickup(self, grid) -> int:\n",
        "\t\tm, n = len(grid), len(grid[0])\n",
        "\n",
        "\t\t# @lru_cache(None)\n",
        "\t\tdef dfs(r,c1,c2):\n",
        "\t\t\tif r==m:\n",
        "\t\t\t\treturn 0\n",
        "\n",
        "\t\t\tch = grid[r][c1] if c1==c2 else grid[r][c1]+grid[r][c2]            \n",
        "\t\t\tres = 0\n",
        "\t\t\tfor p in range(c1-1,c1+2):\n",
        "\t\t\t\tfor q in range(c2-1,c2+2):\n",
        "\t\t\t\t\tif 0<=p<n and 0<=q<n:\n",
        "\t\t\t\t\t\tres = max(res,dfs(r+1,p,q))\n",
        "\t\t\treturn ch+res\n",
        "\n",
        "\t\treturn dfs(0,0,n-1)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "VYIHhPAt6efH",
        "outputId": "c4b2e380-ad17-4be8-984c-0cfcae6cc2aa"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "24\n"
          ]
        }
      ],
      "source": [
        "obj1 = Solution()\n",
        "print(obj1.cherryPickup([[3,1,1],[2,5,1],[1,5,5],[2,1,1]]))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "wjRoOsLxWNBc"
      },
      "source": [
        "## ***Jan 9:* 1041. Robot Bounded In Circle**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "DYZAEszoWqwU"
      },
      "outputs": [],
      "source": [
        "# Copied and understanded\n",
        "class Solution(object):\n",
        "    def isRobotBounded(self, instructions):\n",
        "        d = [[1, 0], [0, 1], [-1, 0], [0, -1]]\n",
        "        di = x = y = 0\n",
        "        for i in instructions:\n",
        "            if i == 'L': di = (di + 1) % 4\n",
        "            elif i == 'R': di = (di - 1) % 4\n",
        "            else: x, y = x + d[di][0], y + d[di][1]     \n",
        "        if x == 0 and y == 0 or di > 0: return True\n",
        "        return False"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "gvUWZONOcJt9",
        "outputId": "6499e3ac-dd55-48b2-a7f2-073baf693e64"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "True"
            ]
          },
          "execution_count": 63,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "obj1 = Solution()\n",
        "obj1.isRobotBounded(instructions = \"GGLLGG\")"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Wn3yumVBOlGQ"
      },
      "source": [
        "## ***Jan 10:* 67. Add Binary**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "PlqDRDJfO3Ok",
        "outputId": "d10ce730-8cd3-49b0-bc40-2b252a5fb6e5"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "10101\n"
          ]
        }
      ],
      "source": [
        "a = '1010';b = '1011'\n",
        "a = int(a, 2)\n",
        "b = int(b, 2)\n",
        "print(bin(int(a+b))[2:])"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "kJtftQ7oPFZd"
      },
      "source": [
        "## ***Jan 11:* 1022. Sum of Root To Leaf Binary Numbers**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 380
        },
        "id": "9QtGEoWxPd46",
        "outputId": "332822ed-5fe1-48c8-fef5-74cb5592b4f4"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "['[1, 0, 1, 0, 1, 0, 1]']\n",
            "[1, 0, 1, 0, 1, 0, 1]\n"
          ]
        },
        {
          "ename": "ValueError",
          "evalue": "ignored",
          "output_type": "error",
          "traceback": [
            "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
            "\u001b[0;31mValueError\u001b[0m                                Traceback (most recent call last)",
            "\u001b[0;32m<ipython-input-9-671bb7af50ed>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m     35\u001b[0m \u001b[0mobj1\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mSolution\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     36\u001b[0m \u001b[0mobj2\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mTreeNode\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 37\u001b[0;31m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mobj1\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msumRootToLeaf\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mroot\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mobj2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
            "\u001b[0;32m<ipython-input-9-671bb7af50ed>\u001b[0m in \u001b[0;36msumRootToLeaf\u001b[0;34m(self, root)\u001b[0m\n\u001b[1;32m     30\u001b[0m         \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnos\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     31\u001b[0m         \u001b[0;32mfor\u001b[0m \u001b[0mb\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mnos\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 32\u001b[0;31m             \u001b[0mres\u001b[0m\u001b[0;34m+=\u001b[0m\u001b[0mbin_to_dec\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mb\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     33\u001b[0m         \u001b[0;32mreturn\u001b[0m \u001b[0mres\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     34\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m<ipython-input-9-671bb7af50ed>\u001b[0m in \u001b[0;36mbin_to_dec\u001b[0;34m(s)\u001b[0m\n\u001b[1;32m     24\u001b[0m             \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ms\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     25\u001b[0m             \u001b[0;32mfor\u001b[0m \u001b[0mi\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 26\u001b[0;31m                 \u001b[0mans\u001b[0m\u001b[0;34m+=\u001b[0m\u001b[0mint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ms\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m*\u001b[0m \u001b[0;36m2\u001b[0m \u001b[0;34m**\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     27\u001b[0m             \u001b[0;32mreturn\u001b[0m \u001b[0mans\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     28\u001b[0m         \u001b[0mdp\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mroot\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\"\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;31mValueError\u001b[0m: invalid literal for int() with base 10: '['"
          ]
        }
      ],
      "source": [
        "class TreeNode:\n",
        "    def __init__(self, val=0, left=None, right=None):\n",
        "        self.val = val\n",
        "        self.left = left\n",
        "        self.right = right\n",
        "class Solution:\n",
        "    def sumRootToLeaf(self, root) -> int:\n",
        "        if not root: return 0\n",
        "        nos=[]\n",
        "        def dp(node,s):\n",
        "            s+=str(node.val)\n",
        "            if not node.left and not node.right:\n",
        "                nos.append(s)\n",
        "            elif not node.right:\n",
        "                dp(node.left,s)\n",
        "            elif not node.left:\n",
        "                dp(node.right,s)\n",
        "            else:\n",
        "                dp(node.left,s)\n",
        "                dp(node.right,s)\n",
        "        def bin_to_dec(s):\n",
        "            ans=0\n",
        "            n=len(s)\n",
        "            print(s)\n",
        "            for i in range(n):\n",
        "                ans+=int(s[i]) * 2 ** (n-i-1)\n",
        "            return ans\n",
        "        dp(root,\"\")\n",
        "        res=0\n",
        "        print(nos)\n",
        "        for b in nos:\n",
        "            res+=bin_to_dec(b)\n",
        "        return res\n",
        "\n",
        "obj1 = Solution()\n",
        "obj2 = TreeNode([1,0,1,0,1,0,1])\n",
        "print(obj1.sumRootToLeaf(root = obj2))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "b8wpCu_Tj_2y"
      },
      "source": [
        "## ***Jan 12:* 701. Insert into a Binary Search Tree**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "-GdqKQdLkIKS"
      },
      "outputs": [],
      "source": [
        "# Definition for a binary tree node.\n",
        "class TreeNode:\n",
        "    def __init__(self, val=0, left=None, right=None):\n",
        "        self.val = val\n",
        "        self.left = left\n",
        "        self.right = right\n",
        "class Solution:\n",
        "    def insertIntoBST(self, root, val: int):\n",
        "        node = TreeNode(val=val)\n",
        "        if not root:\n",
        "            return node\n",
        "        temp = root\n",
        "        prev = None\n",
        "        while temp:\n",
        "            prev = temp\n",
        "            if val > temp.val:\n",
        "                temp = temp.right\n",
        "            else:\n",
        "                temp = temp.left\n",
        "        if val > prev.val:\n",
        "            prev.right = node\n",
        "        else:\n",
        "            prev.left = node\n",
        "        return root"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 321
        },
        "id": "iCxZesjMkYSk",
        "outputId": "35f86a4e-a6e6-45f4-a482-af5f31aa7913"
      },
      "outputs": [
        {
          "ename": "AttributeError",
          "evalue": "ignored",
          "output_type": "error",
          "traceback": [
            "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
            "\u001b[0;31mAttributeError\u001b[0m                            Traceback (most recent call last)",
            "\u001b[0;32m<ipython-input-8-da5f123fdae7>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m      6\u001b[0m \u001b[0;31m# obj1.val = 2\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      7\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 8\u001b[0;31m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mobj\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0minsertIntoBST\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mroot\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mval\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
            "\u001b[0;32m<ipython-input-2-5ecf2f0031fa>\u001b[0m in \u001b[0;36minsertIntoBST\u001b[0;34m(self, root, val)\u001b[0m\n\u001b[1;32m     14\u001b[0m         \u001b[0;32mwhile\u001b[0m \u001b[0mtemp\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     15\u001b[0m             \u001b[0mprev\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mtemp\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 16\u001b[0;31m             \u001b[0;32mif\u001b[0m \u001b[0mval\u001b[0m \u001b[0;34m>\u001b[0m \u001b[0mtemp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mval\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     17\u001b[0m                 \u001b[0mtemp\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mtemp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mright\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     18\u001b[0m             \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;31mAttributeError\u001b[0m: 'list' object has no attribute 'val'"
          ]
        }
      ],
      "source": [
        "root = [4,2,7,1,3]; val = 5\n",
        "obj = Solution()\n",
        "obj1 = TreeNode()\n",
        "obj1.val = 4\n",
        "obj1 = obj1.left\n",
        "# obj1.val = 2\n",
        "\n",
        "print(obj.insertIntoBST(root,val))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "12qM35msAVyO"
      },
      "source": [
        "## ***Jan 13:* 452. Minimum Number of Arrows to Burst Balloons**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "H0gj7BUUDViW",
        "outputId": "7436a8e9-a074-4865-eb11-cd9a1cde751c"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "[1, 2, 2, 2, 1]\n",
            "3\n"
          ]
        }
      ],
      "source": [
        "points = [[10,16],[2,8],[1,6],[7,12]]\n",
        "# points = [[1,2],[3,4],[5,6],[7,8]]\n",
        "points = [[1,2],[2,3],[3,4],[4,5]]\n",
        "maxi_val = 0\n",
        "for i in points:\n",
        "  for j in i:\n",
        "    maxi_val = max(maxi_val, j)\n",
        "# print(maxi_val)\n",
        "record = [0] * maxi_val\n",
        "for i in points:\n",
        "  for j in range(i[0]-1, i[1]):\n",
        "    record[j] += 1\n",
        "print(record)\n",
        "l = len(points)\n",
        "decrement = 0\n",
        "for i in range(len(record)-1):\n",
        "  if record[i] < record[i+1]:\n",
        "    decrement += 1\n",
        "print(l-decrement)\n",
        "\n",
        "# Stuck \n",
        "# Don't know what should do next"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "GlJlq09nNqZB",
        "outputId": "88cb6219-bdcd-42b6-f67d-f13720070de0"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "[[1, 2], [2, 3], [3, 4], [4, 5]]\n",
            "2\n"
          ]
        }
      ],
      "source": [
        "points = [[10,16],[2,8],[1,6],[7,12]]\n",
        "# points = [[1,2],[3,4],[5,6],[7,8]]\n",
        "points = [[1,2],[2,3],[3,4],[4,5]]\n",
        "points.sort(key= lambda x : x[1])\n",
        "print(points)\n",
        "ans = 0; arrow = 0\n",
        "for start, end in points:\n",
        "  if ans == 0 or start > arrow:\n",
        "    ans = ans + 1\n",
        "    arrow = end\n",
        "print(ans)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "GvESRij4QD0P",
        "outputId": "5a858636-9dd1-4705-bb09-787fe7ebf512"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Help on built-in function sort:\n",
            "\n",
            "sort(*, key=None, reverse=False) method of builtins.list instance\n",
            "    Stable sort *IN PLACE*.\n",
            "\n"
          ]
        }
      ],
      "source": [
        "help(points.sort)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ONFpJAyUfvTA"
      },
      "source": [
        "## ***Jan 14:* 8. String to Integer (atoi)**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "ppsUBI4snPxg",
        "outputId": "e2a6b474-7ad1-4180-88b9-864359aafeb1"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "['words', 'and', '987']\n",
            "987\n",
            "-45\n"
          ]
        }
      ],
      "source": [
        "s = \"   -42\"\n",
        "s = \"4193 with words\"\n",
        "s = \"words and 987\"\n",
        "s = \"-91283472332\"      # output = -91283472332     # expected = -2147483648\n",
        "alpha = \"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz .\"\n",
        "new = \"\"\n",
        "print(s.split(' '))\n",
        "for i in s:\n",
        "  if i not in alpha:\n",
        "    new += i \n",
        "flag = True\n",
        "# s = s.strip()\n",
        "print(new)\n",
        "print(int(\"-45\"))\n",
        "\"42\"\n",
        "\"   -42\"\n",
        "\"4193 with words\"\n",
        "\"words and 987\""
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "6XT832mELerH"
      },
      "outputs": [],
      "source": [
        "class Solution:\n",
        "    def myAtoi(self, s: str) -> int:\n",
        "        s = s.strip()\n",
        "        alpha = \"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz .\"\n",
        "        lst = s.split(' ')\n",
        "        s = lst[0].split('.')\n",
        "        s = s[0]\n",
        "        new = \"\"\n",
        "        for i in s:\n",
        "            if i not in alpha:\n",
        "                new += i\n",
        "        new = new.strip()\n",
        "        if new == '':   return 0\n",
        "        if not new[1].isdigit():   return 0\n",
        "        def clip(val, min_ = -2147483648, max_=2147483647):\n",
        "            return min_ if val < min_ else max_ if val > max_ else val\n",
        "        return clip(int(new))"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "hDCGJWX_CnHl"
      },
      "outputs": [],
      "source": [
        "class Solution:\n",
        "    def myAtoi(self, s: str) -> int:\n",
        "        s = s.strip()\n",
        "        alpha = \"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz .\"\n",
        "        lst = s.split(' ')\n",
        "        s = lst[0]\n",
        "        new = \"\"\n",
        "        for i in s:\n",
        "            if i not in alpha:\n",
        "                new += i\n",
        "        new = new.strip()\n",
        "        if new == '':   return 0\n",
        "        def clip(val, min_ = -2147483648, max_=2147483647):\n",
        "          return min_ if val < min_ else max_ if val > max_ else val\n",
        "        return clip(int(new))"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "maq17fLQDRjW",
        "outputId": "9eb3e6fb-2e89-450b-b5b0-edb786f068ec"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "-2147483648\n",
            "['3', '14159']\n"
          ]
        }
      ],
      "source": [
        "obj = Solution()\n",
        "print(obj.myAtoi(\"-91283472332\"))\n",
        "lst = \"3.14159 jfjkl fj\"\n",
        "print(lst.split()[0].split('.'))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "z88f6pgND4TN"
      },
      "source": [
        "## ***Jan 15:* 1345. Jump Game IV**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "KXdr3WrrEFJl"
      },
      "outputs": [],
      "source": [
        "from collections import defaultdict, deque\n",
        "class Solution:\n",
        "    def minJumps(self, arr) -> int:\n",
        "        if len(arr) == 1:\n",
        "            return 0\n",
        "        adj = defaultdict(list)\n",
        "        for i, n in enumerate(arr):\n",
        "            adj[n].append(i)\n",
        "        \n",
        "        ans = [0] * len(arr)  # the return value is ans[0], once we find it, we can return immediately.\n",
        "        dq = deque([len(arr) - 1])  # obviously, ans[-1] == 0, so we fulfill ans from ans[-1] to ans[0] iteratively\n",
        "        while dq:\n",
        "            i = dq.popleft()\n",
        "\n",
        "            # move forward if the next one has not seen before that is ans[i + 1] == 0\n",
        "            # note that the ans[len(arr) - 1] is always 0, we should NOT update it, so i < len(arr) - 1\n",
        "            if i < len(arr) - 1 and ans[i + 1] == 0 and i + 1 < len(arr) - 1:\n",
        "                ans[i + 1] = ans[i] + 1\n",
        "                dq.append(i + 1)\n",
        "\n",
        "            # move backward if the previous one has not seen before that is ans[i - 1] == 0\n",
        "            if i > 0 and ans[i - 1] == 0:\n",
        "                ans[i - 1] = ans[i] + 1\n",
        "                if i - 1 == 0: return ans[0]\n",
        "                dq.append(i - 1)\n",
        "\n",
        "            # move to j where arr[i] == arr[j]\n",
        "            for j in adj[arr[i]]:\n",
        "                if ans[j] == 0 and j < len(arr) - 1:\n",
        "                    ans[j] = ans[i] + 1\n",
        "                    if j == 0: return ans[0]\n",
        "                    dq.append(j)\n",
        "            adj.pop(arr[i])  # pop arr[i] from the adj, very very important to avoid double calculating"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "54pDR-wxKKKS",
        "outputId": "31eab6d6-474b-4588-92a8-193c213ea84f"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "3"
            ]
          },
          "execution_count": 6,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "obj = Solution()\n",
        "arr = [100,-23,-23,404,100,23,23,23,3,404]\n",
        "obj.minJumps(arr)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ISbLUljyymR8"
      },
      "source": [
        "## ***Jan 16:* 849. Maximize Distance to Closest Person**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "xdW7MZ5nyxyO"
      },
      "outputs": [],
      "source": [
        "class Solution:\n",
        "    def maxDistToClosest(self, seats) -> int:\n",
        "        \"\"\"\n",
        "        Scan the seats array (seats) to create a list of occupied\n",
        "        seats (occupied).\n",
        "        \"\"\"\n",
        "        len_seats = len(seats)\n",
        "        occupied = [k for k in range(len_seats) if seats[k] == 1]\n",
        "\n",
        "        \"\"\"\n",
        "        Use occupied to compute the maximum distance to an\n",
        "        occupied seat:\n",
        "        - Handle edge cases for the seats at the beginning and\n",
        "          end of seats that have an occupied seat on only one\n",
        "          side.\n",
        "        - Loop through occupied to handle interior seats that\n",
        "          have occupied seats on both sides\n",
        "        \"\"\"\n",
        "        max_distance = max(occupied[0], len_seats - 1 - occupied[-1])\n",
        "        len_occupied = len(occupied)\n",
        "        for k in range(1, len_occupied):\n",
        "            distance = (occupied[k] - occupied[k - 1]) // 2\n",
        "            if distance > max_distance:\n",
        "                max_distance = distance\n",
        "        return max_distance"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "E73PPeJmzFMs",
        "outputId": "f0cddcca-50cc-4028-ada1-74810eddcb84"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "2\n"
          ]
        }
      ],
      "source": [
        "obj = Solution()\n",
        "seats = [1,0,0,0,1,0,1]\n",
        "print(obj.maxDistToClosest(seats))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Ff26dOMMSH-y"
      },
      "source": [
        "## ***Jan 17:* 290. Word Pattern**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "LFXF8kbfSTuA",
        "outputId": "9e16ba99-67f7-4976-b5a2-5129372a5675"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "False\n"
          ]
        }
      ],
      "source": [
        "class Solution:\n",
        "    def wordPattern(self, pattern: str, s: str) -> bool:\n",
        "        lst = s.split()\n",
        "        match = dict()\n",
        "        if len(pattern) != len(lst) or len(set(pattern)) != len(set(lst)): return False\n",
        "        for a, val in zip(pattern, lst):\n",
        "            if a in match and match[a] != val:\n",
        "                return False\n",
        "            elif a not in match:\n",
        "                match[a] = val\n",
        "            else:\n",
        "                pass\n",
        "        return True\n",
        "        \n",
        "obj = Solution()\n",
        "print(obj.wordPattern(pattern = \"abba\", s = \"dog cat cat fish\"))"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "ffn5Qq-Qd62C",
        "outputId": "66df5c7a-4b93-4265-ad5b-1d2511af09cf"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "False\n"
          ]
        }
      ],
      "source": [
        "from collections import *\n",
        "class Solution:\n",
        "    def wordPattern(self, pattern: str, s: str) -> bool:\n",
        "        dic = defaultdict()  # the projection dict, key is the char in pattern and the value is a word\n",
        "        words = s.split(' ')\n",
        "\t\t# 'aa' -> 'dog', 'ab' -> 'dog dog', 'abc'- > 'cat dog cat'\n",
        "        if len(pattern) != len(words) or len(set(pattern)) != len(set(words)): return False\n",
        "        for i, c in enumerate(pattern):\n",
        "            if c in dic:  # c has been projected to some word\n",
        "                if dic[c] != words[i]: return False  # 'aba' -> 'cat dog dog'\n",
        "            else:\n",
        "                dic[c] = words[i]\n",
        "        return True\n",
        "obj = Solution()\n",
        "print(obj.wordPattern(pattern = \"abba\", s = \"dog cat cat fish\"))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "PELr3x-Vfp3g"
      },
      "source": [
        "## ***Jan 18:* 605. Can Place Flowers**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "vtvAzEUOf13T",
        "outputId": "f1fb44b4-69bc-40de-b016-9f5b8ea1d6cf"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "True\n",
            "None\n"
          ]
        }
      ],
      "source": [
        "class Solution:\n",
        "    def canPlaceFlowers(self, flowerbed, n: int) -> bool:\n",
        "        def is_adjecent(lst):\n",
        "            for i in range(0,len(lst)):\n",
        "                if i == 0:\n",
        "                    if lst[i] == 1 and lst[i+1] == 1:\n",
        "                        return False\n",
        "                elif i == len(lst)-1:\n",
        "                    if lst[i] == 1 and lst[i-1] == 1:\n",
        "                        return False\n",
        "                elif lst[i] == 1 and lst[i+1] != 0 and lst[i-1] != 0:\n",
        "                    return False\n",
        "            return True\n",
        "        print(is_adjecent([1,0,0,0,1]))\n",
        "obj = Solution()\n",
        "print(obj.canPlaceFlowers(flowerbed = [1,0,0,0,1], n = 1))"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "CkdakzLKoz_t",
        "outputId": "a9b29e1c-6e17-4e8e-8b5d-d995bdd15c80"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "True\n"
          ]
        }
      ],
      "source": [
        "class Solution:\n",
        "    def canPlaceFlowers(self, flowerbed, n: int) -> bool:\n",
        "        \n",
        "        count = 0\n",
        "        prev = 0\n",
        "        last = 0\n",
        "        \n",
        "        for i in range(len(flowerbed)-1):\n",
        "            if flowerbed[i] == 0 and prev == 0 and flowerbed[i+1] == 0:\n",
        "                prev = 1\n",
        "                count += 1\n",
        "            else:\n",
        "                prev = flowerbed[i]\n",
        "                \n",
        "        if prev == 0 and flowerbed[-1] == 0 and last == 0:\n",
        "            prev = 1\n",
        "            count += 1\n",
        "                    \n",
        "        return count >= n\n",
        "obj = Solution()\n",
        "print(obj.canPlaceFlowers(flowerbed = [1,0,0,0,1], n = 1))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "k-XTzhpDEyJK"
      },
      "source": [
        "## ***Jan 19:* 142. Linked List Cycle II**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "O-aN1nTAE6W6"
      },
      "outputs": [],
      "source": [
        "# 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 detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
        "        visited = set()\n",
        "        \n",
        "        while head:\n",
        "            if head in visited:\n",
        "                return head\n",
        "            else:\n",
        "                visited.add(head)\n",
        "                head = head.next\n",
        "        return None"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "P9EcBNYrdx48"
      },
      "source": [
        "## ***Jan 20:* 875. Koko Eating Bananas**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "L1f2BB3Nd0JZ",
        "outputId": "1ba46291-0306-45d1-8abd-1a6d718dc928"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "4\n"
          ]
        }
      ],
      "source": [
        "import math\n",
        "class Solution:\n",
        "    def minEatingSpeed(self, piles, h: int) -> int:\n",
        "        #If the length of the piles is equal to the H, return max(piles)\n",
        "        if h == len(piles):\n",
        "            return max(piles)\n",
        "        \n",
        "        #Binary search\n",
        "\t      #Koko could each at least 1 banana and at most max(piles) bananas each time\n",
        "        lo, hi = 1, max(piles)\n",
        "        \n",
        "        while lo < hi:\n",
        "            #Get the mid number of bananas to eat\n",
        "            mid = (lo+hi) // 2\n",
        "            #Calculate how many hours that koko need to finish eating all of the piles given the eating speed mid \n",
        "            H = 0\n",
        "            for p in piles:\n",
        "                if p < mid:\n",
        "                    H += 1\n",
        "                else:\n",
        "                    H += math.ceil(p/mid)\n",
        "            \n",
        "            #If the time that koko need is less than or equal to H, we need to search for the left part\n",
        "            if H <= h:\n",
        "                hi = mid\n",
        "            #If the time that koko need is bigger than H, we need to search for the right part\n",
        "            else:\n",
        "                lo = mid + 1\n",
        "                \n",
        "        return lo\n",
        "\n",
        "obj = Solution()\n",
        "print(obj.minEatingSpeed(piles = [3,6,7,11], h = 8))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "h2dA7LQv-KNu"
      },
      "source": [
        "## ***Jan 21:* 134. Gas Station**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Lb_itmMF-yFa",
        "outputId": "78b4bb10-7b1d-4783-8aeb-3375d6403f79"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "3\n"
          ]
        }
      ],
      "source": [
        "class Solution:\n",
        "    def canCompleteCircuit(self, gas, cost) -> int:\n",
        "        trip_tank, curr_tank, start, n = 0, 0, 0, len(gas)\n",
        "        for i in range(n):\n",
        "            trip_tank += gas[i] - cost[i]\n",
        "            curr_tank += gas[i] - cost[i]\n",
        "            if curr_tank < 0:\n",
        "                start = i + 1\n",
        "                curr_tank = 0 \n",
        "        return start if trip_tank >= 0 else -1\n",
        "obj = Solution()\n",
        "print(obj.canCompleteCircuit(gas = [1,2,3,4,5], cost = [3,4,5,1,2]))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "BEndaYduxSbK"
      },
      "source": [
        "## ***Jan 22:* 1510. Stone Game IV**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "CI25SN4cxahX",
        "outputId": "d723d381-5a77-4200-fa94-6356b1a4a1e5"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "True\n"
          ]
        }
      ],
      "source": [
        "class Solution:\n",
        "    def winnerSquareGame(self, n: int) -> bool:\n",
        "        dp = [False] * (n + 1)\n",
        "        for i in range(1, n + 1):\n",
        "            for k in range(1, int(i**0.5)+1):\n",
        "                lst.append(dp[i - k * k])\n",
        "            dp[i]not all(lst)\n",
        "            # dp[i] = not all(dp[i - k * k] for k in range(1, int(i**0.5) + 1))\n",
        "        return dp[-1]\n",
        "obj = Solution()\n",
        "print(obj.winnerSquareGame(10))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "i3hAt5ELQVnK"
      },
      "source": [
        "## ***Jan 23:* 1291. Sequential Digits**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "rKdfhltKQbfs",
        "outputId": "cbd47543-87b8-4576-94af-85659099834a"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "[67, 78, 89, 123]\n"
          ]
        }
      ],
      "source": [
        "class Solution:\n",
        "    def sequentialDigits(self, low: int, high: int):\n",
        "        def creat_digit(l,low,high):\n",
        "            lst = ['1','2','3','4','5','6','7','8','9']\n",
        "            ret = []\n",
        "            i = 0\n",
        "            while l < 10:\n",
        "                val = ''.join(lst[i:l])\n",
        "                val = int(val)\n",
        "                if val <= high and val >= low:\n",
        "                  ret.append(val)\n",
        "                i += 1\n",
        "                l += 1\n",
        "            return ret\n",
        "\n",
        "        answer = []    \n",
        "        for i in range(len(str(low)), len(str(high)) + 1):\n",
        "            answer += creat_digit(i,low, high)\n",
        "        return answer\n",
        "               \n",
        "\n",
        "low = 1000; high = 130000\n",
        "low = 58; high = 155\n",
        "obj = Solution()\n",
        "print(obj.sequentialDigits(low, high))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "O_cr-vowT_v0"
      },
      "source": [
        "## ***Jan 24:* Check Captals**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "KdFLxnKhT9GQ",
        "outputId": "ad9e7549-d4ed-48a2-b954-f7f24a14f4bc"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "True\n"
          ]
        }
      ],
      "source": [
        "class Solution:\n",
        "    def detectCapitalUse(self, word: str) -> bool:\n",
        "        if len(word) < 2: return True\n",
        "        if word[0].isupper() and word[1].isupper():\n",
        "            for i in range(2, len(word)):\n",
        "                if word[i].islower(): return False\n",
        "        else:\n",
        "            for i in range(1, len(word)):\n",
        "                if word[i].isupper(): return False\n",
        "        return True\n",
        "        \n",
        "obj = Solution()\n",
        "print(obj.detectCapitalUse(\"USA\"))"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## ***Jan 25:* 941. Valid Mountain Array**"
      ],
      "metadata": {
        "id": "VB4Y5DrOdN3z"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "class Solution:\n",
        "    def validMountainArray(self, arr) -> bool:\n",
        "        if len(arr) < 3:\n",
        "            return False\n",
        "        y = False\n",
        "        j = 0\n",
        "        for i in range(len(arr)-1):\n",
        "            if arr[i] >= arr[i+1] and i == 0:\n",
        "                return False\n",
        "            if arr[i] >= arr[i+1]:\n",
        "                print(arr[i],i)\n",
        "                y = True\n",
        "                j = i\n",
        "                break\n",
        "        i = 0\n",
        "        while (y and i < j):\n",
        "            if arr[i] <= arr[i+1]:\n",
        "                return False\n",
        "                j = i\n",
        "                break\n",
        "            i += 1\n",
        "        return True\n",
        "obj = Solution()\n",
        "nums = [2,1]\n",
        "nums = [3,5,5]\n",
        "nums = [0,3,2,1]\n",
        "nums = [9,8,7,6,5,4,3,2,1,0]\n",
        "print(obj.validMountainArray(nums))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "HEvxIuyMdTKV",
        "outputId": "77811cb7-a616-4bd0-d12d-1e0da87b4510"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "9 0\n",
            "True\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "class Solution:\n",
        "    def validMountainArray(self, arr: List[int]) -> bool:\n",
        "        if len(arr) < 3:\n",
        "            return False\n",
        "        y = False\n",
        "        j = 0\n",
        "        for i in range(len(arr)-1):\n",
        "            if arr[i] > arr[i+1]:\n",
        "                # y = True\n",
        "                j = i\n",
        "                break\n",
        "        for i in range(j,len(arr)-1):\n",
        "            if arr[i] < arr[i+1]:\n",
        "                return False\n",
        "                j = i\n",
        "                break\n",
        "        return True"
      ],
      "metadata": {
        "id": "y0Vgxugkf_x5"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "class Solution:\n",
        "    def validMountainArray(self, arr) -> bool:\n",
        "        if len(arr) < 3: return False;\n",
        "        l = 0;\n",
        "        r = len(arr) - 1\n",
        "        while l + 1 < len(arr) - 1 and arr[l] < arr[l + 1]: \n",
        "            l += 1\n",
        "        while r - 1 > 0 and arr[r] < arr[r - 1]: \n",
        "            r -= 1\n",
        "        return l == r\n",
        "obj = Solution()\n",
        "nums = [2,1]\n",
        "nums = [3,5,5]\n",
        "nums = [0,3,2,1]\n",
        "nums = [9,8,7,6,5,4,3,2,1,0]\n",
        "print(obj.validMountainArray(nums))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Zuy02QHTk-GB",
        "outputId": "6dc21c54-10e3-40d1-e7e9-dc1b3ec66c98"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "False\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## ***Jan 27:* 421. Maximum XOR of Two Numbers in an Array**\n",
        "\n",
        "A XOR B = (A AND !B) OR (!A AND B)\n",
        "\n",
        "(hint : 1^0 = 1 and 1^1 = 0^0 = 0)"
      ],
      "metadata": {
        "id": "3q39t1PHTEAL"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "from math import *\n",
        "nums = [3,10,5,25,2,8]\n",
        "nums = [14,70,53,83,49,91,36,80,92,51,66,70]\n",
        "result = -inf\n",
        "for i in range(len(nums)):\n",
        "  for j in range(len(nums)):\n",
        "    result = max(result, nums[i] ^ nums[j])\n",
        "print(result)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "IvvOsjTrTAEX",
        "outputId": "00ecedd9-f0c9-4ba9-85ac-5d08ccee3be4"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "127\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "from typing import List\n",
        "\n",
        "\n",
        "class Solution:\n",
        "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
        "        \"\"\"\n",
        "        let ni and nj be the numbers such that xor between them produces maximum\n",
        "        value among other pairs. let m be the max value.\n",
        "\n",
        "        m = ni ^ nj\n",
        "        => m ^ nj = (ni ^ nj) ^ nj\n",
        "        =>        = ni ^ (nj ^ nj) # xor is associative\n",
        "        =>        = ni ^ 0\n",
        "        =>        = ni\n",
        "\n",
        "        so, m ^ nj = ni\n",
        "\n",
        "        We note that m is 31-bit integer so we guess bits of m and and with each nj,\n",
        "        we check if the combination of m and nj will produce ni.\n",
        "\n",
        "        So time complexity becomes O(32N) = O(N)\n",
        "        :param nums:\n",
        "        :return:\n",
        "        \"\"\"\n",
        "        m, mask = 0, 0\n",
        "\n",
        "        for i in range(32)[::-1]:\n",
        "            mask |= 1 << i\n",
        "            prefixes = {n & mask for n in nums}\n",
        "\n",
        "            tmp = m | (1 << i)\n",
        "\n",
        "            if any(prefix ^ tmp in prefixes for prefix in prefixes):\n",
        "                m = tmp\n",
        "\n",
        "        return m\n",
        "nums = [3,10,5,25,2,8]\n",
        "nums = [14,70,53,83,49,91,36,80,92,51,66,70]\n",
        "obj = Solution()\n",
        "print(obj.findMaximumXOR(nums))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "CJlXcOvSeEen",
        "outputId": "f0171aa8-48ef-433c-cd4d-f23ed06c0dc2"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "127\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## ***Jan 28:* 211. Design Add and Search Words Data Structure**"
      ],
      "metadata": {
        "id": "EBt8-wVibp0E"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "import collections\n",
        "# class WordDictionary:\n",
        "\n",
        "#     def __init__(self):\n",
        "        \n",
        "\n",
        "#     def addWord(self, word: str) -> None:\n",
        "        \n",
        "\n",
        "#     def search(self, word: str) -> bool:\n",
        "        \n",
        "\n",
        "\n",
        "# Your WordDictionary object will be instantiated and called as such:\n",
        "# obj = WordDictionary()\n",
        "# obj.addWord(word)\n",
        "# param_2 = obj.search(word)\n",
        "class TrieNode():\n",
        "    def __init__(self):\n",
        "        self.children = collections.defaultdict(TrieNode)\n",
        "        self.isWord = False\n",
        "    \n",
        "class WordDictionary(object):\n",
        "    def __init__(self):\n",
        "        self.root = TrieNode()\n",
        "\n",
        "    def addWord(self, word):\n",
        "        node = self.root\n",
        "        for w in word:\n",
        "            node = node.children[w]\n",
        "        node.isWord = True\n",
        "\n",
        "    def search(self, word):\n",
        "        node = self.root\n",
        "        self.res = False\n",
        "        self.dfs(node, word)\n",
        "        return self.res\n",
        "    \n",
        "    def dfs(self, node, word):\n",
        "        if not word:\n",
        "            if node.isWord:\n",
        "                self.res = True\n",
        "            return \n",
        "        if word[0] == \".\":\n",
        "            for n in node.children.values():\n",
        "                self.dfs(n, word[1:])\n",
        "        else:\n",
        "            node = node.children.get(word[0])\n",
        "            if not node:\n",
        "                return \n",
        "            self.dfs(node, word[1:])\n",
        "\n",
        "obj = WordDictionary()\n",
        "obj.addWord(\"dad\")\n",
        "param_2 = obj.search(\"dad\")\n",
        "print(param_2)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "4llWyMGebrpa",
        "outputId": "18a6a6cf-e497-4464-e139-8d1f26d89092"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "True\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## ***Jan 29:* 84. Largest Rectangle in Histogram**"
      ],
      "metadata": {
        "id": "S9BCK9k79hRJ"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "class Solution:\n",
        "    def largestRectangleArea(self, heights) -> int:\n",
        "        heights.append(0)\n",
        "        stack = [-1]\n",
        "        ans = 0\n",
        "        for i in range(len(heights)):\n",
        "            while heights[i] < heights[stack[-1]]:\n",
        "                h = heights[stack.pop()]\n",
        "                w = i - stack[-1] - 1\n",
        "                ans = max(ans, h * w)\n",
        "            stack.append(i)\n",
        "        heights.pop()\n",
        "        return ans\n",
        "obj = Solution()\n",
        "print(obj.largestRectangleArea(heights = [2,1,5,6,2,3]))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "CysGGkoW9rMb",
        "outputId": "010044d4-9f5f-4ff5-81aa-cd4875ed52c4"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "10\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## ***Jan 30:* 189. Rotate Array**"
      ],
      "metadata": {
        "id": "h1yuVcg8NupY"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "class Solution:\n",
        "    def rotate(self, nums, k: int) -> None:\n",
        "        \"\"\"\n",
        "        Do not return anything, modify nums in-place instead.\n",
        "        \"\"\"\n",
        "        for i in range(k):\n",
        "            val = nums.pop()\n",
        "            nums.insert(0,val)\n",
        "        print(nums)\n",
        "obj = Solution()\n",
        "nums = [1,2,3,4,5,6,7]; k = 3\n",
        "print(obj.rotate(nums,k))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "6b8dDzxzVU2v",
        "outputId": "99ff5df9-c1e1-460a-9803-de3080526b98"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[5, 6, 7, 1, 2, 3, 4]\n",
            "None\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "class Solution:\n",
        "    def rotate(self, nums, k: int) -> None:\n",
        "        \"\"\"\n",
        "        Do not return anything, modify nums in-place instead.\n",
        "        \"\"\"\n",
        "        k = k % len(nums)\n",
        "        nums[:] = nums[-k:] + nums[:-k]\n",
        "        print(nums)\n",
        "obj = Solution()\n",
        "nums = [1,2,3,4,5,6,7]; k = 3\n",
        "print(obj.rotate(nums,k))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "ZRwhSeXaNy0n",
        "outputId": "4223584e-7e32-4c90-f373-527524f4cf03"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[5, 6, 7, 1, 2, 3, 4]\n",
            "None\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "LB74Ic6RFX3k"
      },
      "source": [
        "# **Weekly Contest 274**"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "mQGsrMmGFb4N"
      },
      "source": [
        "## **2124. Check if All A's Appears Before All B's**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "l2Ky_luKvxP8"
      },
      "outputs": [],
      "source": [
        "class Solution:\n",
        "    def checkString(self, s: str) -> bool:\n",
        "        if 'ba' in s:\n",
        "            return False\n",
        "        else:\n",
        "            return True"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "QcCJavZmv0is",
        "outputId": "1e4c25e7-29e5-4f4b-e7dc-7bc071526b11"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "False\n"
          ]
        }
      ],
      "source": [
        "obj1 = Solution()\n",
        "print(obj1.checkString(\"aaababb\"))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "obXWXz5tFeWE"
      },
      "source": [
        "## **2125. Number of Laser Beams in a Bank**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "27NvkgJZwKUD"
      },
      "outputs": [],
      "source": [
        "bank = [\"011001\",\"000000\",\"010100\",\"001000\"]\n",
        "beams = []\n",
        "for i in range(len(bank)):\n",
        "  if '1' not in bank[i]:\n",
        "    continue\n",
        "  else:\n",
        "    beam = 0\n",
        "    for j in range(i):\n",
        "      if bank[i][j] == '1':\n",
        "        beam += 1\n",
        "    beams.append(beam)\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "QJFfbL9n1kq0",
        "outputId": "275f974d-dcea-4ca4-b5f8-715d80710e15"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "[3, 0, 2, 1]\n",
            "8\n"
          ]
        }
      ],
      "source": [
        "beam = []\n",
        "bank = [\"011001\",\"000000\",\"010100\",\"001000\"]\n",
        "# bank = [\"000\",\"111\",\"000\"]\n",
        "for i in bank:\n",
        "  beam.append(i.count('1'))\n",
        "print(beam)\n",
        "no_of_beams = 0\n",
        "first = beam[0]\n",
        "second = 0\n",
        "for i in range(1, len(beam)):\n",
        "  if beam[i] == 0:\n",
        "    continue\n",
        "  else:\n",
        "    second = beam[i]\n",
        "    no_of_beams += first * second\n",
        "  first = second\n",
        "print(no_of_beams)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "1Opd7D4jHMmQ"
      },
      "source": [
        "# **Biweekly Contest 69**"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "EkYGok8jNxmA"
      },
      "source": [
        "## **5960. Capitalize the Title**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "V1YeZ-83HRBe",
        "outputId": "708fca1f-682c-4d5b-e648-33f6bd361573"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "\n",
            "['Capitalize', 'He', 'Title']\n",
            "Capitalize he Title\n",
            "2\n"
          ]
        }
      ],
      "source": [
        "title = \"capiTalIze He titLe\"\n",
        "print()\n",
        "new_str = ''\n",
        "val = title.title().split()\n",
        "print(val)\n",
        "for i in range(len(val)):\n",
        "  if len(val[i]) <= 2:\n",
        "    new_str += val[i].lower() + ' '\n",
        "  else:\n",
        "    new_str += val[i] + ' '\n",
        "print(new_str[:-1])  \n",
        "\n",
        "print(len(val[1]))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Jw3OeV0ZOE6G"
      },
      "source": [
        "## **5961. Maximum Twin Sum of a Linked List**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "461zNQ3sJkt8"
      },
      "outputs": [],
      "source": [
        "class ListNode:\n",
        "    def __init__(self, val=0, next=None):\n",
        "        self.val = val\n",
        "        self.next = next\n",
        "class Solution:\n",
        "    def pairSum(self, head) -> int:\n",
        "        array = []\n",
        "        curr = head\n",
        "        while curr:\n",
        "            array.append(curr.val)\n",
        "            curr = curr.next\n",
        "        print(array)\n",
        "        "
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "_AGQzJlHSxK_",
        "outputId": "b78cd2b9-27f3-452b-d100-696a227f9a76"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "7\n",
            "4\n",
            "7\n"
          ]
        }
      ],
      "source": [
        "head = [0, 1,-2,-1]\n",
        "# head = [5, 4, 2, 1]\n",
        "head = [4, 2, 2, 3]\n",
        "max_sum = 0\n",
        "curr_sum = 0\n",
        "n = len(head)\n",
        "for i in range(int(n/2)):\n",
        "  curr_sum = head[i] + head[-(i+1)]\n",
        "  max_sum = max(max_sum, curr_sum)\n",
        "  print(curr_sum)\n",
        "print(max_sum)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "x0So8MlBXNkQ"
      },
      "source": [
        "## **5962. Longest Palindrome by Concatenating Two Letter Words**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "ieqmAxHMX5Re"
      },
      "outputs": [],
      "source": [
        "from itertools import permutations\n",
        "total = []\n",
        "largest = 0\n",
        "curr = 0\n",
        "# words = [\"lc\",\"cl\",\"gg\"]\n",
        "words = [\"ab\",\"ty\",\"yt\",\"lc\",\"cl\",\"ab\"]\n",
        "words = [\"cc\",\"ll\",\"xx\"]\n",
        "words = [\"dd\",\"aa\",\"bb\",\"dd\",\"aa\",\"dd\",\"bb\",\"dd\",\"aa\",\"cc\",\"bb\",\"cc\",\"dd\",\"cc\"]\n",
        "lst_count = []\n",
        "for i in range(len(words)+1):\n",
        "  perm = permutations(words, i)\n",
        "  for j in list(perm):\n",
        "    total.append(list(j))\n",
        "total = total[1:]\n",
        "print(total)\n",
        "for sub in total:\n",
        "  is_pal = ''.join(sub)\n",
        "  if is_pal == is_pal[::-1]:\n",
        "    print(is_pal)\n",
        "    curr = len(is_pal)\n",
        "    lst_count.append(curr)\n",
        "    # largest = max(curr, largest)\n",
        "print(max(lst_count))\n",
        "\n",
        "# Not Working this Idea"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "hALuDeplhJqn"
      },
      "outputs": [],
      "source": [
        "from collections import Counter\n",
        "# Counter is basically here creating a dictionary of \n",
        "# all the occurences against their count in words list\n",
        "class Solution:\n",
        "    def longestPalindrome(self, words) -> int:\n",
        "        c = Counter(words)\n",
        "        ans = 0\n",
        "        ans2 = 0\n",
        "        t = 0\n",
        "        for i in c:\n",
        "            if i == i[::-1]:\n",
        "                ans2 += c[i]//2*2\n",
        "                t += c[i]%2\n",
        "            elif i < i[::-1]:\n",
        "                ans += min(c[i], c[i[::-1]])*2\n",
        "        print(ans, ans2, t)\n",
        "        return (ans+ans2+min(t, 1))*2"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "NCTHwFk6hgMg",
        "outputId": "29dea859-4448-4259-ae9d-df5827770ff5"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "0 10 4\n",
            "22\n"
          ]
        }
      ],
      "source": [
        "obj = Solution()\n",
        "# words = [\"lc\",\"cl\",\"gg\"]\n",
        "words = [\"ab\",\"ty\",\"yt\",\"lc\",\"cl\",\"ab\"]\n",
        "words = [\"cc\",\"ll\",\"xx\"]\n",
        "words = [\"dd\",\"aa\",\"bb\",\"dd\",\"aa\",\"dd\",\"bb\",\"dd\",\"aa\",\"cc\",\"bb\",\"cc\",\"dd\",\"cc\"]\n",
        "print(obj.longestPalindrome([\"dd\",\"aa\",\"bb\",\"dd\",\"aa\",\"dd\",\"bb\",\"dd\",\"aa\",\"cc\",\"bb\",\"cc\",\"dd\",\"cc\"]))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "pPmUQr67xEFk"
      },
      "source": [
        "# **Weekly Contest 275**"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "j_e_a9l06Bbz"
      },
      "source": [
        "## **5976. Check if Every Row and Column Contains All Numbers**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "SObZqvUP5HPV"
      },
      "outputs": [],
      "source": [
        "class Solution:\n",
        "    def checkValid(self, matrix) -> bool:\n",
        "        if len(matrix) == 1:\n",
        "            return True\n",
        "        n = len(matrix)\n",
        "        c = {}\n",
        "        for i in range(1, n+1):\n",
        "            if i not in c:\n",
        "                c[i] = 1\n",
        "            else:\n",
        "                c[i] += 1\n",
        "        \n",
        "        for i in range(0, len(matrix)):\n",
        "            nc = Counter(matrix[i])\n",
        "            if c != nc:\n",
        "                return False\n",
        "        \n",
        "        def column(matrix, i):\n",
        "            return [row[i] for row in matrix]\n",
        "        \n",
        "        for i, j in enumerate(matrix):\n",
        "            col = column(matrix, i)\n",
        "            nc = Counter(col)\n",
        "            if c != nc:\n",
        "                return False  \n",
        "            \n",
        "        return True"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "xGcChOZ2xTY1",
        "outputId": "791d9ffb-45ef-441e-9c74-033b9d3b4d26"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "False\n"
          ]
        }
      ],
      "source": [
        "matrix = [[1,1,1],[1,2,3],[1,2,3]]\n",
        "# matrix = [[1,2,3],[3,1,2],[2,3,1]]\n",
        "# matrix = [[1]]\n",
        "obj = Solution()\n",
        "print(obj.checkValid(matrix))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aZptK1T7593T"
      },
      "source": [
        "## **5977. Minimum Swaps to Group All 1's Together II**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "SEJy6pG56aHb"
      },
      "outputs": [],
      "source": [
        "# Copied and Understanded\n",
        "class Solution:\n",
        "    def minSwaps(self, nums) -> int:\n",
        "        n1 = sum(nums)\n",
        "        cur = sum(nums[:n1])\n",
        "        ans = n1\n",
        "        for i in range(len(nums)):\n",
        "            ans = min(ans, n1 - cur)                # Minimum no of swaps\n",
        "            cur += nums[(i + n1) % len(nums)]       # For Circular array\n",
        "            cur -= nums[i]\n",
        "        return ans"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "h91xQC9QH6l6",
        "outputId": "b021db43-c8a9-4443-a38d-41981dbd8c58"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "2"
            ]
          },
          "execution_count": 52,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "obj = Solution()\n",
        "obj.minSwaps(nums = [0,1,1,1,0,0,1,1,0])"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "2bKMMq1p0h8I"
      },
      "source": [
        "# **Weekly Contest 276**"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "DuWe8kNbu9bX"
      },
      "source": [
        "## **5980. Divide a String Into Groups of Size k**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "zgZMHOpGu-C5"
      },
      "outputs": [],
      "source": [
        "class Solution:\n",
        "    def divideString(self, s: str, k: int, fill: str):\n",
        "        l = len(s)\n",
        "        # e = 0\n",
        "        if l % k != 0:\n",
        "            extra = fill * (k - (l % k))\n",
        "            s += extra\n",
        "            # e = 1\n",
        "        lst = []\n",
        "        st = 0\n",
        "        ls = k\n",
        "        # e += k\n",
        "        print(s)\n",
        "        e = len(s) // k\n",
        "        print(e)\n",
        "        for i in range(e):\n",
        "            grp = s[st:ls]\n",
        "            lst.append(grp)\n",
        "            st = ls\n",
        "            ls += k\n",
        "        return lst\n",
        "        "
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "sixbxdimxNeE",
        "outputId": "046bc83f-3b39-4f9f-faa8-31de9f69b427"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "ctoyjrwtngqwtnnn\n",
            "2\n",
            "['ctoyjrwt', 'ngqwtnnn']\n"
          ]
        }
      ],
      "source": [
        "obj = Solution()\n",
        "# s = \"abcdefghij\"; k = 3; fill = \"x\"\n",
        "s = \"ctoyjrwtngqwt\"\n",
        "k = 8\n",
        "fill = \"n\"                        # [\"ctoyjrwt\",\"ngqwtnnn\",\"\",\"\",\"\",\"\",\"\",\"\",\"\"]\n",
        "print(obj.divideString(s,k,fill))\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0Hcc-JwH0mm4"
      },
      "source": [
        "## **5194. Minimum Moves to Reach Target Score**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "ZLKqg06s0B2z"
      },
      "outputs": [],
      "source": [
        "class Solution:\n",
        "    def minMoves(self, target: int, maxDoubles: int) -> int:\n",
        "        to_ret = 0\n",
        "        while target > 1 :\n",
        "            if maxDoubles == 0 :\n",
        "                to_ret += target - 1\n",
        "                break\n",
        "            if target % 2 == 1 :\n",
        "                to_ret += 1\n",
        "                target -= 1\n",
        "            else :\n",
        "                to_ret += 1\n",
        "                target = target // 2\n",
        "                maxDoubles -= 1\n",
        "        return to_ret"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "bbnsxvVHaAca",
        "outputId": "c548fd1a-9106-4824-a824-48a507d4643b"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "7\n"
          ]
        }
      ],
      "source": [
        "obj = Solution()\n",
        "print(obj.minMoves(target = 19, maxDoubles = 2))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "hzx_0H-mefti"
      },
      "source": [
        "## **2140. Solving Questions With Brainpower**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "OU6cXEa_eka6"
      },
      "outputs": [],
      "source": [
        "class Solution:\n",
        "    def mostPoints(self, questions) -> int:\n",
        "      lst = [0]*200;\n",
        "      for i in range(len(questions)-1, -1, -1):\n",
        "          lst[i] = max(lst[i+1],questions[i][0] + lst[i + questions[i][1] + 1])\n",
        "\n",
        "      return lst[0]"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "ocdNet3EpAK1",
        "outputId": "9f7e2bd4-35a0-42b4-91f4-998356b7831f"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "7\n"
          ]
        }
      ],
      "source": [
        "obj = Solution()\n",
        "questions = [[3,2],[4,3],[4,4],[2,5]]\n",
        "questions = [[1,1],[2,2],[3,3],[4,4],[5,5]]\n",
        "print(obj.mostPoints(questions))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "JIAUSL3ZM_0r"
      },
      "source": [
        "# **Biweekly Contest 70**"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "p9W3BMvUNC3t"
      },
      "source": [
        "## **5971. Minimum Cost of Buying Candies With Discount**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "YPizyCEdNCOr",
        "outputId": "1b830b3f-aa0a-4a97-eb2d-fe79f67d4e89"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "[9, 7, 6, 5, 2, 2]\n",
            "9\n",
            "7\n",
            "5\n",
            "2\n",
            "23\n"
          ]
        }
      ],
      "source": [
        "# It is clear from the test cases and the question statment also \n",
        "# that in cost list in sorted form sum of every second index is the result \n",
        "class Solution:\n",
        "    def minimumCost(self, cost) -> int:\n",
        "        a=sorted(cost)[::-1]\n",
        "        print(a)\n",
        "        s=0\n",
        "        for i in range(len(a)):\n",
        "            if i%3!=2:\n",
        "                print(a[i])\n",
        "                s+=a[i]\n",
        "        return s\n",
        "obj = Solution()\n",
        "cost = [6,5,7,9,2,2]\n",
        "print(obj.minimumCost(cost))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "eODm2whSRJFp"
      },
      "source": [
        "## **2148. Count the Hidden Sequences**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "5R_kQN2HRLRb",
        "outputId": "ebd42854-5080-4cd8-d640-69f71405ab8e"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "(59, [[-6, -46], [-5, -45], [-4, -44], [-3, -43], [-2, -42], [-1, -41], [0, -40], [1, -39], [2, -38], [3, -37], [4, -36], [5, -35], [6, -34], [7, -33], [8, -32], [9, -31], [10, -30], [11, -29], [12, -28], [13, -27], [14, -26], [15, -25], [16, -24], [17, -23], [18, -22], [19, -21], [20, -20], [21, -19], [22, -18], [23, -17], [24, -16], [25, -15], [26, -14], [27, -13], [28, -12], [29, -11], [30, -10], [31, -9], [32, -8], [33, -7], [34, -6], [35, -5], [36, -4], [37, -3], [38, -2], [39, -1], [40, 0], [41, 1], [42, 2], [43, 3], [44, 4], [45, 5], [46, 6], [47, 7], [48, 8], [49, 9], [50, 10], [51, 11], [52, 12]])\n",
            "None\n"
          ]
        }
      ],
      "source": [
        "class Solution:\n",
        "    def numberOfArrays(self, differences, lower: int, upper: int) -> int:\n",
        "        def generate_sequences(diff,lower,upper):\n",
        "            l = lower\n",
        "            u = upper\n",
        "            sequences = []\n",
        "            for i in range(lower, upper):\n",
        "                val = i\n",
        "                seq = []\n",
        "                seq.append(i)\n",
        "                to_append = True\n",
        "                for j in range(len(diff)):\n",
        "                    val += diff[j]\n",
        "                    seq.append(val)\n",
        "                for k in range(len(seq)):\n",
        "                  if seq[k] not in range(l, u+1):\n",
        "                    to_append = False\n",
        "                  \n",
        "                if to_append:\n",
        "                  sequences.append(seq)\n",
        "            return len(sequences), sequences\n",
        "        \n",
        "        print(generate_sequences(differences, lower, upper))\n",
        "\n",
        "obj = Solution()\n",
        "differences = [-40]; lower = -46; upper = 53\n",
        "# differences = [94357]; lower = -45280; upper = 54014\n",
        "# differences = [1,-3,4]; lower = 1; upper = 6\n",
        "# differences = [3,-4,5,1,-2]; lower = -4; upper = 5\n",
        "print(obj.numberOfArrays(differences, lower, upper))"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "-4gKtn_VmCI1",
        "outputId": "7a7fd350-0579-4da4-8c08-a9a720dd6a8f"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "None\n"
          ]
        }
      ],
      "source": [
        "class Solution:\n",
        "    def numberOfArrays(self, differences, lower: int, upper: int) -> int:\n",
        "        def generate_sequences(diff,lower,upper):\n",
        "            l = lower\n",
        "            u = upper\n",
        "            sequences = 0\n",
        "            for i in range(lower, upper):\n",
        "                val = i\n",
        "                seq = []\n",
        "                seq.append(i)\n",
        "                to_append = True\n",
        "                for j in range(len(differences)):\n",
        "                    val += differences[j]\n",
        "                    seq.append(val)\n",
        "                for k in range(len(seq)):\n",
        "                    if seq[k] not in range(l, u+1):\n",
        "                        to_append = False\n",
        "                  \n",
        "                if to_append:\n",
        "                    sequences +=1\n",
        "            if len(differences) == 1:\n",
        "                return sequences + 1\n",
        "            return sequences\n",
        "\n",
        "obj = Solution()\n",
        "differences = [-40]; lower = -46; upper = 53\n",
        "# differences = [94357]; lower = -45280; upper = 54014\n",
        "# differences = [1,-3,4]; lower = 1; upper = 6\n",
        "# differences = [3,-4,5,1,-2]; lower = -4; upper = 5\n",
        "print(obj.numberOfArrays(differences, lower, upper))"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "M5O_FSNgjnqx",
        "outputId": "58cbf806-2a5f-48f8-f2f0-6e268c3fa785"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "-1 5\n",
            "4\n"
          ]
        }
      ],
      "source": [
        "class Solution:\n",
        "    def numberOfArrays(self, differences, lower: int, upper: int) -> int:\n",
        "        min_ = 0\n",
        "        max_ = 0\n",
        "        curr = 0\n",
        "        for d in differences:\n",
        "            curr += d\n",
        "            min_ = min(curr, min_)\n",
        "            max_ = max(curr, max_)\n",
        "        print(min_,max_)\n",
        "        low_range = lower - min_\n",
        "        high_range = upper - max_\n",
        "        return max(high_range - low_range + 1, 0)\n",
        "\n",
        "obj = Solution()\n",
        "differences = [-40]; lower = -46; upper = 53\n",
        "# differences = [94357]; lower = -45280; upper = 54014\n",
        "# differences = [1,-3,4]; lower = 1; upper = 6\n",
        "differences = [3,-4,5,1,-2]; lower = -4; upper = 5\n",
        "print(obj.numberOfArrays(differences, lower, upper))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "xz_PKT0uznEc"
      },
      "source": [
        "# **Weekly Contest 277**"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "f-6bxuVe9RR7"
      },
      "source": [
        "## **2148. Count Elements With Strictly Smaller and Greater Elements**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "V6G8aadjzqnO",
        "outputId": "1e75304d-54bc-4df7-a22f-39d133cb40bb"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "[-89, 39]\n",
            "0\n"
          ]
        }
      ],
      "source": [
        "class Solution:\n",
        "    def countElements(self, nums) -> int:\n",
        "        nums.sort()\n",
        "        st = nums.count(nums[0])\n",
        "        if st > 1:\n",
        "            nums = nums[st-1:]\n",
        "        en = nums.count(nums[-1])\n",
        "        if en > 1:\n",
        "            l = len(nums)\n",
        "            nums = nums[:l-en+1]\n",
        "        print(nums)\n",
        "        if len(set(nums))<=2:\n",
        "            return 0\n",
        "        return len(nums)-2\n",
        "nums = [-71,-71,93,-71,40]\n",
        "nums = [-89,39,39,-89,39,39]\n",
        "# nums = [11,7,2,15]\n",
        "# nums = [-3,3,3,90]\n",
        "# nums = [-65,-65,50,-65,50,-55,-65,-65]\n",
        "nums = [-89,39,39,-89,39,39]\n",
        "obj = Solution()\n",
        "print(obj.countElements(nums))"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "oTVUHf3V15ju",
        "outputId": "599967a0-eb21-42cc-e918-b2defde094ee"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "3\n"
          ]
        }
      ],
      "source": [
        "# nums = [-71,-71,93,-71,40]\n",
        "nums = [-89,39,39,-89,39,39]\n",
        "nums = [40,40,93,32,6,-71,40]\n",
        "nums = [-71,6,25,17,32,40,40,40]\n",
        "print(nums.count(nums[0]))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "H1wVUnEc9VHL"
      },
      "source": [
        "## **5991. Rearrange Array Elements by Sign**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "d9wvVHoX9XCT",
        "outputId": "53c36486-76f8-4c87-8f0b-ba49717fa394"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "[3, -2, 1, -5, 2, -4]\n"
          ]
        }
      ],
      "source": [
        "class Solution:\n",
        "    def rearrangeArray(self, nums):\n",
        "        p_nums = []\n",
        "        n_nums = []\n",
        "        for i in range(len(nums)):\n",
        "            if nums[i] > 0:\n",
        "                p_nums.append(nums[i])\n",
        "            if nums[i] < 0:\n",
        "                n_nums.append(nums[i])\n",
        "        ret = []\n",
        "        for i in range(int(len(nums)/2)):\n",
        "            ret.append(p_nums[i])\n",
        "            ret.append(n_nums[i])\n",
        "        return ret\n",
        "nums = [3,1,-2,-5,2,-4]\n",
        "obj = Solution()\n",
        "print(obj.rearrangeArray(nums))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "2beDOgeFBocK"
      },
      "source": [
        "## **2150. Find All Lonely Numbers in the Array**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "wNzsrJXNBqjp"
      },
      "outputs": [],
      "source": [
        "import collections\n",
        "class Solution:\n",
        "    def findLonely(self, nums):\n",
        "        cnt = collections.Counter(nums)\n",
        "        modified = []\n",
        "        for num in cnt:\n",
        "            if cnt[num] == 1 and (num - 1) not in cnt and (num + 1) not in cnt:\n",
        "                modified.append(num)\n",
        "#         modified = modified + nums\n",
        "        \n",
        "#         zip_object = zip(list1, list2)\n",
        "#         for list1_i, list2_i in zip_object:\n",
        "#             difference.append(list1_i-list2_i)\n",
        "        return modified"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "lko4s0s9EULV",
        "outputId": "4eea2c3e-d006-42fb-9aa3-0d7e0c2b4411"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "[10, 8]\n"
          ]
        }
      ],
      "source": [
        "nums = [10,6,5,8]\n",
        "obj = Solution()\n",
        "print(obj.findLonely(nums))"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# **Weekly Contest 278**"
      ],
      "metadata": {
        "id": "2IUggtHe5Dru"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## **5993. Keep Multiplying Found Values by Two**"
      ],
      "metadata": {
        "id": "CpkoNOZd5Gwl"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "class Solution:\n",
        "    def findFinalValue(self, nums, original: int) -> int:\n",
        "        if original not in nums:\n",
        "            return original\n",
        "        nums = sorted(nums)\n",
        "        for i in range(len(nums)):\n",
        "            for j in range(i,len(nums)):\n",
        "                if nums[j] == original:\n",
        "                    original *= 2\n",
        "                    break\n",
        "        return original\n",
        "\n",
        "\n",
        "\n",
        "obj = Solution()\n",
        "nums = [5,3,6,1,12]; original = 3\n",
        "print('result:',obj.findFinalValue(nums, original))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "1Dhnp64W5Mn1",
        "outputId": "3877fe2a-057a-4b52-fba2-3d8df3059f4a"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "result: 24\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## **5981. All Divisions With the Highest Score of a Binary Array**"
      ],
      "metadata": {
        "id": "nQnpFn4s-dYe"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "class Solution:\n",
        "    def maxScoreIndices(self, nums):\n",
        "        scores = []\n",
        "        for i in range(len(nums)+1):\n",
        "            left_s = nums[0:i].count(0)\n",
        "            right_s = nums[i:].count(1)\n",
        "            scores.append(left_s + right_s)\n",
        "            # print(left_s + right_s)\n",
        "            # print(i,nums[0:i],end= '\\t')\n",
        "            # print(nums[i:])\n",
        "        # print(scores)\n",
        "        m = max(scores)\n",
        "        ret = [scores.index(m)]\n",
        "        # print(ret)\n",
        "        scores[ret[-1]] = -1000\n",
        "        while True:\n",
        "            if m in scores:\n",
        "                ret.append(scores.index(m))\n",
        "                scores[ret[-1]] = -1000\n",
        "            else:\n",
        "                return ret\n",
        "\n",
        "obj = Solution()\n",
        "nums = [0,0,1,0]\n",
        "# print(nums.count(1),nums.count(0))\n",
        "# print(obj.maxScoreIndices(nums))"
      ],
      "metadata": {
        "id": "QcpbE3S0-gy_"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "class Solution:\n",
        "    def maxScoreIndices(self, nums):\n",
        "        best = sum(nums)\n",
        "        s = best\n",
        "        res = [0]\n",
        "        for i in range(len(nums)):\n",
        "            s = s - nums[i] + (1 - nums[i])\n",
        "            if s > best:\n",
        "                best = s\n",
        "                res = [i + 1]\n",
        "            elif s == best:\n",
        "                res += [i + 1]\n",
        "        return res\n",
        "obj = Solution()\n",
        "nums = [0,0,1,0]\n",
        "print(obj.maxScoreIndices(nums))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "nd_BNmK4YiEl",
        "outputId": "639ce245-454b-4e46-c6a8-faf579d1a5f0"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[2, 4]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "class Solution(object):\n",
        "    def maxScoreIndices(self, nums):\n",
        "        \"\"\"\n",
        "        :type nums: List[int]\n",
        "        :rtype: List[int]\n",
        "        \"\"\"\n",
        "        # As following the pattern in the case 2 and 3:\n",
        "        # first of all  store sum of nums in 's'\n",
        "        # if we face '0' then we'll add '1' to the s value and append it in 'score'\n",
        "        # if we face '1' then we'll subtract '1' from s in append it to 'score'\n",
        "        # at last we'll get all the occurences of maximum number in scores and return\n",
        "        s = sum(nums)\n",
        "        score = [s]\n",
        "        for v in nums:\n",
        "            s += 1-2*v\n",
        "            score.append(s)\n",
        "        m = max(score)\n",
        "        return [i for i, v in enumerate(score) if v == m]\n",
        "obj = Solution()\n",
        "nums = [0,0,1,0]\n",
        "print(obj.maxScoreIndices(nums))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "sTHtm0ZeYi1N",
        "outputId": "d0d154b0-d417-4aa0-b2ff-a833980c240f"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[2, 4]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# **Biweekly Contest 71**"
      ],
      "metadata": {
        "id": "QGfeYvGHZTIG"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## **5984. Minimum Sum of Four Digit Number After Splitting Digits**"
      ],
      "metadata": {
        "id": "LFixJbxBZZRi"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "from itertools import permutations\n",
        "class Solution:\n",
        "    def minimumSum(self, num: int) -> int:\n",
        "        digits = list(str(num))\n",
        "        com = []\n",
        "        l = list(permutations(digits))\n",
        "        for i in range(len(l)):\n",
        "            com.append((l[i][:2],l[i][2:]))\n",
        "        val = 1000000\n",
        "        for i in range(len(com)):\n",
        "            temp = int(''.join(com[i][0][:])) + int(''.join(com[i][1][:]))\n",
        "            val = min(val,temp)\n",
        "        return val\n",
        "obj = Solution()\n",
        "print(obj.minimumSum(4009))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "9qnrlfs_ZdbI",
        "outputId": "8bd7e128-437f-47b3-e98e-bafbb3ccccff"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "13\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "class Solution:\n",
        "    def minimumSum(self, num: int) -> int:\n",
        "        buf = sorted(str(num))\n",
        "        vals = [\"\", \"\"]\n",
        "        for i in range(len(buf)):\n",
        "            vals[i % 2] += buf[i]\n",
        "        return sum(map(int, vals))\n",
        "obj = Solution()\n",
        "print(obj.minimumSum(4009))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "tAORE7MmuOJw",
        "outputId": "202bd366-cb35-4dda-9f4d-30ebe1fed410"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "13\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## **5985. Partition Array According to Given Pivot**"
      ],
      "metadata": {
        "id": "k024wKAukPmS"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "class Solution:\n",
        "    def pivotArray(self, nums, pivot: int):\n",
        "        smaller = []\n",
        "        equals = []\n",
        "        greater = []\n",
        "        for i in range(len(nums)):\n",
        "            if nums[i] < pivot:\n",
        "                smaller.append(nums[i])\n",
        "            elif nums[i] > pivot:\n",
        "                greater.append(nums[i])\n",
        "            else:\n",
        "                equals.append(nums[i])\n",
        "        return smaller + equals + greater\n",
        "obj = Solution()\n",
        "print(obj.pivotArray(nums = [9,12,5,10,14,3,10], pivot = 10))"
      ],
      "metadata": {
        "id": "C1yT1lnIkO6L"
      },
      "execution_count": null,
      "outputs": []
    }
  ],
  "metadata": {
    "colab": {
      "collapsed_sections": [
        "7BwRRpCdxyrC",
        "9zWvDp7H12j2"
      ],
      "name": "LeetCode Problems-1.ipynb",
      "provenance": [],
      "authorship_tag": "ABX9TyMw1/Ub94r/K7OtJJRkx/Fm",
      "include_colab_link": true
    },
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}