30DaysChallengeLeetCode1_18.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "30DaysChallengeLeetCode1_18.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "authorship_tag": "ABX9TyP8WBfn6cFLFEmjwdN89bPK",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/anhhaibkhn/LeetCode_Daily_Challenges/blob/master/30DaysChallengeLeetCode1_18.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "XjZWH94JrFBc",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "import numpy as np"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8Z3TOBJgrJZj",
        "colab_type": "code",
        "outputId": "09224b69-8e03-4eaf-89cd-c8ccd48cc5f3",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 68
        }
      },
      "source": [
        "Arr = np.random.randn(3,5) \n",
        "print(Arr)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[[-1.13513437  1.62429862  0.76270637 -0.97553635 -1.0010499 ]\n",
            " [-0.29434556 -0.65266952 -0.65442675  0.37543419 -0.80592201]\n",
            " [ 1.68140604  0.8161118  -0.62979583 -0.09935531 -1.88754474]]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "UIH-CfpWrUDv",
        "colab_type": "code",
        "outputId": "825ace28-ed51-419e-d2a1-dcc2545c6cd9",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 102
        }
      },
      "source": [
        "from typing import List\n",
        "class Solution:\n",
        "    def moveZeroes(self, nums: List[int]) -> None:\n",
        "        \"\"\"\n",
        "        Do not return anything, modify nums in-place instead.\n",
        "        \n",
        "        \"\"\"\n",
        "        print(nums)\n",
        "        for index, k in enumerate(nums):\n",
        "          if(k == 0):\n",
        "            print(index)\n",
        "            nums.append(nums.pop(index)) \n",
        "            print(nums)\n",
        "        \n",
        "\n",
        "Arrr = [0,1,0,3,12]\n",
        "arr2 = [0,0,1]\n",
        "test = Solution()\n",
        "test.moveZeroes(arr2)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[0, 0, 1]\n",
            "0\n",
            "[0, 1, 0]\n",
            "2\n",
            "[0, 1, 0]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "0tbzKwIKuLei",
        "colab_type": "code",
        "outputId": "bed8d4cb-9f48-45e6-ae50-efd6a6e6bea8",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 153
        }
      },
      "source": [
        "# test_list = [3, 5, 3, 9, 11]\n",
        "test_list = [0,0,1]\n",
        " # printing original list  \n",
        "print (\"The original list is : \" + str(test_list)) \n",
        "# https://www.geeksforgeeks.org/python-move-element-to-end-of-the-list/\n",
        "test_list.sort(key = 0 .__eq__) \n",
        "\n",
        "# printing result \n",
        "print (\"The modified element moved list is : \" + str(test_list)) "
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "The original list is : [0, 0, 1]\n",
            "0\n",
            "[1, 0, 0]\n",
            "1\n",
            "[1, 0, 0]\n",
            "2\n",
            "[1, 0, 0]\n",
            "The modified element moved list is : [1, 0, 0]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ERlt40gsuWCG",
        "colab_type": "code",
        "outputId": "d11bdcc5-c447-48f8-ea50-3fc0a3fa9717",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "#Day 6. Anagram\n",
        "from typing import List\n",
        "class Solution:\n",
        "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
        "      groupAna = []\n",
        "      Un_unique = []\n",
        "\n",
        "      for word in strs:\n",
        "        A = sorted(word)\n",
        "        # print(A)\n",
        "        if A not in groupAna:\n",
        "          groupAna.append(A)\n",
        "          Un_unique.append([])\n",
        "        for k in range(0, len(groupAna)):\n",
        "          if A == groupAna[k]:\n",
        "            Un_unique[k].append(word)\n",
        "\n",
        "      return Un_unique\n",
        "            \n",
        "\n",
        "\n",
        "Input = [\"eat\", \"tea\", \"tan\", \"ate\", \"nat\", \"bat\"]\n",
        "Check = Solution()\n",
        "\n",
        "Check.groupAnagrams(Input)\n",
        "\n"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 33
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "eXLpS-cZhK0Q",
        "colab_type": "code",
        "outputId": "a8525f30-8668-45a5-94db-8f17ec70cffd",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 153
        }
      },
      "source": [
        "''' Fastest Approach:\n",
        "1. sort the values in the list.\n",
        "2. Dictionary:sorted words will be the key and the words matching these will be values in a  list\n",
        "3. if the  sorted word is not present in the dictionary, add the sorted word to the dictionary with the corresponding word as the value.\n",
        "4. else append  the  word  to the existing  list\n",
        "'''\n",
        "from typing import List\n",
        "class Solution:\n",
        "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
        "\n",
        "        dic = { }\n",
        "        for words in strs:\n",
        "            sorted_word  = \"\".join(sorted(words))\n",
        "            print(sorted_word)\n",
        "            \n",
        "            if sorted_word not in dic:\n",
        "                dic[sorted_word]= [words]\n",
        "            else:\n",
        "                dic[sorted_word].append(words)\n",
        "        print(dic)              \n",
        "        return dic.values()\n",
        "\n",
        "Input = [\"eat\", \"tea\", \"tan\", \"ate\", \"nat\", \"bat\"]\n",
        "Check = Solution()\n",
        "\n",
        "print(Check.groupAnagrams(Input))\n"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "aet\n",
            "aet\n",
            "ant\n",
            "aet\n",
            "ant\n",
            "abt\n",
            "{'aet': ['eat', 'tea', 'ate'], 'ant': ['tan', 'nat'], 'abt': ['bat']}\n",
            "dict_values([['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']])\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "CoGOvXcWpT0p",
        "colab_type": "code",
        "outputId": "aa09d636-af3a-4c99-8ba6-2d96597e6fec",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "class Recursion:\n",
        "    def reverseString(self, s: List[str]) -> None:\n",
        "        \"\"\"\n",
        "        Do not return anything, modify s in-place instead.\n",
        "        \"\"\"\n",
        "        left, right = 0, len(s) - 1\n",
        "        while left < right:\n",
        "            s[left], s[right] = s[right], s[left]\n",
        "            left, right = left + 1, right - 1\n",
        "\n",
        "Input = [\"h\",\"e\",\"l\",\"l\",\"o\"]\n",
        "# Input: [\"h\",\"e\",\"l\",\"l\",\"o\"]\n",
        "# Output: [\"o\",\"l\",\"l\",\"e\",\"h\"]\n",
        "Input2 = [\"H\",\"a\",\"n\",\"n\",\"a\",\"h\"]\n",
        "# Input: [\"H\",\"a\",\"n\",\"n\",\"a\",\"h\"]\n",
        "# Output: [\"h\",\"a\",\"n\",\"n\",\"a\",\"H\"]\n",
        "\n",
        "testA = Recursion()\n",
        "testA.reverseString(Input2)\n",
        "Input2\n"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "['h', 'a', 'n', 'n', 'a', 'H']"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 37
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "aogJDeqG0OxT",
        "colab_type": "code",
        "outputId": "688275cf-b445-49e6-9739-4f412a8f3ebd",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 119
        }
      },
      "source": [
        "# Day 8: Singly Linked list examle\n",
        "class Node: \n",
        "  def __init__(self, data, next = None):\n",
        "    self.data = data\n",
        "    self.next = next\n",
        "\n",
        "node1 = Node(12)\n",
        "node2 = Node(4, node1)\n",
        "node3 = Node(6, node2)\n",
        "\n",
        "print(node3.data)\n",
        "print(node3.next.data)\n",
        "print(node3.next.next.data)\n",
        "\n",
        "cur = node3\n",
        "while cur != None:\n",
        "  print(cur.data)\n",
        "  cur = cur.next\n"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "6\n",
            "4\n",
            "12\n",
            "6\n",
            "4\n",
            "12\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "4EF5u7wmJ4M-",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Circular Linked list\n",
        "class Node: \n",
        "  def __init__(self, data, next = None):\n",
        "    self.data = data\n",
        "    self.next = next\n",
        "\n",
        "node1 = Node(12)\n",
        "node2 = Node(4, node1)\n",
        "node3 = Node(6, node2)\n",
        "node1.next = node3 # This is for circular linked list \n",
        "\n",
        "print(node3.data)\n",
        "print(node3.next.data)\n",
        "print(node3.next.next.data)\n",
        "\n",
        "cur = node3\n",
        "while cur != None:\n",
        "  print(cur.data)\n",
        "  cur = cur.next\n",
        "\n",
        "\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gVFVMRsHKgeg",
        "colab_type": "code",
        "outputId": "a2a6e85c-904c-4d22-89aa-0e7c1d274630",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 68
        }
      },
      "source": [
        "# Doubly linked list\n",
        "class Node: \n",
        "  def __init__(self, data, next = None):\n",
        "      self.data = data\n",
        "      self.next = next\n",
        "      self.pre = None\n",
        "\n",
        "node1 = Node(12)\n",
        "node2 = Node(4, node1)\n",
        "node1.pre = node2\n",
        "node3 = Node(6,node2)\n",
        "node2.pre = node3\n",
        "\n",
        "cur = node3\n",
        "while cur != None:\n",
        "  print(cur.data)\n",
        "  cur = cur.next"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "6\n",
            "4\n",
            "12\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "EwCrcJIpOJs4",
        "colab_type": "code",
        "outputId": "4098eb15-e918-458a-b7e3-cafed5fdc008",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 85
        }
      },
      "source": [
        "# LInked list Class FULL\n",
        "class Node:\n",
        "    # constructor\n",
        "    def __init__(self, data, next=None):\n",
        "        self.data = data\n",
        "        self.next = next\n",
        "    # for printing out object data \n",
        "    def __repr__(self):\n",
        "        return str(self.data)\n",
        "\n",
        "# Singly Linked list\n",
        "class LinkedList:\n",
        "\n",
        "    def __init__(self, data):\n",
        "        first = Node(data)\n",
        "        self.head = first\n",
        "        self.tail = first\n",
        "\n",
        "    def add_node(self, data):\n",
        "        self.new = Node(data)\n",
        "        self.tail.next = self.new\n",
        "        self.tail = self.new\n",
        "\n",
        "    def pop(self):\n",
        "        cur = self.head\n",
        "        while cur.next != self.tail:\n",
        "            cur = cur.next\n",
        "        data = cur.next.data\n",
        "        cur.next = None\n",
        "        return data\n",
        "\n",
        "    def remove(self, pos):\n",
        "        # Can update\n",
        "        cur = self.head\n",
        "        count = 0\n",
        "        while cur != None and count < pos - 1:\n",
        "            count += 1\n",
        "            cur = cur.next\n",
        "        cur.next = cur.next.next # cur.next = None \n",
        "\n",
        "ll = LinkedList(12)\n",
        "ll.add_node(3)\n",
        "ll.add_node(45)\n",
        "ll.add_node(5)\n",
        "# 12 -> 3 -> 5\n",
        "print(ll.remove(0))\n",
        "\n",
        "cur = ll.head\n",
        "while cur != None:\n",
        "    print(cur.data)\n",
        "    cur = cur.next\n",
        "\n"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "None\n",
            "12\n",
            "45\n",
            "5\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Sy1dmmTWXw1F",
        "colab_type": "code",
        "outputId": "1149001e-dab3-40c1-b892-52c2deea754c",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "# Day 8\n",
        "# Definition for singly-linked list.\n",
        "# class ListNode:\n",
        "#     def __init__(self, x):\n",
        "#         self.val = x\n",
        "#         self.next = None\n",
        "\n",
        "class Solution:\n",
        "    def middleNode(self, head: ListNode) -> ListNode:\n",
        "        count = 0\n",
        "        check =  cur = head\n",
        "        while cur != None:\n",
        "              count += 1\n",
        "              cur = cur.next\n",
        "        index = 0\n",
        "        while check != None and index < (count//2):\n",
        "            index += 1\n",
        "            check = check.next\n",
        "          \n",
        "        return check\n",
        "\"\"\"Runtime: 20 ms\n",
        "Memory Usage: 13.7 MB\"\"\"\n",
        "\n",
        "# CACH 2\n",
        "  def middleNode2(self, head: ListNode) -> ListNode:\n",
        "      count = 0\n",
        "      mid = head\n",
        "      while head != None:\n",
        "          count += 1\n",
        "          if count % 2 == 0:\n",
        "              mid = mid.next\n",
        "          head = head.next\n",
        "      return mid\n",
        "\"\"\"Runtime: 20 ms\n",
        "Memory Usage: 13.9 MB\"\"\""
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "0\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "-2FTSmBtJEDz",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# day 9. Accepted answer, AddtwoNumber.\n",
        "\n",
        "# Definition for singly-linked list.\n",
        "class ListNode:\n",
        "    def __init__(self, x):\n",
        "        self.val = x\n",
        "        self.next = None\n",
        "\n",
        "class Solution:\n",
        "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
        "        result = ListNode(0)\n",
        "        temp = result \n",
        "        carry = 0 \n",
        "        while l1 != None or l2 != None:\n",
        "            l1_val = l1.val if l1 else 0\n",
        "            l2_val = l2.val if l2 else 0\n",
        "            total = l1_val + l2_val + carry\n",
        "            carry = 1 if total >= 10 else 0\n",
        "            total = total if total < 10 else total % 10\n",
        "            \n",
        "            temp.next = ListNode(total)\n",
        "            temp = temp.next\n",
        "                         \n",
        "            l1 = l1.next if l1 else None\n",
        "            l2 = l2.next if l2 else None\n",
        "            \n",
        "        if carry == 0:\n",
        "            return result.next\n",
        "        else:\n",
        "            temp.next = ListNode(carry)\n",
        "            return result.next\n",
        "\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DzXuoepHJqXE",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Cysec IP map \n",
        "\n",
        "Nmap scan report for 192.168.100.2\n",
        "Host is up (0.00027s latency).\n",
        "MAC Address: 90:1B:0E:6C:86:D8 (Fujitsu Technology Solutions GmbH)\n",
        "\n",
        "Nmap scan report for 192.168.100.24\n",
        "Host is up (0.00072s latency).\n",
        "MAC Address: 4C:52:62:14:3C:6B (Fujitsu Technology Solutions GmbH)\n",
        "\n",
        "Nmap scan report for 192.168.100.25\n",
        "Host is up (0.00043s latency).\n",
        "MAC Address: 4C:52:62:43:0F:EF (Fujitsu Technology Solutions GmbH)\n",
        "\n",
        "#Hoang \n",
        "Nmap scan report for 192.168.100.29\n",
        "Host is up (0.00012s latency).\n",
        "MAC Address: 4C:52:62:43:10:74 (Fujitsu Technology Solutions GmbH)\n",
        "\n",
        "Nmap scan report for 192.168.100.31\n",
        "Host is up (0.00028s latency).\n",
        "MAC Address: 90:1B:0E:10:74:AE (Fujitsu Technology Solutions GmbH)\n",
        "\n",
        "Nmap scan report for 192.168.100.45\n",
        "Host is up (0.00052s latency).\n",
        "MAC Address: 4C:52:62:43:0E:75 (Fujitsu Technology Solutions GmbH)\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8BPJaO04YpAp",
        "colab_type": "code",
        "outputId": "1122c17a-a0d2-42cf-c316-91c48f3c5e13",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "# Day 9 Origional \n",
        "class Solution:\n",
        "    def backspaceCompare(self, S: str, T: str) -> bool:\n",
        "      while S.find('#') != -1:\n",
        "        S = S.split('#',1) \n",
        "        S[0] = S[0][:-1]\n",
        "        S = \"\".join(S)\n",
        "\n",
        "      while T.find('#') != -1:\n",
        "        T = T.split('#',1) \n",
        "        T[0] = T[0][:-1]\n",
        "        T = \"\".join(T)\n",
        "    \n",
        "      return S == T\n",
        "\n",
        "\n",
        "        \n",
        "S = \"ab##cc#c\"\n",
        "T = \"ad#c\"\n",
        "day9 = Solution()\n",
        "print(day9.backspaceCompare(S,T))\n"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "False\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "fH8j7Qo1FE2V",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Day 9 Origional Updated 36ms\n",
        "class Solution:\n",
        "    def backspaceCompare(self, S: str, T: str) -> bool:  \n",
        "      return self.backspaceCheck(S) == self.backspaceCheck(T)\n",
        "\n",
        "    def backspaceCheck(self, InStr: str) -> str:\n",
        "        while InStr.find('#') != -1:\n",
        "          InStr = InStr.split('#',1) \n",
        "          InStr[0] = InStr[0][:-1]\n",
        "          InStr = \"\".join(InStr)\n",
        "        return InStr\n",
        "        \n",
        "S = \"ab##cc#c\"\n",
        "T = \"ad#c\"\n",
        "day9 = Solution()\n",
        "print(day9.backspaceCompare(S,T))"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8x2fPOzbB7H7",
        "colab_type": "code",
        "outputId": "04dda187-f4b4-4227-b912-46957418d8a1",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 102
        }
      },
      "source": [
        "# 16 ms Ver\n",
        "import collections\n",
        "class Solution2:\n",
        "    def backspaceCompare(self, S: str, T: str) -> bool:\n",
        "        return self.editorProcessor(S) == self.editorProcessor(T)\n",
        "    def editorProcessor(self, string: str) -> str:\n",
        "        res = collections.deque() # Deque can append, left, right, pop left, right\n",
        "        l = 0\n",
        "        for i in string:\n",
        "            if i == \"#\":\n",
        "                if  l > 0: \n",
        "                    res.pop()\n",
        "                    l -= 1\n",
        "            else:\n",
        "                res.append(i)\n",
        "                l += 1\n",
        "        print(res)        # deque(['c', 'c'])\n",
        "        print(list(res))  # ['c', 'c']\n",
        "        return ''.join(list(res)) # 'cc'\n",
        "\n",
        "\n",
        "S = \"ab##cc#c\"\n",
        "T = \"ad#c\"\n",
        "day9 = Solution2()\n",
        "print(day9.backspaceCompare(S,T))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "deque(['c', 'c'])\n",
            "['c', 'c']\n",
            "deque(['a', 'c'])\n",
            "['a', 'c']\n",
            "False\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "apW-vFgdF3aZ",
        "colab_type": "code",
        "outputId": "dbf18b60-63eb-436f-8ab9-77de04132564",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "# 12 ms Ver\n",
        "class SolutionFastest:\n",
        "    def backspaceCompare(self, S: str, T: str) -> bool:\n",
        "        \n",
        "        def finalStr(s: str):\n",
        "            stack = []\n",
        "            for char in s:\n",
        "                if stack and char == '#':\n",
        "                    stack.pop()\n",
        "                elif char != '#':\n",
        "                    stack.append(char)\n",
        "            return stack\n",
        "\n",
        "        return finalStr(S) == finalStr(T)\n",
        "\n",
        "S = \"ab##cc#c\"\n",
        "T = \"ad#c\"\n",
        "day9 = SolutionFastest()\n",
        "print(day9.backspaceCompare(S,T))\n",
        "                                       \n",
        "                "
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "False\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "sJifYA7HGpTe",
        "colab_type": "code",
        "outputId": "6c99a154-7280-4e1e-d1ce-7c50cce76935",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 238
        }
      },
      "source": [
        "class SolutionFinal:\n",
        "    def backspaceCompare(self, S: str, T: str) -> bool:\n",
        "        def final( InStr: str) -> str:\n",
        "            StrArr = []\n",
        "            find = 0\n",
        "            for char in InStr:\n",
        "                if StrArr and char == '#':\n",
        "                    StrArr.pop()\n",
        "                elif char != '#':\n",
        "                    StrArr.append(char)\n",
        "                print(StrArr)\n",
        "            print(StrArr)\n",
        "            return StrArr\n",
        "        return final(S) == final(T)\n",
        "\n",
        "S = \"##cc#c\"\n",
        "T = \"a#cc\"\n",
        "day9 = SolutionFinal()\n",
        "print(day9.backspaceCompare(S,T))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[]\n",
            "[]\n",
            "['c']\n",
            "['c', 'c']\n",
            "['c']\n",
            "['c', 'c']\n",
            "['c', 'c']\n",
            "['a']\n",
            "[]\n",
            "['c']\n",
            "['c', 'c']\n",
            "['c', 'c']\n",
            "True\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kb1VC6dsMoML",
        "colab_type": "code",
        "outputId": "753aae93-6487-43c1-8429-8e5351f38dcf",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 102
        }
      },
      "source": [
        "# Day 9. Min Stack\n",
        "class MinStack:\n",
        "    def __init__(self):\n",
        "      self.Arr = []\n",
        "\n",
        "    def __repr__(self):\n",
        "      return str(self.Arr)\n",
        "        \n",
        "    def push(self, x: int) -> None:\n",
        "      self.Arr.append(x)\n",
        "      \n",
        "    def pop(self) -> None:\n",
        "      del self.Arr[-1]\n",
        "        \n",
        "    def top(self) -> int:\n",
        "      return self.Arr[-1]\n",
        "   \n",
        "\n",
        "    def getMin(self) -> int:\n",
        "      return min(self.Arr)\n",
        "        \n",
        "\n",
        "\n",
        "# Your MinStack object will be instantiated and called as such:\n",
        "# obj = MinStack()\n",
        "# obj.push(x)\n",
        "# obj.pop()\n",
        "# param_3 = obj.top()\n",
        "# param_4 = obj.getMin()\n",
        "# MinStack minStack = new MinStack()\n",
        "\n",
        "minStack = MinStack()\n",
        "minStack.push(-2)\n",
        "minStack.push(0)\n",
        "minStack.push(-3)\n",
        "\n",
        "print(minStack)\n",
        "\n",
        "print(minStack.getMin())  # --> Returns -3.\n",
        "print(minStack.pop())\n",
        "print(minStack.top() )   # --> Returns 0.\n",
        "print(minStack.getMin() ) # --> Returns -2."
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[-2, 0, -3]\n",
            "-3\n",
            "None\n",
            "0\n",
            "-2\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "6_t81O1P_rQE",
        "colab_type": "code",
        "outputId": "efb18448-5eed-4c53-cdd2-dd1dc956064e",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 102
        }
      },
      "source": [
        "# Day 9: Other answers 1 \n",
        "class MinStack:\n",
        "    def __init__(self):\n",
        "        \"\"\"\n",
        "        initialize your data structure here.\n",
        "        \"\"\"\n",
        "        self.stack = []\n",
        "        self.min = []\n",
        "    def __repr__(self):\n",
        "      return str(self.stack)\n",
        "         \n",
        "\n",
        "    def push(self, x: int) -> None:\n",
        "        self.stack.append(x)\n",
        "        if len(self.min) == 0:\n",
        "            self.min.append(x)\n",
        "        elif self.min[-1] >= x:\n",
        "            self.min.append(x)\n",
        "        \n",
        "    def pop(self) -> None:\n",
        "        val = self.stack.pop()\n",
        "        if val == self.min[-1]:\n",
        "            self.min.pop()\n",
        "        # return val\n",
        "    def top(self) -> int:\n",
        "        return self.stack[-1]\n",
        "        \n",
        "\n",
        "    def getMin(self) -> int:\n",
        "        return self.min[-1]\n",
        "\n",
        "minStack = MinStack()\n",
        "minStack.push(-2)\n",
        "minStack.push(0)\n",
        "minStack.push(-3)\n",
        "\n",
        "print(minStack)\n",
        "\n",
        "print(minStack.getMin())  # --> Returns -3.\n",
        "print(minStack.pop())\n",
        "print(minStack.top() )   # --> Returns 0.\n",
        "print(minStack.getMin() ) # --> Returns -2.\n"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[-2, 0, -3]\n",
            "-3\n",
            "None\n",
            "0\n",
            "-2\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "46ia30NOFsrE",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Day 9: Other answers 2 (40ms)\n",
        "class MinStack:\n",
        "\n",
        "    def __init__(self):\n",
        "        \"\"\"\n",
        "        initialize your data structure here.\n",
        "        \"\"\"\n",
        "        self.array=[]\n",
        "        self.stack=[]\n",
        "        \n",
        "\n",
        "    def push(self, x: int) -> None:\n",
        "        self.array.append(x)\n",
        "        if len(self.stack)==0 or x<=self.stack[-1]:\n",
        "            self.stack.append(x)\n",
        "        \n",
        "\n",
        "    def pop(self) -> None:\n",
        "        val=self.array.pop()\n",
        "        if val==self.stack[-1]:\n",
        "            self.stack.pop()\n",
        "        \n",
        "\n",
        "    def top(self) -> int:\n",
        "        return self.array[-1]\n",
        "        \n",
        "\n",
        "    def getMin(self) -> int:\n",
        "        return self.stack[-1]\n",
        "\n",
        "\n",
        "# Other 3. 45 ms\n",
        "class MinStack:\n",
        "\n",
        "    def __init__(self):\n",
        "        \"\"\"\n",
        "        initialize your data structure here.\n",
        "        \"\"\"\n",
        "        self.stack = []\n",
        "\n",
        "    def push(self, x: int) -> None:\n",
        "        if len(self.stack)==0:\n",
        "            self.stack.append((x,x))\n",
        "        else:\n",
        "            self.stack.append((x, min(x, self.stack[-1][1])))\n",
        "\n",
        "    def pop(self) -> None:\n",
        "        if len(self.stack):\n",
        "            x, _ = self.stack.pop()\n",
        "            return x\n",
        "        \n",
        "    def top(self) -> int:\n",
        "        if self.stack:\n",
        "            x, _ = self.stack[-1]\n",
        "            return x\n",
        "        \n",
        "    def getMin(self) -> int:\n",
        "        if self.stack:\n",
        "            _, m = self.stack[-1]\n",
        "            return m\n",
        "        \n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "UqTAXUHg71UE",
        "colab_type": "code",
        "outputId": "2fbe96c6-daaa-49e4-f88e-8cecc9b91d85",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "#Day 11: Definition for a binary tree node.\n",
        "class TreeNode:\n",
        "    def __init__(self, x):\n",
        "        self.val = x\n",
        "        self.left = None\n",
        "        self.right = None\n",
        "\n",
        "\n",
        "root = TreeNode(1) \n",
        "# root.left = TreeNode(2) \n",
        "# root.right = TreeNode(3) \n",
        "# root.left.left = TreeNode(4) \n",
        "# root.left.right = TreeNode(5)\n",
        "\n",
        "class Solution:\n",
        "    def height(self, node: TreeNode):\n",
        "      if node is None:\n",
        "        return 0\n",
        "      return 1 + max(self.height(node.left), self.height(node.right))\n",
        "\n",
        "    def diameterOfBinaryTree(self, root: TreeNode) -> int:\n",
        "      if root is None:\n",
        "        return 0\n",
        "      # find tree height \n",
        "      l_height = self.height(root.left)\n",
        "      r_height = self.height(root.right)\n",
        "      # find left and right diamter\n",
        "      l_diameter = self.diameterOfBinaryTree(root.left)\n",
        "      r_diameter = self.diameterOfBinaryTree(root.right)\n",
        "\n",
        "      return max(l_height + r_height, max(l_diameter,r_diameter))\n",
        "\n",
        "\n",
        "Test = Solution()\n",
        "print(Test.diameterOfBinaryTree(root))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "0\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "nezCtsxN8dPT",
        "colab_type": "code",
        "outputId": "ad8e7f8c-38f2-41c8-c79b-09fb89d196f2",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "# Python program to find the diameter of binary tree \n",
        "\n",
        "# A binary tree node \n",
        "class Node: \n",
        "\n",
        "\t# Constructor to create a new node \n",
        "\tdef __init__(self, data): \n",
        "\t\tself.data = data \n",
        "\t\tself.left = None\n",
        "\t\tself.right = None\n",
        "\n",
        "\n",
        "\"\"\" \n",
        "The function Compute the \"height\" of a tree. Height is the \n",
        "number f nodes along the longest path from the root node \n",
        "down to the farthest leaf node. \n",
        "\"\"\"\n",
        "def height(node): \n",
        "\t\n",
        "\t# Base Case : Tree is empty \n",
        "\tif node is None: \n",
        "\t\treturn 0 ; \n",
        "\t\n",
        "\t# If tree is not empty then height = 1 + max of left \n",
        "\t# height and right heights \n",
        "\treturn 1 + max(height(node.left) ,height(node.right)) \n",
        "\n",
        "# Function to get the diamtere of a binary tree \n",
        "def diameter(root): \n",
        "\t\n",
        "\t# Base Case when tree is empty \n",
        "\tif root is None: \n",
        "\t\treturn 0; \n",
        "\n",
        "\t# Get the height of left and right sub-trees \n",
        "\tlheight = height(root.left) \n",
        "\trheight = height(root.right) \n",
        "\n",
        "\t# Get the diameter of left and irgh sub-trees \n",
        "\tldiameter = diameter(root.left) \n",
        "\trdiameter = diameter(root.right) \n",
        "\n",
        "\t# Return max of the following tree: \n",
        "\t# 1) Diameter of left subtree \n",
        "\t# 2) Diameter of right subtree \n",
        "\t# 3) Height of left subtree + height of right subtree +1 \n",
        "\treturn max(lheight + rheight + 1, max(ldiameter, rdiameter)) \n",
        "\t\n",
        "\n",
        "# Driver program to test above functions \n",
        "\n",
        "\"\"\" \n",
        "Constructed binary tree is \n",
        "\t\t\t1 \n",
        "\t\t/ \\ \n",
        "\t\t2\t 3 \n",
        "\t/ \\ \n",
        "\t4\t 5 \n",
        "\"\"\"\n",
        "\n",
        "root = Node(1) \n",
        "root.left = Node(2) \n",
        "root.right = Node(3) \n",
        "root.left.left = Node(4) \n",
        "root.left.right = Node(5) \n",
        "print(\"Diameter of given binary tree is %d\" %(diameter(root)))\n",
        "\n",
        "# This code is contributed by Nikhil Kumar Singh(nickzuck_007) \n",
        "\n"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Diameter of given binary tree is 4\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "nvowGfaIP8dH",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# 24ms sample\n",
        "\n",
        "# Definition for a binary tree node.\n",
        "# class TreeNode:\n",
        "#     def __init__(self, x):\n",
        "#         self.val = x\n",
        "#         self.left = None\n",
        "#         self.right = None\n",
        "\n",
        "class Solution:\n",
        "    def diameterOfBinaryTree(self, root: TreeNode) -> int:\n",
        "\n",
        "        self.number_of_nodes = 1\n",
        "        def depth(node):\n",
        "            if not node: return 0\n",
        "            L = depth(node.left)\n",
        "            R = depth(node.right)\n",
        "            # path\n",
        "            self.number_of_nodes = max(self.number_of_nodes, L+R+1)\n",
        "            return max(L, R) + 1 # find depth\n",
        "\n",
        "        depth(root)\n",
        "        return self.number_of_nodes - 1\n",
        "\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "04fCx3Z4U3l2",
        "colab_type": "code",
        "outputId": "83b0361a-5e31-44fb-92b3-1e9dc645dd21",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "# Geek examples \n",
        "# Definition for a binary tree node.\n",
        "class TreeNode:\n",
        "    def __init__(self, x):\n",
        "        self.val = x\n",
        "        self.left = None\n",
        "        self.right = None\n",
        "\n",
        "class Solution:\n",
        "    def height(self, root, ans): \n",
        "        if (root == None): \n",
        "            return 0\n",
        "\n",
        "        left_height = self.height(root.left, ans)  \n",
        "\n",
        "        right_height = self.height(root.right, ans)  \n",
        "\n",
        "        # update the answer, because diameter  \n",
        "        # of a tree is nothing but maximum  \n",
        "        # value of (left_height + right_height + 1) \n",
        "        # for each node  \n",
        "        ans[0] = max(ans[0], 1 + left_height + \n",
        "                                 right_height)  \n",
        "\n",
        "        return 1 + max(left_height, \n",
        "                       right_height) \n",
        "\n",
        "    # Computes the diameter of binary  \n",
        "    # tree with given root.  \n",
        "    def diameterOfBinaryTree(self, root: TreeNode) -> int:\n",
        "        if (root == None):  \n",
        "            return 0\n",
        "        ans = [0] # This will store \n",
        "                              # the final answer  \n",
        "        height_of_tree = self.height(root, ans)  \n",
        "        return ans[0] - 1\n",
        "\n",
        "\n",
        "root = Node(1) \n",
        "root.left = Node(2) \n",
        "root.right = Node(3) \n",
        "root.left.left = Node(4) \n",
        "root.left.right = Node(5) \n",
        "A = Solution()\n",
        "print(\"Diameter of given binary tree is %d\" %(A.diameterOfBinaryTree(root)))\n"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Diameter of given binary tree is 3\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "hRQf8VSsVP6x",
        "colab_type": "code",
        "outputId": "96e10431-d6db-46dc-b14a-60b2d950dac9",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "# Day 12. 24 ms . Last Stone Weight \n",
        "from typing import List\n",
        "numbers = [1]\n",
        "class Solution:\n",
        "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
        "        while len(stones) > 1:\n",
        "            stones.sort()\n",
        "            stoneA = stones.pop(-1)\n",
        "            stoneB = stones.pop(-1)\n",
        "            if stoneA != stoneB:\n",
        "                stones.append(abs(stoneA - stoneB))\n",
        "\n",
        "        if not stones:\n",
        "            return 0\n",
        "        return stones[0]\n",
        "\n",
        "test = Solution()\n",
        "print(test.lastStoneWeight(numbers))\n"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "1\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "YKhRQt9BXkE3",
        "colab_type": "code",
        "outputId": "7e2411ab-7a27-4df4-9ee5-532b1f92135a",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "\n",
        "print(abs(0 - 2))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "2\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "CCS0aIkhtekD",
        "colab_type": "code",
        "outputId": "e93cf0b1-3d53-4701-f945-1b9863d4b2c4",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 51
        }
      },
      "source": [
        "# 12ms answer. \n",
        "class Solution:\n",
        "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
        "        stones.sort(reverse=True)\n",
        "        print(stones)\n",
        "        while len(stones) > 1:\n",
        "            arr = stones[2:]\n",
        "            y = stones[0]\n",
        "            x = stones[1]\n",
        "            if x != y:\n",
        "                arr.append(y-x)\n",
        "            stones = sorted(arr,reverse=True)\n",
        "        if stones:\n",
        "            return stones[0]\n",
        "        return 0\n",
        "\n",
        "numbers = [2,7,4,1,8,1]\n",
        "test = Solution()\n",
        "print(test.lastStoneWeight(numbers))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[8, 7, 4, 2, 1, 1]\n",
            "1\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Fi6IPDhvwtFY",
        "colab_type": "code",
        "outputId": "d0caf597-92a1-481f-fbd6-10471dc371a5",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "# Day 12: Binary Contiguous Array \n",
        "\n",
        "# InputArr = [1,1,1,0,0,0,1]\n",
        "# InputArr =[1,1,1,1,1,1]\n",
        "from typing import List\n",
        "class Solution:\n",
        "    def findMaxLength(self, nums: List[int]) -> int:\n",
        "      One = nums.count(1)\n",
        "      Zero = len(nums) - One\n",
        "      if One == 0 or Zero == 0:\n",
        "        return 0\n",
        "      if One == Zero:\n",
        "        return 2 * One\n",
        "      elif One < Zero:\n",
        "        size = 2 * One\n",
        "      else:\n",
        "        size = 2 * Zero \n",
        "\n",
        "      for window in range(size,1,-1):\n",
        "        ListArr = self.subArr(window,nums)\n",
        "        print(ListArr)\n",
        "        for arr in ListArr:\n",
        "          Count = arr.count(1)\n",
        "          print(Count)\n",
        "          if  Count == (window - Count):\n",
        "            print(arr)\n",
        "            return window\n",
        "        \n",
        "    def subArr(self,n, x):\n",
        "      if len(x) < n:\n",
        "        return []\n",
        "\n",
        "      return [x[:n]] + self.subArr(n, x[1:])\n",
        "      \n",
        "\n",
        "test = Solution()\n",
        "print(test.findMaxLength(InputArr))\n"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "0\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "OHX_Z7oGn-66",
        "colab_type": "code",
        "outputId": "6b695c57-c23f-4ce0-8ad6-f2716fc2100e",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 51
        }
      },
      "source": [
        "# Solution Day 12. Fk\n",
        "\n",
        "from typing import List\n",
        "class Solution:\n",
        "    def findMaxLength(self, nums: List[int]) -> int:\n",
        "      # NOTE: Dictonary in python in  \n",
        "      # implemented as Hash Maps.  \n",
        "      # Create an empty hash map (dictionary)  \n",
        "      hash_map = {}   \n",
        "      curr_sum = 0 \n",
        "      max_len = 0 \n",
        "      ending_index = -1 \n",
        "      n = len(nums)\n",
        "      for i in range (0, n):  \n",
        "          if(nums[i] == 0):  \n",
        "              nums[i] = -1 \n",
        "          else:  \n",
        "              nums[i] = 1 \n",
        "    \n",
        "      # Traverse through the given array  \n",
        "      for i in range (0, n):  \n",
        "        \n",
        "          # Add current element to sum  \n",
        "          curr_sum = curr_sum + nums[i]  \n",
        "    \n",
        "          # To handle sum=0 at last index  \n",
        "          if (curr_sum == 0):  \n",
        "              max_len = i + 1 \n",
        "              ending_index = i  \n",
        "    \n",
        "          # If this sum is seen before,  \n",
        "          if curr_sum in hash_map: \n",
        "                \n",
        "              # If max_len is smaller than new subarray \n",
        "              # Update max_len and ending_index \n",
        "              if max_len < i - hash_map[curr_sum]: \n",
        "                  max_len = i - hash_map[curr_sum] \n",
        "                  ending_index = i \n",
        "          else:  \n",
        "    \n",
        "              # else put this sum in dictionary  \n",
        "              hash_map[curr_sum] = i   \n",
        "            \n",
        "      for i in range (0, n):  \n",
        "          if(nums[i] == -1):  \n",
        "              nums[i] = 0 \n",
        "          else:  \n",
        "              nums[i] = 1 \n",
        "                \n",
        "      print (ending_index - max_len + 1, end =\" \") \n",
        "      print (\"to\", end = \" \") \n",
        "      print (ending_index) \n",
        "    \n",
        "      return max_len \n",
        "\n",
        "InputArr = [1,1,1,0,0,0,1]\n",
        "# InputArr =[1,1,1,1,1,1]\n",
        "test = Solution()\n",
        "print(test.findMaxLength(InputArr))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "0 to 5\n",
            "6\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "9Ma9B3VW5Hif",
        "colab_type": "code",
        "outputId": "79bd085d-ac93-48ad-80ac-6396f5c35058",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "# FASTEST ANSWER \n",
        "from typing import List\n",
        "class Solution:\n",
        "    def findMaxLength(self, nums: List[int]) -> int:\n",
        "        d = {0: -1}\n",
        "        net = 0\n",
        "        mx = 0\n",
        "\n",
        "        for i, x in enumerate(nums):\n",
        "            if x == 1:\n",
        "                net += 1\n",
        "            else:\n",
        "                net -= 1\n",
        "\n",
        "            if net in d:\n",
        "               l = i - d[net]\n",
        "               if l > mx:\n",
        "                   mx = l\n",
        "            else:\n",
        "                d[net] = i\n",
        "\n",
        "            # print(f\"\\ni={i}, x={x}, net={net}, mx={mx}\")\n",
        "            # print(d)\n",
        "\n",
        "        return mx\n",
        "InputArr = [1,1,1,0,0,0,1]\n",
        "# InputArr =[1,1,1,1,1,1]\n",
        "test = Solution()\n",
        "print(test.findMaxLength(InputArr))\n",
        "\n"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "6\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "SL5-APPC7Nne",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Second fastest answer \n",
        "class Solution:\n",
        "    def findMaxLength(self, nums: List[int]) -> int:\n",
        "        maxlen = count = 0\n",
        "        d = {0: -1}\n",
        "        for i, num in enumerate(nums):\n",
        "            if num == 0:\n",
        "                count -= 1\n",
        "            else:\n",
        "                count += 1\n",
        "            if count in d:\n",
        "                if i - d[count] > maxlen:\n",
        "                    maxlen = i - d[count]\n",
        "            else:\n",
        "                d[count] = i\n",
        "        return maxlen"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "AC6Bxksf2T5m",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#Day 14. String shift\n",
        "import collections\n",
        "\n",
        "class Solution:\n",
        "    def stringShift(self, s: str, shift: List[List[int]]) -> str:\n",
        "        left = right = 0\n",
        "        for dir in shift:\n",
        "            if dir[0] == 0:\n",
        "                left += dir[1]\n",
        "            else:\n",
        "                right += dir[1]\n",
        "        from collections import deque\n",
        "         \n",
        "        if left == right:\n",
        "            return s\n",
        "        else:\n",
        "            str_re = deque(s)\n",
        "            str_re.rotate(right - left)\n",
        "            return ''.join(list(str_re))\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "n9ZK_ymGEf4O",
        "colab_type": "code",
        "outputId": "b171ca6a-938f-4798-8faf-3179f10a4159",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "# day 15\n",
        "from typing import List\n",
        "class Solution:\n",
        "    def productExceptSelf(self, nums: List[int]) -> List[int]:    \n",
        "      from functools import reduce    \n",
        "      output = []\n",
        "      for i in range(0,len(nums)):\n",
        "        arr = []\n",
        "        arr = nums[:i] + nums[i+1:]\n",
        "        output.append(reduce((lambda x, y: x * y), arr))\n",
        "\n",
        "      return output\n",
        "\n",
        "Input = [1,2,3,4]\n",
        "\n",
        "Test = Solution()\n",
        "Test.productExceptSelf(Input)\n",
        "  "
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[24, 12, 8, 6]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 14
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ot8cb9izEx_8",
        "colab_type": "code",
        "outputId": "a06fbdfd-b5c7-453c-8f1d-c77793378e38",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 170
        }
      },
      "source": [
        "from typing import List\n",
        "\n",
        "class Solution:\n",
        "    def productExceptSelf(self, nums: List[int]) -> List[int]:    \n",
        "      from functools import reduce    \n",
        "      output = [1]* len(nums)\n",
        "      prod = 1\n",
        "      for i in range(0,len(nums)): # to go forward in array \n",
        "        output[i] *=prod\n",
        "        prod *= nums[i]\n",
        "      prod = 1\n",
        "      for i in range(len(nums)-1,-1,-1): # to go backward in array\n",
        "        print(i)\n",
        "      return output\n",
        "\n",
        "Input = [1,2,3,4]\n",
        "\n",
        "Test = Solution()\n",
        "Test.productExceptSelf(Input)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "0\n",
            "1\n",
            "2\n",
            "3\n",
            "3\n",
            "2\n",
            "1\n",
            "0\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[1, 1, 2, 6]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 29
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "t7qOsctAQyNR",
        "colab_type": "code",
        "outputId": "04f1ab56-ba76-4bc0-cee6-3f58ef594111",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 170
        }
      },
      "source": [
        "#Day 16 Valid Parenthesis String\n",
        "\n",
        "from typing import List\n",
        "\n",
        "class Solution:\n",
        "  def checkValidString(self, s: str) -> bool:\n",
        "    low = high = 0\n",
        "    for char in s:\n",
        "      low += 1 if char == '(' else  -1\n",
        "      high += 1 if char != ')' else  -1\n",
        "      if high <0:\n",
        "        break\n",
        "      print(\"low:\",low,\"  high:\",high)\n",
        "      low= max(low,0)\n",
        "      \n",
        "    return low == 0\n",
        "\n",
        "Input = \"(((**)))\"\n",
        "\n",
        "Test = Solution()\n",
        "Test.checkValidString(Input)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "low: 1   high: 1\n",
            "low: 2   high: 2\n",
            "low: 3   high: 3\n",
            "low: 2   high: 4\n",
            "low: 1   high: 5\n",
            "low: 0   high: 4\n",
            "low: -1   high: 3\n",
            "low: -1   high: 2\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "True"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 6
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "jVum3mBtwALC",
        "colab_type": "code",
        "outputId": "4f1b7b67-b80d-4412-bae3-063293dc9979",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 578
        }
      },
      "source": [
        "# Day 16. Number of island\n",
        "from typing import List\n",
        "class Solution:\n",
        "    def numIslands(self, grid: List[List[str]]) -> int:\n",
        "        island_count = 0\n",
        "        if not grid:\n",
        "            return island_count\n",
        "\n",
        "        row_len = len(grid)\n",
        "        col_len = len(grid[0])\n",
        "        # 4 direction left, right, up, down\n",
        "        dir_row = [0, -1, 0, 1] \n",
        "        dir_col = [-1, 0, 1, 0]\n",
        "\n",
        "        def RoundToWater(i_row, i_col):\n",
        "          if 0 <= i_row < row_len and 0 <= i_col < col_len and grid[i_row][i_col] == \"1\":\n",
        "            for k in range(row_len):\n",
        "                print(grid[k])\n",
        "            print(\"/n\")\n",
        "\n",
        "            grid[i_row][i_col] = \"0\"\n",
        "            for dir in range(len(dir_row)):\n",
        "                RoundToWater(i_row + dir_row[dir], i_col + dir_col[dir])\n",
        "                       \n",
        "        for i in range(row_len):\n",
        "            for j in range(col_len):\n",
        "                if grid[i][j] == \"1\":\n",
        "                    island_count += 1\n",
        "                    # increase island count and change land connected to zeros\n",
        "                    RoundToWater(i,j)\n",
        "                    for k in range(row_len):\n",
        "                      print(grid[k])\n",
        "                    print('/n')\n",
        "        \n",
        "        return island_count\n",
        "\n",
        "\n",
        "\n",
        "Input = [[\"1\",\"1\",\"1\",\"1\",\"0\"],\n",
        "         [\"1\",\"1\",\"0\",\"1\",\"0\"],\n",
        "         [\"1\",\"1\",\"0\",\"0\",\"0\"],\n",
        "         [\"0\",\"0\",\"0\",\"0\",\"0\"]]\n",
        "\n",
        "Input2 = [[\"1\",\"1\",\"1\"],\n",
        "          [\"0\",\"1\",\"0\"],\n",
        "          [\"1\",\"1\",\"1\"]]\n",
        "\n",
        "Test = Solution()\n",
        "print(Test.numIslands(Input2))\n"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "['1', '1', '1']\n",
            "['0', '1', '0']\n",
            "['1', '1', '1']\n",
            "/n\n",
            "['0', '1', '1']\n",
            "['0', '1', '0']\n",
            "['1', '1', '1']\n",
            "/n\n",
            "['0', '0', '1']\n",
            "['0', '1', '0']\n",
            "['1', '1', '1']\n",
            "/n\n",
            "['0', '0', '0']\n",
            "['0', '1', '0']\n",
            "['1', '1', '1']\n",
            "/n\n",
            "['0', '0', '0']\n",
            "['0', '0', '0']\n",
            "['1', '1', '1']\n",
            "/n\n",
            "['0', '0', '0']\n",
            "['0', '0', '0']\n",
            "['1', '0', '1']\n",
            "/n\n",
            "['0', '0', '0']\n",
            "['0', '0', '0']\n",
            "['0', '0', '1']\n",
            "/n\n",
            "['0', '0', '0']\n",
            "['0', '0', '0']\n",
            "['0', '0', '0']\n",
            "/n\n",
            "1\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "-SspUNJ6ayi9",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# 112 ms solution\n",
        "\n",
        "class Solution:\n",
        "    def numIslands(self, grid: List[List[str]]) -> int:\n",
        "        def recurse(grid,r,c):\n",
        "            grid[r][c] = '0'\n",
        "            if r-1 >= 0 and grid[r-1][c] == '1':\n",
        "                recurse(grid,r-1,c)\n",
        "            if r+1 < len(grid) and grid[r+1][c] == '1':\n",
        "                recurse(grid,r+1,c)\n",
        "            if c-1 >= 0 and grid[r][c-1] == '1':\n",
        "                recurse(grid,r,c-1)\n",
        "            if c+1 < len(grid[0]) and grid[r][c+1] == '1':\n",
        "                recurse(grid,r,c+1)\n",
        "        \n",
        "        count = 0\n",
        "        for i in range(len(grid)):\n",
        "            for j in range(len(grid[0])):\n",
        "                if grid[i][j] == '1':\n",
        "                    count+=1\n",
        "                    recurse(grid,i,j)\n",
        "        return count\n",
        "\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "VMGTyGJ19r8O",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Array consecutive \n",
        "\"\"\"Input: [1,1,0,1,1,1]\n",
        "Output: 3\n",
        "Explanation: The first two digits or the last three digits are consecutive 1s.\n",
        "    The maximum number of consecutive 1s is 3.\"\"\"\n",
        "class Solution:\n",
        "    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:\n",
        "        max_len, cur_len = 0, 0\n",
        "        for num in nums:\n",
        "            if num:\n",
        "                cur_len += 1\n",
        "            else:\n",
        "                max_len = max(max_len, cur_len)\n",
        "                cur_len = 0\n",
        "        return max(max_len, cur_len)\n",
        "\n",
        "# very fast answer, iterate through the array while doing comparisons\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "paF5zMvqgj5V",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Day 17. Search in Rotated Sorted Array\n",
        "\"\"\"Solution\n",
        "Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.\n",
        "(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).\n",
        "You are given a target value to search. If found in the array return its index, otherwise return -1.\n",
        "You may assume no duplicate exists in the array.\n",
        "Your algorithm's runtime complexity must be in the order of O(log n).\"\"\"\n",
        "# Input: nums = [4,5,6,7,0,1,2], target = 0\n",
        "# Output: 4\n",
        "\n",
        "class Solution:\n",
        "    def search(self, nums: List[int], target: int) -> int:\n",
        "        l, r = 0, len(nums) - 1\n",
        "        # using binary search \n",
        "        while l <= r:\n",
        "            m = (l + r) // 2\n",
        "            \n",
        "            if nums[m] == target:\n",
        "                return m\n",
        "            elif nums[m] >= nums[l]: # Mid > left, pivot point is on the right side\n",
        "                if target >= nums[l] and target < nums[m]:\n",
        "                    r = m - 1 # target on left side\n",
        "                else:\n",
        "                    l = m + 1 # target on right side\n",
        "            else: # mid < left, pivot point is on the left side \n",
        "                if target > nums[m] and target <= nums[r]:\n",
        "                    l = m + 1\n",
        "                else:\n",
        "                    r = m - 1\n",
        "\n",
        "        return -1"
      ],
      "execution_count": 0,
      "outputs": []
    }
  ]
}