Blind75.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "toc_visible": true,
      "collapsed_sections": [
        "Q4tzKEaQQFb6",
        "G4D5DhSpkuPk",
        "0Lh3e4yQvLjl",
        "qptqa7kP-cNE",
        "3ufj6-BxDB3g",
        "RPxzoOTJS0MB",
        "OjH8ED1i00kt",
        "UkfuGrFNMZBL",
        "kO8FIZdNOHMd",
        "nFRPT8-xQb0S",
        "0Z50FoXWzp8D"
      ],
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/mvdheram/DataStructures-Algorithms/blob/master/Blind75.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# BLIND 75\n",
        "\n",
        "\n",
        "[1] **Math Basic** : https://algo.monster/problems/math-basics \\\\\n",
        "[2] **Run-time Cheatsheet** : https://algo.monster/problems/runtime_summary \\\\\n",
        "[3] **Tech interview preparation** :https://www.techinterviewhandbook.org/best-practice-questions/ \\\\\n",
        "[4] **Problem solving patterns** : https://hackernoon.com/14-patterns-to-ace-any-coding-interview-question-c5bb3357f6ed"
      ],
      "metadata": {
        "id": "VKvm6yNckNqr"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Arrays \n",
        "* **What** : *Contigious area of memory consisting of equal size(type) of elements*\n",
        "* Two types:\n",
        "  1. *Static* - Fixed length container containing n elements indexable from [0,n-1]\n",
        "    * **Why?**\n",
        "      * Storing and accessing sequential data\n",
        "      * Temp storage \n",
        "    * **Speciality** \n",
        "      * **Constant time access**\n",
        "       * How?\n",
        "        * Arrays are indexable \n",
        "    * Syntax :\n",
        "      * **C** => *arr_type array_name [arraySize]* - `int balance[10]` or ` int balance[] = {1,2,3,4,5,6,7}`\n",
        "      * **Java** => \n",
        "      * **Python**\n",
        "\n",
        "  2. *Dynamic* - Variable size array which grow and shrink in size (underthehood resized using statis array)\n",
        "\n",
        "\n",
        "\n",
        " \n",
        "\n",
        "\n",
        "---\n",
        "Algo Prep : https://www.techinterviewhandbook.org/algorithms/array/ \\\\\n",
        "Leetcode - **Python** : https://neetcode.io/ \\\\\n",
        "Leetcode - **Java** : https://www.youtube.com/watch?v=4oZsPXG9B94&list=PLU_sdQYzUj2keVENTP0a5rdykRSgg9Wp-&index=3 \\\\\n",
        "Leetcode - **C** : \n",
        "\n",
        "---"
      ],
      "metadata": {
        "id": "bhvcdM9kkQtl"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Complexity "
      ],
      "metadata": {
        "id": "0stU1q6qHwnw"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Notes**:\n",
        "\n",
        "* Constant access because arrays are indexable \n",
        "* Insert, delete and append not applicable to static array as its fixed size.\n",
        "* Insert and Delete in dynamic array can take linear time in the worst case scenario of excceding the size of static array \n",
        "* Append operation in dynamic array takes constant time as its negligeble. "
      ],
      "metadata": {
        "id": "2HEd94m4JE7h"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "import pandas as pd\n",
        "import numpy as np\n",
        "\n",
        "df = pd.DataFrame({'Operation' : ['Access', 'Search','Insert','Append','Delete'],'Static Array' :['O(1)','O(n)','N/A','N/A','N/A'],'Dynamic Array': ['O(1)','O(n)','O(n)','O(1)','O(n)']})\n",
        "df"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 206
        },
        "id": "m5XgcYmfGQog",
        "outputId": "50d972b0-d611-4ec3-8334-e1eaec121064"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "  Operation Static Array Dynamic Array\n",
              "0    Access         O(1)          O(1)\n",
              "1    Search         O(n)          O(n)\n",
              "2    Insert          N/A          O(n)\n",
              "3    Append          N/A          O(1)\n",
              "4    Delete          N/A          O(n)"
            ],
            "text/html": [
              "\n",
              "  <div id=\"df-5b8859b3-d432-4c2d-879a-997dd0496649\">\n",
              "    <div class=\"colab-df-container\">\n",
              "      <div>\n",
              "<style scoped>\n",
              "    .dataframe tbody tr th:only-of-type {\n",
              "        vertical-align: middle;\n",
              "    }\n",
              "\n",
              "    .dataframe tbody tr th {\n",
              "        vertical-align: top;\n",
              "    }\n",
              "\n",
              "    .dataframe thead th {\n",
              "        text-align: right;\n",
              "    }\n",
              "</style>\n",
              "<table border=\"1\" class=\"dataframe\">\n",
              "  <thead>\n",
              "    <tr style=\"text-align: right;\">\n",
              "      <th></th>\n",
              "      <th>Operation</th>\n",
              "      <th>Static Array</th>\n",
              "      <th>Dynamic Array</th>\n",
              "    </tr>\n",
              "  </thead>\n",
              "  <tbody>\n",
              "    <tr>\n",
              "      <th>0</th>\n",
              "      <td>Access</td>\n",
              "      <td>O(1)</td>\n",
              "      <td>O(1)</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>1</th>\n",
              "      <td>Search</td>\n",
              "      <td>O(n)</td>\n",
              "      <td>O(n)</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>2</th>\n",
              "      <td>Insert</td>\n",
              "      <td>N/A</td>\n",
              "      <td>O(n)</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>3</th>\n",
              "      <td>Append</td>\n",
              "      <td>N/A</td>\n",
              "      <td>O(1)</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>4</th>\n",
              "      <td>Delete</td>\n",
              "      <td>N/A</td>\n",
              "      <td>O(n)</td>\n",
              "    </tr>\n",
              "  </tbody>\n",
              "</table>\n",
              "</div>\n",
              "      <button class=\"colab-df-convert\" onclick=\"convertToInteractive('df-5b8859b3-d432-4c2d-879a-997dd0496649')\"\n",
              "              title=\"Convert this dataframe to an interactive table.\"\n",
              "              style=\"display:none;\">\n",
              "        \n",
              "  <svg xmlns=\"http://www.w3.org/2000/svg\" height=\"24px\"viewBox=\"0 0 24 24\"\n",
              "       width=\"24px\">\n",
              "    <path d=\"M0 0h24v24H0V0z\" fill=\"none\"/>\n",
              "    <path d=\"M18.56 5.44l.94 2.06.94-2.06 2.06-.94-2.06-.94-.94-2.06-.94 2.06-2.06.94zm-11 1L8.5 8.5l.94-2.06 2.06-.94-2.06-.94L8.5 2.5l-.94 2.06-2.06.94zm10 10l.94 2.06.94-2.06 2.06-.94-2.06-.94-.94-2.06-.94 2.06-2.06.94z\"/><path d=\"M17.41 7.96l-1.37-1.37c-.4-.4-.92-.59-1.43-.59-.52 0-1.04.2-1.43.59L10.3 9.45l-7.72 7.72c-.78.78-.78 2.05 0 2.83L4 21.41c.39.39.9.59 1.41.59.51 0 1.02-.2 1.41-.59l7.78-7.78 2.81-2.81c.8-.78.8-2.07 0-2.86zM5.41 20L4 18.59l7.72-7.72 1.47 1.35L5.41 20z\"/>\n",
              "  </svg>\n",
              "      </button>\n",
              "      \n",
              "  <style>\n",
              "    .colab-df-container {\n",
              "      display:flex;\n",
              "      flex-wrap:wrap;\n",
              "      gap: 12px;\n",
              "    }\n",
              "\n",
              "    .colab-df-convert {\n",
              "      background-color: #E8F0FE;\n",
              "      border: none;\n",
              "      border-radius: 50%;\n",
              "      cursor: pointer;\n",
              "      display: none;\n",
              "      fill: #1967D2;\n",
              "      height: 32px;\n",
              "      padding: 0 0 0 0;\n",
              "      width: 32px;\n",
              "    }\n",
              "\n",
              "    .colab-df-convert:hover {\n",
              "      background-color: #E2EBFA;\n",
              "      box-shadow: 0px 1px 2px rgba(60, 64, 67, 0.3), 0px 1px 3px 1px rgba(60, 64, 67, 0.15);\n",
              "      fill: #174EA6;\n",
              "    }\n",
              "\n",
              "    [theme=dark] .colab-df-convert {\n",
              "      background-color: #3B4455;\n",
              "      fill: #D2E3FC;\n",
              "    }\n",
              "\n",
              "    [theme=dark] .colab-df-convert:hover {\n",
              "      background-color: #434B5C;\n",
              "      box-shadow: 0px 1px 3px 1px rgba(0, 0, 0, 0.15);\n",
              "      filter: drop-shadow(0px 1px 2px rgba(0, 0, 0, 0.3));\n",
              "      fill: #FFFFFF;\n",
              "    }\n",
              "  </style>\n",
              "\n",
              "      <script>\n",
              "        const buttonEl =\n",
              "          document.querySelector('#df-5b8859b3-d432-4c2d-879a-997dd0496649 button.colab-df-convert');\n",
              "        buttonEl.style.display =\n",
              "          google.colab.kernel.accessAllowed ? 'block' : 'none';\n",
              "\n",
              "        async function convertToInteractive(key) {\n",
              "          const element = document.querySelector('#df-5b8859b3-d432-4c2d-879a-997dd0496649');\n",
              "          const dataTable =\n",
              "            await google.colab.kernel.invokeFunction('convertToInteractive',\n",
              "                                                     [key], {});\n",
              "          if (!dataTable) return;\n",
              "\n",
              "          const docLinkHtml = 'Like what you see? Visit the ' +\n",
              "            '<a target=\"_blank\" href=https://colab.research.google.com/notebooks/data_table.ipynb>data table notebook</a>'\n",
              "            + ' to learn more about interactive tables.';\n",
              "          element.innerHTML = '';\n",
              "          dataTable['output_type'] = 'display_data';\n",
              "          await google.colab.output.renderOutput(dataTable, element);\n",
              "          const docLink = document.createElement('div');\n",
              "          docLink.innerHTML = docLinkHtml;\n",
              "          element.appendChild(docLink);\n",
              "        }\n",
              "      </script>\n",
              "    </div>\n",
              "  </div>\n",
              "  "
            ]
          },
          "metadata": {},
          "execution_count": 3
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Contains Duplicate : https://leetcode.com/problems/contains-duplicate/\n",
        "\n",
        "```\n",
        "Input: nums = [1,2,3,1]\n",
        "Output: true\n",
        "```\n",
        "\n",
        "**Idea: Use Hashset** "
      ],
      "metadata": {
        "id": "GPySM8OSojSr"
      }
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        },
        "id": "KUMcSIfXifJz",
        "outputId": "60e7f0cd-adea-406f-afba-3960ede621d6"
      },
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "''"
            ],
            "application/vnd.google.colaboratory.intrinsic+json": {
              "type": "string"
            }
          },
          "metadata": {},
          "execution_count": 17
        }
      ],
      "source": [
        "class Solution:\n",
        "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
        "        hashset = set()\n",
        "\n",
        "        for n in nums:\n",
        "            if n in hashset:\n",
        "                return True\n",
        "            hashset.add(n)\n",
        "        return False"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Valid Anagram : https://leetcode.com/problems/valid-anagram/\n",
        "\n",
        "```\n",
        "Input: s = \"anagram\", t = \"nagaram\"\n",
        "Output: true\n",
        "```\n",
        "\n",
        "**Idea: Use the counts and compare two strings** "
      ],
      "metadata": {
        "id": "0dINFFaYc0wk"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "from collections import Counter\n",
        "\n",
        "class Solution:\n",
        "  def isAnagram(self, s :str, t:str) -> bool:\n",
        "    \n",
        "    s1 = Counter(s)\n",
        "    s2 = Counter(t)\n",
        "\n",
        "    if s1==s2:\n",
        "      print(True)\n",
        "    else:\n",
        "      print(False)"
      ],
      "metadata": {
        "id": "phZc8HL-UFZL"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Optimized approach:\n",
        "\n",
        "* Using Dictionary"
      ],
      "metadata": {
        "id": "8AZiOqm_22N4"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "s = \"anagram\"\n",
        "t = \"nagaram\"\n",
        "\n",
        "if len(s) != len(t):\n",
        "  print(False)\n",
        "\n",
        "countS= {}\n",
        "countT = {}\n",
        "\n",
        "for i in range(len(s)):\n",
        "  countS[s[i]] = 1+ countS.get(s[i],0)\n",
        "  countT[t[i]] = 1+ countT.get(t[i],0)\n",
        "\n",
        "print(countS == countT)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "4_47CNGn206T",
        "outputId": "0ba7516c-ea53-49ed-e6ec-cc93890d0631"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "True\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Two sum :https://leetcode.com/problems/two-sum/submissions/\n",
        "\n",
        "```\n",
        "Input: nums = [2,7,11,15], target = 9\n",
        "Output: [0,1]\n",
        "Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].\n",
        "```"
      ],
      "metadata": {
        "id": "yZabfo_o6X4E"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### Naive \n",
        "\n",
        "Runtime : O(n^2)"
      ],
      "metadata": {
        "id": "KgGrCpzx6kOQ"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "%%timeit\n",
        "\n",
        "class Solution:\n",
        "  def twoSum(self, nums, target):\n",
        "        for i in range(0,len(nums)):\n",
        "            for j in range(i+1,len(nums)):\n",
        "                if nums[i]+nums[j] ==  target:\n",
        "                    return[i,j]"
      ],
      "metadata": {
        "id": "YH8JB_koUb2b",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "01572dc0-6da2-4d6e-89f5-c59c4cb35bbc"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "7.88 µs ± 115 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### Optimized \n",
        "\n",
        "Runtime: O(n)\n",
        "\n",
        "**Idea : Use hashmap to check values and index and check if the reamining sum(`target - array[i]`) present in hashmap or else add**.\n",
        "  * Decrease the lookup time(linear)  \n",
        "\n",
        "Algorithm:\n",
        "  1. Create a hashmap of values and index out of array (array_value :index).\n",
        "    * Reduce the number of checks by using  **hashmap*\n",
        "  2. Calculate the remaining sum.\n",
        "    * Remaining sum = target - array[i]\n",
        "  3. Check if the remaining sum in hashmap[values] \n",
        "    * If remaining sum is present in hashmap, return the index of current index of array and value in the hashmap "
      ],
      "metadata": {
        "id": "vgAkUU_f8nOV"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "%%timeit\n",
        "\n",
        "class Solution:\n",
        "  def twoSum(self, nums, target):\n",
        "    prevMap = {}\n",
        "    for i, n in enumerate(nums):\n",
        "      diff = target - n\n",
        "      if diff in prevMap:\n",
        "        return [prevMap[diff],i]\n",
        "      prevMap[n] = i"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "LQIfHfy87LNX",
        "outputId": "2527c4e5-d5eb-4c81-8535-889fa0e59975"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "8.91 µs ± 2.13 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Group Anagrams"
      ],
      "metadata": {
        "id": "Q4tzKEaQQFb6"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "```\n",
        "Input: strs = [\"eat\",\"tea\",\"tan\",\"ate\",\"nat\",\"bat\"]\n",
        "Output: [[\"bat\"],[\"nat\",\"tan\"],[\"ate\",\"eat\",\"tea\"]]\n",
        "```\n",
        "\n",
        "**Idea : Create a hashmap of 26 letters (count:tuple(anagram)) and append to the anagram based on count**\n",
        "  * E.g.:\n",
        "    * 1a,....1e,...,1t..0z: (eat,ate,tea)\n",
        "    * 1a,....,1t,....,1n.. 0z: (tan,nat)\n",
        "    * 1a,1b,....1t....0z : (bat)\n",
        "  \n",
        "  * **Use Ascii values** and subtract from ascii value of a to fit it in 26 array\n",
        "    * E.g. **To fit 80 - 106 in 0 - 26**:\n",
        "      * a = 80 (Aciivalue) -> 80-80\n",
        "      * b = 81 (Aciivalue) -> 81-80\n",
        "      ..\n",
        "\n",
        "  * Trick:\n",
        "    * As tje strings only contain a-z (26 characters), create a 26 array and  \n",
        "\n",
        "\n",
        "* Ideas :\n",
        "  * Sorting anagram leads to same string."
      ],
      "metadata": {
        "id": "YEhpQx2TTvSm"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# %%timeit\n",
        "\n",
        "from collections import defaultdict\n",
        "\n",
        "strs = [\"eat\",\"tea\",\"tan\",\"ate\",\"nat\",\"bat\"]\n",
        "ans = defaultdict(list)\n",
        "\n",
        "for s in strs:\n",
        "  count = [0] * 26\n",
        "  for c in s:\n",
        "    count[ord(c) - ord('a')] += 1\n",
        "  ans[tuple(count)].append(s)\n",
        "print(ans)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "M9KPxj8jQUXa",
        "outputId": "85d5ec16-870a-40a5-e505-a4afadf705fd"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "defaultdict(<class 'list'>, {(1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0): ['eat', 'tea', 'ate'], (1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0): ['tan', 'nat'], (1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0): ['bat']})\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "print(ans.values())"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "XpR0GAToKN8v",
        "outputId": "4808d0fe-8a89-4ec3-fbaa-f74b7fc3ad38"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "dict_values([['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']])\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Top K Frequent elements \n",
        "\n",
        "```\n",
        "Input: nums = [1,1,1,2,2,3], k = 2\n",
        "Output: [1,2]\n",
        "```"
      ],
      "metadata": {
        "id": "G4D5DhSpkuPk"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "nums = [1,1,1,2,2,3]\n",
        "k = 2"
      ],
      "metadata": {
        "id": "8IVuffBnqHvs"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Approach using Counter and most common(heapq.nlargest)\n",
        "\n",
        "* **Complexity** : `O(k logn)`\n",
        "  * k - Heapify k elements \n",
        "  * logn - to sort \n"
      ],
      "metadata": {
        "id": "t6cp8tR0pgQ1"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "from collections import Counter\n",
        "\n",
        "def topKFrequent(nums,k):\n",
        "  most_common_elements = [ele for ele, count in Counter(nums).most_common(k)]\n",
        "  return most_common_elements"
      ],
      "metadata": {
        "id": "cbwBcLWNksUZ"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Naive approach \n",
        "\n",
        "* Sorted algorithm in python : Tim sort \n",
        "  * Special variation of  merge sort Merge sort\n",
        "  * Time complexity : O(nlogn) "
      ],
      "metadata": {
        "id": "xyx8uIdDN1xE"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "dic = {}\n",
        "\n",
        "for i in nums:\n",
        "  if i in dic:\n",
        "    dic[i] += 1\n",
        "  else:\n",
        "    dic[i] = 1"
      ],
      "metadata": {
        "id": "uy270Alh1MPS"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "sortedDict = {k:v for k,v in sorted(dic.items(), key = lambda item : item[1])}"
      ],
      "metadata": {
        "id": "O44nm4eu0z9N"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "[sortedDict[i] for i in list(sortedDict)[:k]]"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "QD7J22UO7_i6",
        "outputId": "ff2bcb3c-2068-45cc-e746-6e12174c32c1"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[1, 2]"
            ]
          },
          "metadata": {},
          "execution_count": 38
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Optimized approach :\n",
        "\n",
        "* Use variation of bucket sort \n",
        "\n",
        "Algorithm :\n",
        "  1. Create value count dictionary.\n",
        "  2. Create count (ascending order) and value arra of length n (number of elements in array).\n",
        "    * ```\n",
        "      |0|1|2|3|4|5|6| i(count)\n",
        "      |0|3|2|1|0|0|0| values\n",
        "      ```\n",
        "    * If more than one value occurs n times, add it as an array \n",
        "        * E.g.  [2,3] - 3  \n",
        "  3. Start popping k elements from right\n",
        "\n",
        "**Complexity**: `O(n)` - Iterating over n elements"
      ],
      "metadata": {
        "id": "I__45sviN4Ya"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "counts = {}\n",
        "\n",
        "for n in nums:\n",
        "  counts[n] = 1+ counts.get(n,0)"
      ],
      "metadata": {
        "id": "8tHSjJ5fN6Y8"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "counts"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "xmOjsnlfSRXs",
        "outputId": "403932d3-6788-4d8d-f776-07dd3646c528"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "{1: 3, 2: 2, 3: 1}"
            ]
          },
          "metadata": {},
          "execution_count": 16
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "req = [[] for i in range(len(nums)+1)]\n",
        "\n",
        "for n, c in counts.items():\n",
        "  req[c].append(n)\n",
        "\n",
        "print(req)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "-n4Os8WeOKJh",
        "outputId": "d809c4f0-85a0-44a1-e0b4-ca4f577f40a3"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[[], [3], [2], [1], [], [], []]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "res = []\n",
        "for i in range(len(req) -1, 0,-1):\n",
        "  for n in req[i]:\n",
        "    print(n)\n",
        "    res.append(n)\n",
        "    if len(res) == k:\n",
        "      print(res)"
      ],
      "metadata": {
        "id": "SsTyUvfCOwdq"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Priority Queue Implementation "
      ],
      "metadata": {
        "id": "wzZzM4rJk7ch"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "from queue import PriorityQueue\n",
        "q = PriorityQueue()"
      ],
      "metadata": {
        "id": "otCCWwWNk--J"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "counts = {}\n",
        "\n",
        "for n in nums:\n",
        "  counts[n] = 1+ counts.get(n,0)"
      ],
      "metadata": {
        "id": "oYJ1Fxfal-EK"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "counts"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "tac6JOoMmFOu",
        "outputId": "014c6d5a-e742-483b-bf17-946f1254901b"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "{1: 3, 2: 2, 3: 1}"
            ]
          },
          "metadata": {},
          "execution_count": 59
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "for k,v in counts.items():\n",
        "  q.put(v,k)"
      ],
      "metadata": {
        "id": "6aneA2MolB-W"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "[q.get() for i in range(1,k)] "
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "NLWkkjd3rysG",
        "outputId": "99f74d72-85b5-4303-f0cf-23724d4078f8"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[1, 2]"
            ]
          },
          "metadata": {},
          "execution_count": 61
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Product of Array except Self\n",
        "\n",
        "```\n",
        "Input: nums = [1,2,3,4]\n",
        "Output: [24,12,8,6]\n",
        "```"
      ],
      "metadata": {
        "id": "0Lh3e4yQvLjl"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Naive Approach : \n",
        "\n",
        "* Doesn't work for 0,0\n",
        "* Cartesian product\n",
        "  * Time complexity : `O(n^2)`"
      ],
      "metadata": {
        "id": "KaRhDaMQ56G9"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# nums = [1,2,3,4]\n",
        "# nums = [-1,1,0,-3,3]\n",
        "nums = [0,4,0]"
      ],
      "metadata": {
        "id": "i9Vhlxy0v1FL"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "[*itertools.product(nums,repeat =2)]"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "V5ROMHz1hYrM",
        "outputId": "cdd43a05-505d-4504-c38e-e144ad8f690e"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[(0, 0), (0, 4), (0, 0), (4, 0), (4, 4), (4, 0), (0, 0), (0, 4), (0, 0)]"
            ]
          },
          "metadata": {},
          "execution_count": 180
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "counts = {}\n",
        "import itertools\n",
        "\n",
        "for n1,n2 in [*itertools.product(nums,repeat =2)]:\n",
        "  if len(nums) ==2 and nums[0] == nums[1]:\n",
        "    print([n1,n2])\n",
        "    break\n",
        "  elif n1 != n2:\n",
        "    print(n1,n2)\n",
        "    counts[n1] = n2 * counts.get(n1,1)"
      ],
      "metadata": {
        "id": "8GCu6pQZyt82"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "counts"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "69Sca0EriOHv",
        "outputId": "d83b0543-aa23-4049-ce26-d5dfd293a3de"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "{0: 16, 4: 0}"
            ]
          },
          "metadata": {},
          "execution_count": 182
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "print(counts.values())"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "XtSrRDHm262l",
        "outputId": "1d7a34a5-a62c-42b5-d75a-8f2eebaaf9c6"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "dict_values([16, 0])\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Optimized approach\n",
        "\n",
        "Product array :\n",
        "  * Product of each consecutive elements except itself.\n",
        "\n",
        "Algorithm:\n",
        "\n",
        "1. Take postfix and prefix array \n",
        "  * Postfix : Product array elements from the current position\n",
        "  * Prefix : Product array elements before the current position \n",
        "2. Multiply the postfix and prefix elements and store it in the current position of result array.\n",
        "\n",
        "Complexity : O(n) - No extra space needed "
      ],
      "metadata": {
        "id": "acgOjelY-olC"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "res = [1] * (len(nums))"
      ],
      "metadata": {
        "id": "tZyTJduTvSHX"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "prefix = 1\n",
        "for i in range(len(nums)):\n",
        "  res[i] = prefix\n",
        "  prefix *= nums[i]\n",
        "\n",
        "postfix = 1\n",
        "for i in range(len(nums)-1,-1,-1):\n",
        "  res[i] *= postfix\n",
        "  postfix *= nums[i]\n",
        "\n",
        "print(res) "
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "niuCXK96jRQD",
        "outputId": "88f9cf74-7bd2-4f8c-8a9b-c2c7c4ff9e50"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[0, 0, 0]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Encode decode\n",
        "\n",
        "Encode and decode string without storing the state variable \n",
        "  * String can contain any character \n",
        "  * Should not store the intermediate variable \n",
        "\n",
        "* E.g.:\n",
        "  * Encode = ['PyCharm','is','good']\n",
        "  * Decode = ['PyCharm','is','good']\n",
        "    * Possible encoding = ['7#PyCharm2#is4#good']"
      ],
      "metadata": {
        "id": "qptqa7kP-cNE"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def encode(words):\n",
        "  res = \"\"\n",
        "  for word in words:\n",
        "    res += len(str(word))+\"#\"+word\n",
        "\n",
        "def decode(words):\n",
        "  decode, i = [],0\n",
        "  while i <= len(words):\n",
        "    i = j\n",
        "    while words[j] != \"#\":\n",
        "      j = j+1\n",
        "      length = int(words[i:j])\n",
        "\n",
        "      decode.append(words[j+1 : j+1+length])\n",
        "      i = j+1+length"
      ],
      "metadata": {
        "id": "cCM2b7dJ-bbQ"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Longest Consecutive Sequence\n",
        "\n",
        "```\n",
        "Input: nums = [100,4,200,1,3,2]\n",
        "Output: 4\n",
        "Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.\n",
        "```"
      ],
      "metadata": {
        "id": "3ufj6-BxDB3g"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Solution:\n",
        "\n",
        "* For each number, check if its the start of the sequence.\n",
        "  * If it doesnot have a left neighbor (n-1) then its a start of a sequence.\n",
        "* For all n+1 elements from the start sequene in the set, add it to a list.\n",
        "\n",
        "\n",
        "**Catch**:\n",
        "  * Create a `set` \n",
        "  * Check for the start sequence  \n",
        "  * Check if n+1 exists using the `in` operator.\n"
      ],
      "metadata": {
        "id": "yFnRyIlxDwV6"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "nums = [101,102,103,7,4,9]"
      ],
      "metadata": {
        "id": "VO7UshnBPn-O"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "numSet = set(nums)\n",
        "longest = 0\n",
        "\n",
        "for n in numSet:\n",
        "  if n-1 not in numSet:\n",
        "    length = 1\n",
        "    while (n+ length) in numSet:\n",
        "      length += 1\n",
        "    longest = max(length,longest)\n",
        "\n",
        "print(longest)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "0hNofXyfDBeF",
        "outputId": "aa47bbc4-c527-47dd-be11-cb40b610ef7f"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "3\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Two pointer\n",
        "\n",
        "\n",
        "* Two pointer one pointing to the head another to tail, iterate from left and right until some condition is met.\n",
        "\n"
      ],
      "metadata": {
        "id": "bHeQ0Nj3Sxga"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Valid Palindrome\n",
        "\n",
        "Link : https://leetcode.com/problems/valid-palindrome/"
      ],
      "metadata": {
        "id": "RPxzoOTJS0MB"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.\n",
        "\n",
        "```\n",
        "Input: s = \"A man, a plan, a canal: Panama\"\n",
        "Output: true\n",
        "Explanation: \"amanaplanacanalpanama\" is a palindrome.\n",
        "\n",
        "```"
      ],
      "metadata": {
        "id": "1TtYYm-xTbKT"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "s = \"A man, a plan, a canal: Panama\""
      ],
      "metadata": {
        "id": "QSMS6ceVS3hy"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "r = \"race a car\""
      ],
      "metadata": {
        "id": "_MXa4E4RaISy"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "t = \" \""
      ],
      "metadata": {
        "id": "1DsE5800akKQ"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def is_pal(pre_pro):\n",
        "  pre_pro = (''.join(e for e in pre_pro if e.isalnum())).lower()\n",
        "  pre_pro_len = len(pre_pro)\n",
        "  \n",
        "  if pre_pro_len > 0:\n",
        "    for x in range(pre_pro_len):\n",
        "      if pre_pro[x] == pre_pro[(pre_pro_len-1)-x]:\n",
        "        continue\n",
        "      else:\n",
        "        return False\n",
        "  return True"
      ],
      "metadata": {
        "id": "dmhPpu4IUTTX"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "is_pal(t), is_pal(s), is_pal(r)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "4HGJYeX5Zwtm",
        "outputId": "2921580d-d3bb-44d2-8b27-edddea1055c0"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "(True, True, False)"
            ]
          },
          "metadata": {},
          "execution_count": 125
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Complexity : `O(n)`"
      ],
      "metadata": {
        "id": "zl-KS7sMclkl"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Neetcode-approach**"
      ],
      "metadata": {
        "id": "Y2Cb6-rZca8C"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def alphanum(s):\n",
        "  return (\n",
        "      ord(\"A\") <= ord(s) <= ord(\"z\")\n",
        "      or ord(\"a\") <= ord(s) <= ord(\"z\")\n",
        "      or ord(\"0\") <= ord(s) <= ord(\"9\")\n",
        "  )"
      ],
      "metadata": {
        "id": "tmtRm4hfchz5"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def ispalindrome(pal_str):\n",
        "  l, r = 0, len(pal_str) -1\n",
        "  while l < r:\n",
        "      while l < r and not alphanum(s[l]):\n",
        "          l += 1\n",
        "      while l < r and not alphanum(s[r]):\n",
        "          r -= 1\n",
        "      if s[l].lower() != s[r].lower():\n",
        "            return False\n",
        "      l += 1\n",
        "      r -= 1\n",
        "  return True"
      ],
      "metadata": {
        "id": "xte5XYE2dJiM"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "## 3Sum"
      ],
      "metadata": {
        "id": "tljZd6A5q0On"
      }
    },
    {
      "cell_type": "markdown",
      "source": [],
      "metadata": {
        "id": "qj-Zb984t9CC"
      }
    },
    {
      "cell_type": "code",
      "source": [],
      "metadata": {
        "id": "X-BRlDJrsjg2"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Key findings"
      ],
      "metadata": {
        "id": "FsAzAsKGznah"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Use `set` ds for membership check and to avoid duplicates. "
      ],
      "metadata": {
        "id": "OjH8ED1i00kt"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Duplicates:\n",
        "\n",
        "```\n",
        "for n in nums:\n",
        "  if n in hashset:\n",
        "    return True\n",
        "  hashset.add(n)\n",
        "return false\n",
        "```"
      ],
      "metadata": {
        "id": "MHeoaoD-1d_6"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Membership"
      ],
      "metadata": {
        "id": "-BkUFQIY2O2B"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "%timeit 'a' in ['a','b','c'] # List"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "TCQE6_NX0cRv",
        "outputId": "cd3b4429-1c4c-4264-b967-3663ed689636"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "34 ns ± 0.719 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "%timeit 'a' in ('a','b','c') # Tuple"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "rShe5aus1-N7",
        "outputId": "3cf1909c-aa8d-41ed-c597-95265b38d0c6"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "35.9 ns ± 6.04 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "%timeit 'a' in {'a','b','c'} # Set"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "UNJO1vlP2CcW",
        "outputId": "92ae12c2-b31a-4384-e8bf-3f34c7be22b2"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "36.7 ns ± 0.451 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Sorting dictionary based on values "
      ],
      "metadata": {
        "id": "UkfuGrFNMZBL"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "```\n",
        "{k:v, k,v in sorted(dic.items(), key = lambda item : item[1])}\n",
        "```\n",
        "\n"
      ],
      "metadata": {
        "id": "_hcXYqUzNZ5i"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Iterating from last "
      ],
      "metadata": {
        "id": "kO8FIZdNOHMd"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "\n",
        "\n",
        "Last :\n",
        "\n",
        "```\n",
        "for i in range(len(list) -1, 0,-1) #for i in range(star, end (not included), -1)\n",
        "```\n",
        "\n"
      ],
      "metadata": {
        "id": "efSUV3z6OKvv"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "nums = [1,4,2,8]\n",
        "\n",
        "for i in range(len(nums)-1,-1,-1):\n",
        "  print(nums[i])"
      ],
      "metadata": {
        "id": "Z45xUQq-OfHb",
        "outputId": "e225aa8f-c840-4184-c4ac-19252b9ec756",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "8\n",
            "2\n",
            "4\n",
            "1\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "for i in range(len(nums) -1, 0,-1):\n",
        "    print(nums[i])"
      ],
      "metadata": {
        "id": "LQgSfbMGOtvV",
        "outputId": "91f1bdef-67d6-4b69-a7de-35956d5c6f67",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "8\n",
            "2\n",
            "4\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Top k  frequent elements using counter and most common "
      ],
      "metadata": {
        "id": "nFRPT8-xQb0S"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "\n",
        "```\n",
        "from collections import Counter\n",
        "\n",
        "most_common_elements = [ele for ele, count in Counter(nums).most_common(k)]\n",
        "```"
      ],
      "metadata": {
        "id": "1ihl8b5XQl2R"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Value count dictionary"
      ],
      "metadata": {
        "id": "0Z50FoXWzp8D"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "\n",
        "\n",
        "```\n",
        "nums = [1,2,2,7]\n",
        "counts = {}\n",
        "\n",
        "for n in nums:\n",
        "  counts[n] = 1+ counts.get(n,0)\n",
        "```\n",
        "\n"
      ],
      "metadata": {
        "id": "ChuzjR2q0Sht"
      }
    }
  ]
}