LeetCode/Aug_end.ipynb

{
    "cells": [
        {
            "cell_type": "markdown",
            "source": [
                "# To find if a string is a subsequence of another string\r\n",
                "---\r\n",
                "* iter() funtion is used\r\n",
                "* all() function return True if all the elements in the list is True(basically a large and gate)"
            ],
            "metadata": {}
        },
        {
            "cell_type": "code",
            "execution_count": 40,
            "source": [
                "def isSubsequence(s,t):\r\n",
                "    t=iter(t)\r\n",
                "    return all(i in t for i in s)"
            ],
            "outputs": [],
            "metadata": {}
        },
        {
            "cell_type": "markdown",
            "source": [
                "An iterator can only be iterated once. i in t will both return True if i is an element produced by t, but also modify t by consuming each element that was looked at in order to determine if i in t was true.\r\n",
                "\r\n",
                "For example:\r\n",
                "\r\n",
                "\r\n",
                "    >>> t = iter([1,2,3,4,5,6])\r\n",
                "    >>> 3 in t\r\n",
                "    True\r\n",
                "    >>> list(t)\r\n",
                "    [4, 5, 6]\r\n",
                "\r\n",
                "So when using a single fixed iterator in the call to all, each i in t can only consider values from the original t that haven't already been looked at by previous uses of i in t.\r\n",
                "\r\n",
                "Without t = iter(t), each evaluation of i in t would use the full original value of t:\r\n",
                "\r\n",
                "    >>> t = [1,2,3,4,5,6]\r\n",
                "    >>> 3 in t\r\n",
                "    True\r\n",
                "    >>> list(t)\r\n",
                "    [1, 2, 3, 4, 5, 6]\r\n",
                "\r\n",
                "and so isSubsequence would really only test if s was a subset of t."
            ],
            "metadata": {}
        },
        {
            "cell_type": "markdown",
            "source": [
                "> #Note\r\n",
                "\r\n",
                "`enumerate(iterable,start=0)` is a funtion which is similar to `iter()` but also returns a counter (index of current element being iterated)"
            ],
            "metadata": {}
        },
        {
            "cell_type": "code",
            "execution_count": 41,
            "source": [
                "# enemerate() example\r\n",
                "\r\n",
                "l1 = [\"eat\",\"sleep\",\"repeat\"]\r\n",
                "s1 = \"hello\"\r\n",
                " \r\n",
                "# creating enumerate objects\r\n",
                "obj1 = enumerate(l1)\r\n",
                "obj2 = enumerate(s1)\r\n",
                " \r\n",
                "print (\"Return type:\",type(obj1))\r\n",
                "print (list(enumerate(l1)))\r\n",
                " \r\n",
                "# changing start index to 2 from 0\r\n",
                "print (list(enumerate(s1,2)))"
            ],
            "outputs": [
                {
                    "output_type": "stream",
                    "name": "stdout",
                    "text": [
                        "Return type: <class 'enumerate'>\n",
                        "[(0, 'eat'), (1, 'sleep'), (2, 'repeat')]\n",
                        "[(2, 'h'), (3, 'e'), (4, 'l'), (5, 'l'), (6, 'o')]\n"
                    ]
                }
            ],
            "metadata": {}
        },
        {
            "cell_type": "markdown",
            "source": [
                "> # AUG _ 27th - Longest Uncommon Subsequence II\r\n",
                "\r\n",
                "Given an array of strings `strs`, return the **length of the longest uncommon subsequence** between them. If the longest uncommon subsequence does not exist, `return -1`.\r\n",
                "\r\n",
                "An **uncommon subsequence** between an array of strings is a string that is a **subsequence of one string but not the others.**\r\n",
                "\r\n",
                "A **subsequence** of a string `s` is a string that can be obtained after deleting any number of characters from `s`.\r\n",
                "\r\n",
                "* For example, `\"abc\"` is a subsequence of `\"aebdc\"` because you can delete the underlined characters in `\"a_b_c\"` to get `\"abc\".` Other subsequences of `\"aebdc\"` include `\"aebdc\"`, `\"aeb\"`, and `\"\"` (empty string)."
            ],
            "metadata": {}
        },
        {
            "cell_type": "markdown",
            "source": [
                "## Solution\r\n",
                "---"
            ],
            "metadata": {}
        },
        {
            "cell_type": "code",
            "execution_count": 42,
            "source": [
                "class Solution:\r\n",
                "        def findLUSlength(self, words):\r\n",
                "            def isSubsequence(s, t):\r\n",
                "                t = iter(t)\r\n",
                "                return all(c in t for c in s)\r\n",
                " \r\n",
                "            words.sort(key = lambda x:-len(x))\r\n",
                "            for i, word in enumerate(words):\r\n",
                "                if all(not isSubsequence(word, words[j]) for j in range(len(words)) if j != i): \r\n",
                "                    return len(word)\r\n",
                "        \r\n",
                "            return -1"
            ],
            "outputs": [],
            "metadata": {}
        },
        {
            "cell_type": "markdown",
            "source": [
                "#  bisect_left funtion \r\n",
                "---"
            ],
            "metadata": {}
        },
        {
            "cell_type": "markdown",
            "source": [
                " * function to find out where This function returns the position in the sorted list, \r\n",
                "* where the number passed in argument can be placed so as to maintain the resultant list in sorted order"
            ],
            "metadata": {}
        },
        {
            "cell_type": "markdown",
            "source": [
                "### Length of the Longest increasing substring.. Using bisect_left()\r\n"
            ],
            "metadata": {}
        },
        {
            "cell_type": "code",
            "execution_count": 43,
            "source": [
                "import bisect\r\n",
                "def lengthOfLIS(nums) -> int:\r\n",
                "    sub = []\r\n",
                "    for num in nums:\r\n",
                "        \r\n",
                "        i = bisect.bisect_left(sub, num)\r\n",
                "        if i == len(sub):\r\n",
                "            sub.append(num)\r\n",
                "        else:\r\n",
                "            sub[i] = num\r\n",
                "    return len(sub)\r\n",
                "nums=[10,9,2,5,3,7,101,18]\r\n",
                "print(lengthOfLIS(nums))\r\n"
            ],
            "outputs": [
                {
                    "output_type": "stream",
                    "name": "stdout",
                    "text": [
                        "4\n"
                    ]
                }
            ],
            "metadata": {}
        },
        {
            "cell_type": "markdown",
            "source": [
                "> # AUG_28th - Maximum Profit in Job Scheduling\r\n",
                "\r\n",
                "We have `n` jobs, where every job is scheduled to be done from `startTime[i]` to `endTime[i]`, obtaining a profit of `profit[i]`.\r\n",
                "\r\n",
                "You're given the `startTime`, `endTime` and `profit` arrays, return the maximum profit you can take such that there are no two jobs in the subset with overlapping time range.\r\n",
                "\r\n",
                "If you choose a job that ends at time `X` you will be able to start another job that starts at time `X`."
            ],
            "metadata": {}
        },
        {
            "cell_type": "markdown",
            "source": [
                "## Solution\r\n"
            ],
            "metadata": {}
        },
        {
            "cell_type": "code",
            "execution_count": 44,
            "source": [
                "def jobScheduling(startTime, endTime, profit) -> int:\r\n",
                "        \r\n",
                "    joball=sorted(list(zip(startTime, endTime, profit)))\r\n",
                "    st=[i[0]  for i in joball]\r\n",
                "    n=len(joball)\r\n",
                "    dp=[0] * (n+1)\r\n",
                "    for k in range(n-1,-1,-1):\r\n",
                "        temp=bisect.bisect_left(st,joball[k][1])\r\n",
                "        dp[k]=max(joball[k][2] + dp[temp], dp[k+1])\r\n",
                "    return dp[0]\r\n",
                "    \r\n",
                "startTime=[1,2,3,3]\r\n",
                "endTime=[3,4,5,6]\r\n",
                "profit=[50,10,40,70]\r\n",
                "print(jobScheduling(startTime, endTime, profit))"
            ],
            "outputs": [
                {
                    "output_type": "stream",
                    "name": "stdout",
                    "text": [
                        "120\n"
                    ]
                }
            ],
            "metadata": {}
        },
        {
            "cell_type": "markdown",
            "source": [
                "## Explanation\r\n",
                "\r\n",
                "if we take job with number `k` , the job to be taken next is the nearest job after our forst job ends.\r\n",
                "\r\n",
                "we use binary search for that with the line `temp = bisect.bisect_left(st,joball[k][1]).\r\n",
                "\r\n",
                "The profit will be `joball[k][2] + dp[temp]`.\r\n",
                "\r\n",
                "we move the loop in reverse because to answer `dp[k]` we need queries for `dp[>k]`"
            ],
            "metadata": {}
        },
        {
            "cell_type": "markdown",
            "source": [
                "> # AUG_29th - Patching Array\r\n",
                "\r\n",
                "\r\n",
                "Given a sorted integer array `nums` and an integer `n`, add/patch elements to the array such that any number in the `range [1, n]` inclusive can be formed by the sum of some elements in the array.\r\n",
                "\r\n",
                "Return the minimum number of patches required.\r\n"
            ],
            "metadata": {}
        },
        {
            "cell_type": "markdown",
            "source": [
                "## Solution"
            ],
            "metadata": {}
        },
        {
            "cell_type": "code",
            "execution_count": null,
            "source": [
                "class Solution:\r\n",
                "    def minPatches(self, nums: List[int], n: int) -> int:\r\n",
                "        cnt=0 # cnt is the number of patches\r\n",
                "        summ=0 # summ is the total sum that can be reached from the elements in the array\r\n",
                "        i=0 # i is the index of the current element\r\n",
                "        m=len(nums)\r\n",
                "        while summ<n:  # if the total sum is less than n, then we need to add more elements to the array\r\n",
                "            if i >= m or nums[i] > summ+1: # if the current element is greater than the total sum, then we need to add more elements to the array\r\n",
                "                summ += summ+1 # add the current element to the total sum\r\n",
                "                cnt+=1 # add one patch\r\n",
                "            else:\r\n",
                "                summ += nums[i] # add the current element to the total sum\r\n",
                "                i+=1 # move to the next element\r\n",
                "        return cnt \r\n"
            ],
            "outputs": [],
            "metadata": {}
        },
        {
            "cell_type": "markdown",
            "source": [
                "> # AUG_30th - Range Addition II\n",
                "\n",
                "\n",
                "You are given an `m x n` matrix `M` initialized with all 0's and an array of operations ops, where `ops[i] = [ai, bi]` means` M[x][y]` should be incremented by one for all `0 <= x < ai` and `0 <= y < bi`.\n",
                "\n",
                "Count and return the number of maximum integers in the matrix after performing all the operations."
            ],
            "metadata": {}
        },
        {
            "cell_type": "markdown",
            "source": [
                "## Solution"
            ],
            "metadata": {}
        },
        {
            "cell_type": "code",
            "execution_count": null,
            "source": [
                "class Solution:\r\n",
                "    def maxCount(self, m: int, n: int, ops: List[List[int]]) -> int:\r\n",
                "        # the logic is to find the min of the options cause thats the part which is incremented the most times. \r\n",
                "        # We also have to check if ops contain anythong ass well.\r\n",
                "        if not ops:return m*n\r\n",
                "        a,b=m,n\r\n",
                "        for i,j in ops:\r\n",
                "            a=min(a,i)\r\n",
                "            b=min(b,j)\r\n",
                "        return a*b   "
            ],
            "outputs": [],
            "metadata": {}
        },
        {
            "cell_type": "markdown",
            "source": [
                "> # AUG_30th - Range Addition II\n",
                "\n",
                "Suppose an array of length `n` sorted in ascending order is **rotated** between `1` and `n` times. For example, the array `nums = [0,1,2,4,5,6,7]` might become:\n",
                "\n",
                "- `[4,5,6,7,0,1,2]` if it was rotated 4 times.\n",
                "- `[0,1,2,4,5,6,7]` if it was rotated 7 times.\n",
                "Notice that **rotating** an array `[a[0], a[1], a[2], ..., a[n-1]]` 1 time results in the array `[a[n-1], a[0], a[1], a[2], ..., a[n-2]]`.\n",
                "\n",
                "Given the sorted rotated array `nums` of **unique** elements, return the minimum element of this array.\n",
                "\n",
                "You must write an algorithm that runs in `O(log n)` time."
            ],
            "metadata": {}
        },
        {
            "cell_type": "code",
            "execution_count": null,
            "source": [
                "class Solution:\r\n",
                "    def findMin(self, nums: List[int]) -> int:\r\n",
                "        left, right = 0, len(nums) - 1 # left and right pointer\r\n",
                "        while nums[left] > nums[right]: # if left > right, then the min is in the middle\r\n",
                "            middle  = (left + right) // 2 #\r\n",
                "            if nums[middle] < nums[right]: # if middle > right, then the min is in the right\r\n",
                "                right = middle\r\n",
                "            else:\r\n",
                "                left = middle + 1\r\n",
                "        return nums[left]\r\n"
            ],
            "outputs": [],
            "metadata": {}
        },
        {
            "cell_type": "markdown",
            "source": [
                "> # [click me for September solutions](https://github.com/kiransbaliga/DSA-with-leetcode/blob/main/LeetCode/September.ipynb)  "
            ],
            "metadata": {}
        }
    ],
    "metadata": {
        "orig_nbformat": 4,
        "language_info": {
            "name": "python",
            "version": "3.9.6",
            "mimetype": "text/x-python",
            "codemirror_mode": {
                "name": "ipython",
                "version": 3
            },
            "pygments_lexer": "ipython3",
            "nbconvert_exporter": "python",
            "file_extension": ".py"
        },
        "kernelspec": {
            "name": "python3",
            "display_name": "Python 3.9.6 64-bit"
        },
        "interpreter": {
            "hash": "23300995598eec4bcf6bd89cf02d1c3675e8b2616661418dbbf5580aa901878d"
        }
    },
    "nbformat": 4,
    "nbformat_minor": 2
}