30daysLeetCode_day19_30th.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "30daysLeetCode_day19_30th.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "authorship_tag": "ABX9TyOL5MysJNglOJvYaQWX8bAQ",
      "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/30daysLeetCode_day19_30th.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "YmI_4rGKzPT4",
        "colab_type": "code",
        "outputId": "369cb388-d1f8-45be-cf0c-b8925f0c1f84",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 141
        }
      },
      "source": [
        "#Day 20\n",
        "# A O(n^2) Python3 program for construction of BST from preorder traversal \n",
        "# A binary tree node \n",
        "class Node(): \n",
        "\t\n",
        "\t# A 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",
        "# constructTreeUtil.preIndex is a static variable of \n",
        "# function constructTreeUtil \n",
        "\n",
        "# Function to get the value of static variable \n",
        "# constructTreeUtil.preIndex \n",
        "def getPreIndex(): \n",
        "\treturn constructTreeUtil.preIndex \n",
        "\n",
        "# Function to increment the value of static variable \n",
        "# constructTreeUtil.preIndex \n",
        "def incrementPreIndex(): \n",
        "\tconstructTreeUtil.preIndex += 1\n",
        "\n",
        "# A recurseive function to construct Full from pre[]. \n",
        "# preIndex is used to keep track of index in pre[[]. \n",
        "def constructTreeUtil(pre, low, high, size): \n",
        "\t\n",
        "\t# Base Case \n",
        "\tif( getPreIndex() >= size or low > high): \n",
        "\t\treturn None\n",
        "\n",
        "\t# The first node in preorder traversal is root. So take \n",
        "\t# the node at preIndex from pre[] and make it root, \n",
        "\t# and increment preIndex \n",
        "\troot = Node(pre[getPreIndex()]) \n",
        "\tincrementPreIndex() \n",
        "\n",
        "\t# If the current subarray has onlye one element, \n",
        "\t# no need to recur \n",
        "\tif low == high : \n",
        "\t\treturn root \n",
        "\n",
        "\t# Search for the first element greater than root \n",
        "\tfor i in range(low, high+1): \n",
        "\t\tif (pre[i] > root.data): \n",
        "\t\t\tbreak\n",
        "\t\n",
        "\t# Use the index of element found in preorder to divide \n",
        "\t# preorder array in two parts. Left subtree and right \n",
        "\t# subtree \n",
        "\troot.left = constructTreeUtil(pre, getPreIndex(), i-1 , size) \n",
        "\n",
        "\troot.right = constructTreeUtil(pre, i, high, size) \n",
        "\t\n",
        "\treturn root \n",
        "\n",
        "# The main function to construct BST from given preorder \n",
        "# traversal. This function mailny uses constructTreeUtil() \n",
        "def constructTree(pre): \n",
        "\tsize = len(pre) \n",
        "\tconstructTreeUtil.preIndex = 0\n",
        "\treturn constructTreeUtil(pre, 0, size-1, size) \n",
        "\n",
        "def printInorder(root): \n",
        "\tif root is None: \n",
        "\t\treturn\n",
        "\tprintInorder(root.left) \n",
        "\tprint(root.data) \n",
        "\tprintInorder(root.right) \n",
        "\n",
        "# Driver program to test above function \n",
        "pre = [10, 5, 1, 7, 40, 50] \n",
        "\n",
        "root = constructTree(pre) \n",
        "print(\"Inorder traversal of the constructed tree:\")\n",
        "printInorder(root) \n",
        "\n",
        "# This code is contributed by Nikhil Kumar Singh(nickzuck_007) \n"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Inorder traversal of the constructed tree:\n",
            "1\n",
            "5\n",
            "7\n",
            "10\n",
            "40\n",
            "50\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "VPpBiTzP1kth",
        "colab_type": "code",
        "outputId": "1d450f43-5dc5-4cd5-a61a-365c977a4086",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 230
        }
      },
      "source": [
        "# Subarray Sum Equals K\n",
        "# Day 21 ---- 120 ms\n",
        "from collections import defaultdict \n",
        "from typing import List\n",
        "\n",
        "class Solution(object):\n",
        "  def SubArrSum(self, nums: List[int], k: int) -> int:\n",
        "    total = 0\n",
        "    sums = defaultdict(int)\n",
        "    running_sum = 0\n",
        "\n",
        "    for num in nums:\n",
        "      running_sum += num \n",
        "      \n",
        "      if running_sum == k:\n",
        "        total += 1\n",
        "      if running_sum - k in sums:\n",
        "        total += sums[running_sum - k]\n",
        "\n",
        "      sums[running_sum] += 1\n",
        "      print(\"k = \",k,\" running_sum = \", running_sum, \" running_sum - k = \", running_sum -k,\" sums = \", sums, \"total\", total)\n",
        "    print(sums)\n",
        "    return total \n",
        "\n",
        "Input = [0,0,0,0,0,0,0,0,0,0]\n",
        "test = Solution()\n",
        "print(test.SubArrSum(Input,0))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "k =  0  running_sum =  0  running_sum - k =  0  sums =  defaultdict(<class 'int'>, {0: 1}) total 1\n",
            "k =  0  running_sum =  0  running_sum - k =  0  sums =  defaultdict(<class 'int'>, {0: 2}) total 3\n",
            "k =  0  running_sum =  0  running_sum - k =  0  sums =  defaultdict(<class 'int'>, {0: 3}) total 6\n",
            "k =  0  running_sum =  0  running_sum - k =  0  sums =  defaultdict(<class 'int'>, {0: 4}) total 10\n",
            "k =  0  running_sum =  0  running_sum - k =  0  sums =  defaultdict(<class 'int'>, {0: 5}) total 15\n",
            "k =  0  running_sum =  0  running_sum - k =  0  sums =  defaultdict(<class 'int'>, {0: 6}) total 21\n",
            "k =  0  running_sum =  0  running_sum - k =  0  sums =  defaultdict(<class 'int'>, {0: 7}) total 28\n",
            "k =  0  running_sum =  0  running_sum - k =  0  sums =  defaultdict(<class 'int'>, {0: 8}) total 36\n",
            "k =  0  running_sum =  0  running_sum - k =  0  sums =  defaultdict(<class 'int'>, {0: 9}) total 45\n",
            "k =  0  running_sum =  0  running_sum - k =  0  sums =  defaultdict(<class 'int'>, {0: 10}) total 55\n",
            "defaultdict(<class 'int'>, {0: 10})\n",
            "55\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "48s85ggzOgbK",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#Day 21. 90ms solution\n",
        "\n",
        "class Solution:\n",
        "    def subarraySum(self, nums: List[int], k: int) -> int:\n",
        "        d = {0:1}\n",
        "        total = 0\n",
        "        count = 0\n",
        "        for num in nums:\n",
        "            total += num \n",
        "            if total - k in d:\n",
        "                count += d[total-k]\n",
        "            \n",
        "            d[total] = d.get(total, 0) + 1\n",
        "            \n",
        "        return count "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "cbCqsERCdocz",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Day 22. Bitwise AND for range of number\n",
        "# Use stack over flow algorthm \n",
        "# My answer 56 ms\n",
        "\n",
        "class Solution:\n",
        "    def rangeBitwiseAnd(self, m: int, n: int) -> int:\n",
        "        if m == n:\n",
        "            return m\n",
        "        \n",
        "        m_str = str(bin(m))[2:]\n",
        "        n_str = str(bin(n))[2:] \n",
        "        if 1 < len(m_str) == len(n_str):    \n",
        "            print(m_str,n_str)\n",
        "            s = 1\n",
        "            while m_str != n_str:\n",
        "                m_str = m_str[:-1]\n",
        "                n_str = n_str[:-1]\n",
        "                s *= 2\n",
        "            return s * int(m_str, 2)\n",
        "        elif 1 == len(m_str) == len(n_str):\n",
        "            return m&n\n",
        "        else:\n",
        "            return 0"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Bvgc-GUfeOtR",
        "colab_type": "code",
        "outputId": "43a3d9fd-4dd4-4e19-d834-a70e14d8ebc3",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 70
        }
      },
      "source": [
        "# My answer 32 ms\n",
        "\n",
        "class Solution:\n",
        "    def rangeBitwiseAnd(self, m: int, n: int) -> int:\n",
        "        i=0\n",
        "        while(m!=n):\n",
        "            m>>=1 # shift right \n",
        "            n>>=1\n",
        "            i+=1\n",
        "            print(m,n,i)\n",
        "        return n<<i # shift left \n",
        "\n",
        "test = Solution()\n",
        "print(test.rangeBitwiseAnd(5,7))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "2 3 1\n",
            "1 1 2\n",
            "4\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "pQi2P7Kver1o",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Day 24. fastest answer ( 160ms)\n",
        "# \n",
        "from collections import OrderedDict\n",
        "\n",
        "class LRUCache:\n",
        "    def __init__(self, capacity):\n",
        "        self.cache = OrderedDict()\n",
        "        self.capacity = capacity\n",
        "\n",
        "\n",
        "    def get(self, key):\n",
        "        if key in self.cache:\n",
        "            self.cache.move_to_end(key)\n",
        "\n",
        "        return self.cache.get(key, -1)\n",
        "        \n",
        "\n",
        "    def put(self, key, value):\n",
        "        if key in self.cache:\n",
        "            self.cache.move_to_end(key)\n",
        "        else:\n",
        "            if(len(self.cache) >= self.capacity):\n",
        "                self.cache.popitem(last=False)\n",
        "        \n",
        "        self.cache[key] = value"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "PQHLeRChrreq",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# My answer:  1200 ms\n",
        "class LRUCache:\n",
        "\n",
        "    def __init__(self, capacity: int):\n",
        "        self.capacity = capacity\n",
        "        self.dict_pre = {}\n",
        "        self.last_use = [None] * capacity \n",
        "        \n",
        "    def update_last(self, key: int) -> None:\n",
        "      # reached capacity pop the 1st out\n",
        "        if len(self.last_use) >= self.capacity: \n",
        "            if key in self.last_use:\n",
        "                self.last_use.pop(self.last_use.index(key)) # very important\n",
        "            else:\n",
        "                self.last_use.pop(0)\n",
        "        self.last_use.append(key)\n",
        "\n",
        "    def get(self, key: int) -> int:\n",
        "        if key in self.dict_pre:\n",
        "            self.update_last(key)\n",
        "            return self.dict_pre[key]\n",
        "        else:\n",
        "            return -1\n",
        "        \n",
        "    def put(self, key: int, value: int) -> None:\n",
        "        if key not in self.dict_pre:\n",
        "            # not reached capacity yet\n",
        "            if len(self.dict_pre) < self.capacity:\n",
        "                self.dict_pre[key] = value\n",
        "                   \n",
        "            else: # capacity > 1 and reached capcacity delete the last use\n",
        "                self.dict_pre.pop(self.last_use[0])\n",
        "                \n",
        "        self.dict_pre[key]= value\n",
        "        self.update_last(key)\n",
        "        # print(self.dict_pre)\n",
        "        # print(self.last_use)\n",
        "        \n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "VAgc0fU-tEtQ",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Day 25: fk. Jump Game \n",
        "# 68 ms, fastest answer \n",
        "\n",
        "class Solution:\n",
        "    def canJump(self, nums: List[int]) -> bool:\n",
        "        # problem becomes, will we eventually get stuck on nums[i] == 0\n",
        "        # if nums[i] = 0, need to check nums[i-k] > k\n",
        "        # if satisfied, move on to find next zero\n",
        "        # if not satisfied until nums[0], return false\n",
        "        \n",
        "        # if array length 1, already at last index\n",
        "        if len(nums) == 1: return True\n",
        "        # if array length not 1, and nums[0] is zero, we're already stuck\n",
        "        if nums[0] == 0: return False\n",
        "        \n",
        "        # if last element is zero, we don't need to check it, we're guaranteed\n",
        "        # to reach it if nums[-2] is not zero, if nums[-2] is zero, we'll be \n",
        "        # checking later in this code whether we're stuck at it or not,\n",
        "        # if we'll be stuck at it, program will return False anyways.\n",
        "        if not nums[-1]:\n",
        "            nums.pop()\n",
        "        \n",
        "        # if there's no 0 in nums, automatically True\n",
        "        if 0 not in nums: return True\n",
        "        \n",
        "        # start from tail\n",
        "        i = len(nums)-1\n",
        "        while i > 0:\n",
        "            # look for zero, we only check if elements to the left of zero\n",
        "            # will get stuck at it\n",
        "            if nums[i]:\n",
        "                i -= 1\n",
        "                continue\n",
        "            zero = i # i index is zero\n",
        "            # while elements to the left of zero can only reach this zero or shorter\n",
        "            # we keep going left to look for a number that can jump past this zero\n",
        "            # if we find it, we go to top of while loop to look for another zero\n",
        "            while i >= 0 and nums[i] <= zero - i:\n",
        "                i -= 1\n",
        "            # if we are not able to find this number that can jump past zero at nums[0]\n",
        "            # i will change into -1, this is the only condition we fail the jump game.\n",
        "            if i == -1: return False\n",
        "        # if no failure is found, it means all zero can be jumped past, so we can win.\n",
        "        return True"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "OrE0LDSStRtL",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "\"\"\" day 25: Jump Game. \n",
        "Input: [2,3,1,1,4]\n",
        "Output: true\n",
        "Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index\"\"\"\n",
        "# my answer, checked solution, huhu. \n",
        "\n",
        "class Solution:\n",
        "    def canJump(self, nums: List[int]) -> bool:\n",
        "        max_index = 0\n",
        "        for i,num in enumerate(nums):\n",
        "            if i > max_index: # index can not be reached. \n",
        "                return False\n",
        "            max_index = max(max_index, i+ num)\n",
        "        return True"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "uP_zc7ygueKQ",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "class Solution:\n",
        "    def canJump(self, nums: List[int]) -> bool:\n",
        "        nearest = len(nums)-1\n",
        "        for i in range(len(nums)-2,-1,-1):\n",
        "            if nums[i] >= nearest - i:\n",
        "                nearest = i\n",
        "        return nearest == 0\n",
        "\n",
        "\n",
        "        "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "bqpt6TOyorX1",
        "colab_type": "code",
        "outputId": "dea29653-6842-47b4-804a-6fb065d7c0f3",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "# Day 25. Dynamic Programing \n",
        "\"\"\" Longest Common Subsequence (lcs)\n",
        "Given two strings text1 and text2, return the length of their longest common subsequence.\"\"\"\n",
        "# Input: text1 = \"abcde\", text2 = \"ace\" \n",
        "# Output: 3  \n",
        "# Explanation: The longest common subsequence is \"ace\" and its length is 3.\n",
        "\n",
        "from typing import List\n",
        "class Solution:\n",
        "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
        "      nn, mm = len(text1), len(text2)\n",
        "      # arr = [[None for i in range(nn)] for j in range(mm)] \n",
        "      def LCS(P :str, Q :str, n :int, m:int):\n",
        "        # if arr[n][m] != None:\n",
        "        #   return arr[n][m]\n",
        "        result = 0\n",
        "        if n == 0 or m == 0:\n",
        "          result = 0\n",
        "        elif P[-1] == Q[-1]:\n",
        "          result = 1 + LCS(P,Q,n-1,m-1)\n",
        "        elif P[-1] != Q[-1]:\n",
        "          tmp1 = LCS(P,Q,n-1,m)\n",
        "          tmp2 = LCS(P,Q,n,m-1)\n",
        "          result = max(tmp1,tmp2)\n",
        "        \n",
        "        # arr[n][m] = result\n",
        "        return result\n",
        "\n",
        "      return LCS(text1,text2,nn,mm)\n",
        "\n",
        "       \n",
        "text1 = \"abcdej\"\n",
        "text2 = \"acesj\" \n",
        "\n",
        "Test = Solution()\n",
        "\n",
        "Test.longestCommonSubsequence(text1,text2)\n",
        "\n",
        "\n"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "5"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 4
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "sw1T4ZiVU8Pn",
        "colab_type": "code",
        "outputId": "dfb47f52-46ba-4db1-c779-149693bbfd01",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 153
        }
      },
      "source": [
        "# Day 25. Solution \n",
        "\"\"\" Solution :\n",
        "For each prefix of text1, find lcs with each prefix of text 2, \n",
        "If the end characters of each prefix are equal, we can exend the lcs of the prefixes without the end characters.\n",
        "Else we take the longest lcs ignoring the last characters fro one prefix\n",
        "- Time - O(mn)\n",
        "- Space - O(n)\n",
        "\"\"\"\n",
        "class Solution:\n",
        "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
        "        m, n = len(text1), len(text2) \n",
        "        lcs = [0 for _ in range(n + 1)] \n",
        "        print(lcs)\n",
        "        for c1 in text1: # for prefix of text1 up to and including c1 \n",
        "            new_lcs = [0] \n",
        "            for j, c2 in enumerate(text2): \n",
        "                # for prefix of text2 up to and including c2 \n",
        "                if c1 == c2: \n",
        "                    new_lcs.append(1 + lcs[j]) \n",
        "                else: \n",
        "                    new_lcs.append(max(new_lcs[-1], lcs[j + 1])) \n",
        "            lcs = new_lcs \n",
        "            print(c1, lcs) \n",
        "        return lcs[-1]\n",
        "\n",
        "text1 = \"abcdej\"\n",
        "text2 = \"ace\" \n",
        "\n",
        "Test = Solution()\n",
        "\n",
        "Test.longestCommonSubsequence(text1,text2)\n",
        "\n",
        "\n"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[0, 0, 0, 0]\n",
            "a [0, 1, 1, 1]\n",
            "b [0, 1, 1, 1]\n",
            "c [0, 1, 2, 2]\n",
            "d [0, 1, 2, 2]\n",
            "e [0, 1, 2, 3]\n",
            "j [0, 1, 2, 3]\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "3"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 10
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "mYPwHHZ8XIeY",
        "colab_type": "code",
        "outputId": "830c69a5-3a50-4cfd-ad8d-c2d4104ee828",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 119
        }
      },
      "source": [
        "# Day 26 Maximal Square , fk my answer does not work for some reasons\n",
        "\n",
        "from typing import List\n",
        "\n",
        "class Solution:\n",
        "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
        "        y_len = len(matrix)\n",
        "        x_len = len(matrix[0])\n",
        "        # sum_grid = y_len*[x_len*[-1]]  # This is wrong \n",
        "        sum_grid = [[-1 for i in range(x_len)] for j in range(y_len)] # this is the right way to initialize . \n",
        "\n",
        "        # Contruct a sum matrix \n",
        "        # a. copy 1st row and 1st col      \n",
        "        sum_grid[0] = [int(i) for i in matrix[0]]\n",
        "        for j in range(1,y_len):\n",
        "            sum_grid[j][0] = int(matrix[j][0])\n",
        "        print(sum_grid)\n",
        "        # b. other entries \n",
        "        for y in range(1,y_len):\n",
        "            print(\"/n\")\n",
        "            for x in range(1,x_len):\n",
        "                if matrix[y][x] == \"1\":\n",
        "                  sum_grid[y][x] = min(sum_grid[y][x-1],sum_grid[y-1][x],sum_grid[y-1][x-1]) + 1\n",
        "                else:\n",
        "                  sum_grid[y][x] = 0\n",
        "                \n",
        "        print(sum_grid)\n",
        "        \n",
        "        Max = 0\n",
        "        for y in range(1,y_len):\n",
        "            for x in range(1,x_len):\n",
        "                if sum_grid[y][x] > Max:\n",
        "                    Max = sum_grid[y][x]     \n",
        "        return Max\n",
        "\n",
        "Input = [[\"1\",\"0\",\"1\",\"0\",\"0\"],\n",
        "         [\"0\",\"0\",\"1\",\"1\",\"1\"],\n",
        "         [\"1\",\"1\",\"1\",\"1\",\"1\"],\n",
        "         [\"1\",\"0\",\"0\",\"1\",\"0\"]]\n",
        "\n",
        "\n",
        "Test = Solution()\n",
        "\n",
        "Test.maximalSquare(Input)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[[1, 0, 1, 0, 0], [0, -1, -1, -1, -1], [1, -1, -1, -1, -1], [1, -1, -1, -1, -1]]\n",
            "/n\n",
            "/n\n",
            "/n\n",
            "[[1, 0, 1, 0, 0], [0, 0, 1, 1, 1], [1, 1, 1, 2, 2], [1, 0, 0, 1, 0]]\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "2"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 3
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "CPul5-ngri4O",
        "colab_type": "code",
        "outputId": "eee5e569-b222-4bfc-c636-6c7f270ec006",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "# Day 26. Fastest solution \n",
        "\n",
        "class Solution:\n",
        "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
        "        if not matrix:\n",
        "            return 0\n",
        "        m, n = len(matrix), len(matrix[0])\n",
        "        heights = [0] * n\n",
        "        max_width = 0\n",
        "        for i in range(m):\n",
        "            width = 0\n",
        "            for j in range(n):\n",
        "                # populates heights arr\n",
        "                if matrix[i][j] == '1':\n",
        "                    heights[j] += 1\n",
        "                else:\n",
        "                    heights[j] = 0\n",
        "                # calculates max square width using greedy approach\n",
        "                if heights[j] > max_width:\n",
        "                    width += 1\n",
        "                    if width > max_width:\n",
        "                        max_width, width = width, 0\n",
        "                else:\n",
        "                    width = 0\n",
        "        return max_width * max_width\n",
        "\n",
        "\n",
        "Input = [[\"1\",\"0\",\"1\",\"0\",\"0\"],\n",
        "         [\"1\",\"0\",\"1\",\"1\",\"1\"],\n",
        "         [\"1\",\"1\",\"1\",\"1\",\"1\"],\n",
        "         [\"1\",\"0\",\"0\",\"1\",\"0\"]]\n",
        "\n",
        "\n",
        "Test = Solution()\n",
        "\n",
        "Test.maximalSquare(Input)\n"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "4"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 10
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Z9NUcbBzv_eE",
        "colab_type": "code",
        "outputId": "ae462a4e-6bda-4093-a08e-5abc6d96eab6",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "# Day 26: Phone Solution \n",
        "class Solution:\n",
        "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
        "        \n",
        "        if not matrix or not matrix[0]: \n",
        "            return 0 \n",
        "        rows, cols = len(matrix), len(matrix[0]) \n",
        "        max_side = 0 \n",
        "        square_sides = [0] * cols # largest square side with cell in each col as bottom right \n",
        "        \n",
        "        for r in range(rows): \n",
        "            new_square_sides = [int(matrix[r][0])] + [0 for _ in range(cols-1)] \n",
        "            \n",
        "            for c in range(1, cols): \n",
        "                if matrix[r][c] == '1': \n",
        "                    new_square_sides[c] = 1 + min(new_square_sides[c-1], square_sides[c], square_sides[c-1])\n",
        "            max_side = max(max_side, max(new_square_sides)) \n",
        "            square_sides = new_square_sides \n",
        "        \n",
        "        return max_side**2\n",
        "\n",
        "\n",
        "Input = [[\"1\",\"0\",\"1\",\"0\",\"0\"],\n",
        "         [\"1\",\"0\",\"1\",\"1\",\"1\"],\n",
        "         [\"1\",\"1\",\"1\",\"1\",\"1\"],\n",
        "         [\"1\",\"0\",\"0\",\"1\",\"0\"]]\n",
        "\n",
        "\n",
        "\n",
        "Test = Solution()\n",
        "\n",
        "Test.maximalSquare(Input)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "4"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 12
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "41KSblXTwR1T",
        "colab_type": "code",
        "outputId": "14ee390e-3eb8-4f8e-b3bf-c916e56c06b7",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 119
        }
      },
      "source": [
        "def printMaxSubSquare(M): \n",
        "    R = len(M) # no. of rows in M[][] \n",
        "    C = len(M[0]) # no. of columns in M[][] \n",
        "  \n",
        "    S = [[0 for k in range(C)] for l in range(R)] \n",
        "    # here we have set the first row and column of S[][] \n",
        "    print(S)\n",
        "    # Construct other entries \n",
        "    for i in range(1, R): \n",
        "        for j in range(1, C): \n",
        "            if (M[i][j] == 1): \n",
        "                S[i][j] = min(S[i][j-1], S[i-1][j], \n",
        "                            S[i-1][j-1]) + 1\n",
        "            else: \n",
        "                S[i][j] = 0\n",
        "      \n",
        "    # Find the maximum entry and \n",
        "    # indices of maximum entry in S[][] \n",
        "    print(S)\n",
        "    max_of_s = S[0][0] \n",
        "    max_i = 0\n",
        "    max_j = 0\n",
        "    for i in range(R): \n",
        "        for j in range(C): \n",
        "            if (max_of_s < S[i][j]): \n",
        "                max_of_s = S[i][j] \n",
        "                max_i = i \n",
        "                max_j = j \n",
        "  \n",
        "    print(\"Maximum size sub-matrix is: \") \n",
        "    for i in range(max_i, max_i - max_of_s, -1): \n",
        "        for j in range(max_j, max_j - max_of_s, -1): \n",
        "            print (M[i][j], end = \" \") \n",
        "        print(\"\") \n",
        "  \n",
        "# Driver Program \n",
        "M = [[0, 1, 1, 0, 1], \n",
        "    [1, 1, 0, 1, 0], \n",
        "    [0, 1, 1, 1, 0], \n",
        "    [1, 1, 1, 1, 0], \n",
        "    [1, 1, 1, 1, 1], \n",
        "    [0, 0, 0, 0, 0]] \n",
        "  \n",
        "printMaxSubSquare(M) \n",
        "  "
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]\n",
            "[[0, 0, 0, 0, 0], [0, 1, 0, 1, 0], [0, 1, 1, 1, 0], [0, 1, 2, 2, 0], [0, 1, 2, 3, 1], [0, 0, 0, 0, 0]]\n",
            "Maximum size sub-matrix is: \n",
            "1 1 1 \n",
            "1 1 1 \n",
            "1 1 1 \n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "hBm2bpILxJ6p",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Day 28. Solution \n",
        "class FirstUnique:\n",
        "\n",
        "    def __init__(self, nums: List[int]):\n",
        "        self.nums = nums\n",
        "        self.unique_dict = {}\n",
        "        self.unique = -1\n",
        "        for num in self.nums:\n",
        "            if num not in self.unique_dict:\n",
        "                self.unique_dict[num] = 1\n",
        "            else:\n",
        "                self.unique_dict[num] += 1\n",
        "              \n",
        "        for num in self.unique_dict.keys():\n",
        "            if self.unique_dict[num] == 1:\n",
        "                self.unique = num\n",
        "                break           \n",
        "        # print(\"Init\",self.unique_dict)        \n",
        "        # print(\"Init\", self.unique)\n",
        "                \n",
        "    def showFirstUnique(self) -> int:\n",
        "        if not self.nums:\n",
        "            return null\n",
        "        # print(\"Show\", self.unique)\n",
        "        \n",
        "        return self.unique\n",
        "        \n",
        "\n",
        "    def add(self, value: int) -> None:\n",
        "        self.nums.append(value)\n",
        "        \n",
        "        if value not in self.unique_dict:\n",
        "            self.unique_dict[value] = 1\n",
        "        else:\n",
        "            self.unique_dict[value] += 1\n",
        "            if self.unique == value:\n",
        "                self.unique = -1\n",
        "            \n",
        "        # print(\"add\", self.unique_dict)  \n",
        "        for num in self.unique_dict.keys():\n",
        "            if self.unique_dict[num] == 1:\n",
        "                self.unique = num\n",
        "                break\n",
        "                \n",
        "        # print(\"add\", self.unique)     \n",
        "        \n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ysecvhslHigp",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Day 28 Accepted answer  896 ms\n",
        "\n",
        "class FirstUnique:\n",
        "\n",
        "    def __init__(self, nums: List[int]):\n",
        "        self.d = collections.OrderedDict()\n",
        "        for num in nums:\n",
        "            self.d[num] = self.d.get(num, 0) + 1\n",
        "        self.removed = set()\n",
        "        for key in list(self.d.keys()):\n",
        "            if self.d[key] > 1:\n",
        "                self.removed.add(key)\n",
        "                self.d.pop(key)\n",
        "        # print(self.d)\n",
        "        # print(next(iter(self.d)))\n",
        "\n",
        "    def showFirstUnique(self) -> int:\n",
        "        return next(iter(self.d)) if self.d else -1\n",
        "        \n",
        "\n",
        "    def add(self, value: int) -> None:\n",
        "        if value not in self.removed:\n",
        "            if value in self.d:\n",
        "                self.d.pop(value)\n",
        "                self.removed.add(value)\n",
        "            else:\n",
        "                self.d[value] = 1\n",
        "\n",
        "\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "0Zmw64Zga27c",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "\"\"\"\n",
        "ex. 1 \n",
        "Input: [1,2,3]\n",
        "\n",
        "       1\n",
        "      / \\\n",
        "     2   3\n",
        "\n",
        "Output: 6\n",
        "ex2. \n",
        "Input: [-10,9,20,null,null,15,7]\n",
        "\n",
        "   -10\n",
        "   / \\\n",
        "  9  20\n",
        "    /  \\\n",
        "   15   7\n",
        "\n",
        "Output: 42\n",
        "\"\"\"\n",
        "# Day 29. Solution 76 ms \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 __init__(self):\n",
        "        self.maxVal = 0\n",
        "    def getSum(self, root):\n",
        "        if not root:\n",
        "            return 0\n",
        "        left = max(0, self.getSum(root.left))\n",
        "        right = max(0, self.getSum(root.right))\n",
        "        \n",
        "        self.maxVal = max(self.maxVal, root.val+left+right )\n",
        "        \n",
        "        return max(left, right) + root.val\n",
        "    \n",
        "    def maxPathSum(self, root: TreeNode) -> int:\n",
        "        if not root:\n",
        "            return 0\n",
        "        self.maxVal = root.val\n",
        "        self.getSum(root)\n",
        "        return self.maxVal\n",
        "\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "B4U7VlOFbQsf",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# My answer follow GEEK  92 ms. \n",
        "\n",
        "# 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",
        "    \n",
        "    def maxPathSum(self, root: TreeNode) -> int:\n",
        "        \n",
        "        self.ret = float(\"-inf\")\n",
        "        self.FindMax(root)\n",
        "        \n",
        "        return self.ret\n",
        "\n",
        "    def FindMax(self, node: TreeNode) -> int:\n",
        "        temp_max = 0\n",
        "        global ret\n",
        "        \n",
        "        if node != None:\n",
        "            l = self.FindMax(node.left)\n",
        "            r = self.FindMax(node.right)\n",
        "            # when current node not is not root : then node + left(right) or only node.   \n",
        "            temp_max = max(max(l,r) + node.val, node.val)\n",
        "            #Current is root. then should compare: root + left + right to the temp_max\n",
        "            root_max = max(temp_max, node.val+l+r)\n",
        "\n",
        "            self.ret = max(root_max, self.ret)\n",
        "\n",
        "        return temp_max"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "eC1zw5AZ4E2y",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Last day: Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree\n",
        "\"\"\"Runtime: 108 ms\n",
        "Memory Usage: 15.2 MB\"\"\"\n",
        "\n",
        "\"\"\"Input: root = [0,1,0,0,1,0,null,null,1,0,0], arr = [0,1,0,1]\n",
        "Output: true\n",
        "Explanation: \n",
        "The path 0 -> 1 -> 0 -> 1 is a valid sequence (green color in the figure). \n",
        "Other valid sequences are: \n",
        "0 -> 1 -> 1 -> 0 \n",
        "0 -> 0 -> 0\n",
        "\"\"\"\n",
        "# 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 isValidSequence(self, root: TreeNode, arr: List[int]) -> bool:\n",
        "                  \n",
        "        def CheckNode(node :TreeNode, index : int)-> bool:\n",
        "            # current node is null or value is incorret\n",
        "            if not node or arr[index] != node.val:\n",
        "                return False\n",
        "            # value is correct check if current node is leave and index is the last index\n",
        "            if index == len(arr)-1:  \n",
        "                return True if (not node.left) and (not node.right) else False\n",
        "            return CheckNode(node.left, index + 1) or CheckNode(node.right,index + 1)\n",
        "        \n",
        "        return CheckNode(root, 0)\n",
        "\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "uYiaaU9e4baJ",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    }
  ]
}