LeetCode.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "LeetCode",
      "provenance": [],
      "collapsed_sections": [],
      "authorship_tag": "ABX9TyMRU+vJppU/luWZ1C4H0oz9",
      "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/gregory-marton/curr/blob/master/LeetCode.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "!pip install ipytest memory_profiler"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "d6uoWMbnOKWu",
        "outputId": "adadd0ed-16c9-41e3-fcb6-f0df527085c3"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Looking in indexes: https://pypi.org/simple, https://us-python.pkg.dev/colab-wheels/public/simple/\n",
            "Requirement already satisfied: ipytest in /usr/local/lib/python3.7/dist-packages (0.12.0)\n",
            "Requirement already satisfied: memory_profiler in /usr/local/lib/python3.7/dist-packages (0.60.0)\n",
            "Requirement already satisfied: packaging in /usr/local/lib/python3.7/dist-packages (from ipytest) (21.3)\n",
            "Requirement already satisfied: pytest>=5.4 in /usr/local/lib/python3.7/dist-packages (from ipytest) (7.1.2)\n",
            "Requirement already satisfied: ipython in /usr/local/lib/python3.7/dist-packages (from ipytest) (5.5.0)\n",
            "Requirement already satisfied: iniconfig in /usr/local/lib/python3.7/dist-packages (from pytest>=5.4->ipytest) (1.1.1)\n",
            "Requirement already satisfied: importlib-metadata>=0.12 in /usr/local/lib/python3.7/dist-packages (from pytest>=5.4->ipytest) (4.11.4)\n",
            "Requirement already satisfied: tomli>=1.0.0 in /usr/local/lib/python3.7/dist-packages (from pytest>=5.4->ipytest) (2.0.1)\n",
            "Requirement already satisfied: py>=1.8.2 in /usr/local/lib/python3.7/dist-packages (from pytest>=5.4->ipytest) (1.11.0)\n",
            "Requirement already satisfied: pluggy<2.0,>=0.12 in /usr/local/lib/python3.7/dist-packages (from pytest>=5.4->ipytest) (1.0.0)\n",
            "Requirement already satisfied: attrs>=19.2.0 in /usr/local/lib/python3.7/dist-packages (from pytest>=5.4->ipytest) (21.4.0)\n",
            "Requirement already satisfied: zipp>=0.5 in /usr/local/lib/python3.7/dist-packages (from importlib-metadata>=0.12->pytest>=5.4->ipytest) (3.8.0)\n",
            "Requirement already satisfied: typing-extensions>=3.6.4 in /usr/local/lib/python3.7/dist-packages (from importlib-metadata>=0.12->pytest>=5.4->ipytest) (4.1.1)\n",
            "Requirement already satisfied: psutil in /usr/local/lib/python3.7/dist-packages (from memory_profiler) (5.4.8)\n",
            "Requirement already satisfied: pexpect in /usr/local/lib/python3.7/dist-packages (from ipython->ipytest) (4.8.0)\n",
            "Requirement already satisfied: pygments in /usr/local/lib/python3.7/dist-packages (from ipython->ipytest) (2.6.1)\n",
            "Requirement already satisfied: traitlets>=4.2 in /usr/local/lib/python3.7/dist-packages (from ipython->ipytest) (5.1.1)\n",
            "Requirement already satisfied: decorator in /usr/local/lib/python3.7/dist-packages (from ipython->ipytest) (4.4.2)\n",
            "Requirement already satisfied: simplegeneric>0.8 in /usr/local/lib/python3.7/dist-packages (from ipython->ipytest) (0.8.1)\n",
            "Requirement already satisfied: setuptools>=18.5 in /usr/local/lib/python3.7/dist-packages (from ipython->ipytest) (57.4.0)\n",
            "Requirement already satisfied: prompt-toolkit<2.0.0,>=1.0.4 in /usr/local/lib/python3.7/dist-packages (from ipython->ipytest) (1.0.18)\n",
            "Requirement already satisfied: pickleshare in /usr/local/lib/python3.7/dist-packages (from ipython->ipytest) (0.7.5)\n",
            "Requirement already satisfied: wcwidth in /usr/local/lib/python3.7/dist-packages (from prompt-toolkit<2.0.0,>=1.0.4->ipython->ipytest) (0.2.5)\n",
            "Requirement already satisfied: six>=1.9.0 in /usr/local/lib/python3.7/dist-packages (from prompt-toolkit<2.0.0,>=1.0.4->ipython->ipytest) (1.15.0)\n",
            "Requirement already satisfied: pyparsing!=3.0.5,>=2.0.2 in /usr/local/lib/python3.7/dist-packages (from packaging->ipytest) (3.0.9)\n",
            "Requirement already satisfied: ptyprocess>=0.5 in /usr/local/lib/python3.7/dist-packages (from pexpect->ipython->ipytest) (0.7.0)\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "import pytest\n",
        "import ipytest\n",
        "ipytest.autoconfig()\n",
        "\n",
        "@pytest.mark.parametrize(\"base,square\", [(1, 1), (2, 4), (-3, 9), (0, 0)])# Add for failure:, (4, 2)])\n",
        "def test_squares(base, square):\n",
        "  assert base ** 2 == square\n",
        "ipytest.run()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Fnm6b5iRTT6K",
        "outputId": "ddb19efe-ac43-417f-a589-e93dd742ac79"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m                                                                                         [100%]\u001b[0m\n",
            "\u001b[32m\u001b[32m\u001b[1m4 passed\u001b[0m\u001b[32m in 0.08s\u001b[0m\u001b[0m\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "<ExitCode.OK: 0>"
            ]
          },
          "metadata": {},
          "execution_count": 2
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.\n",
        "\n",
        "Symbol       Value\n",
        "I             1\n",
        "V             5\n",
        "X             10\n",
        "L             50\n",
        "C             100\n",
        "D             500\n",
        "M             1000\n",
        "For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.\n",
        "\n",
        "Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:\n",
        "\n",
        "I can be placed before V (5) and X (10) to make 4 and 9. \n",
        "X can be placed before L (50) and C (100) to make 40 and 90. \n",
        "C can be placed before D (500) and M (1000) to make 400 and 900.\n",
        "Given a roman numeral, convert it to an integer.\n",
        "\n",
        " \n",
        "\n",
        "Example 1:\n",
        "\n",
        "Input: s = \"III\"\n",
        "Output: 3\n",
        "Explanation: III = 3.\n",
        "Example 2:\n",
        "\n",
        "Input: s = \"LVIII\"\n",
        "Output: 58\n",
        "Explanation: L = 50, V= 5, III = 3.\n",
        "Example 3:\n",
        "\n",
        "Input: s = \"MCMXCIV\"\n",
        "Output: 1994\n",
        "Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.\n",
        " \n",
        "\n",
        "Constraints:\n",
        "\n",
        "1 <= s.length <= 15\n",
        "s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M').\n",
        "It is guaranteed that s is a valid roman numeral in the range [1, 3999]."
      ],
      "metadata": {
        "id": "jpegD1Rg_gIb"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "ROM = {\"I\": 1, \"V\": 5, \"X\": 10, \"L\": 50, \"C\": 100, \"D\": 500, \"M\": 1000, \n",
        "       \"IV\": 4, \"IX\": 9, \"XL\": 40, \"XC\": 90, \"CD\": 400, \"CM\": 900}\n",
        "class HashNoRegexSolution:\n",
        "  def romanToInt(self, s: str) -> int:\n",
        "    total = 0\n",
        "    last_part = None\n",
        "    at = 0\n",
        "    while at < len(s):\n",
        "      if at + 1 < len(s) and s[at : at+2] in ROM:\n",
        "        part = ROM[s[at : at+2]]\n",
        "        at += 2\n",
        "      elif s[at] in ROM:\n",
        "        part = ROM[s[at]]\n",
        "        at += 1\n",
        "      else:\n",
        "        return None # No roman numeral part match at the start.\n",
        "      if last_part is None or part <= last_part:\n",
        "        total += part\n",
        "        last_part = part\n",
        "      else:\n",
        "        return None # IM means neither 1999 nor 1001. It's just not valid.\n",
        "    return total\n",
        "\n",
        "@pytest.mark.parametrize(\n",
        "    \"example,expected\", \n",
        "    [(\"I\", 1),\n",
        "     (\"II\", 2),\n",
        "     (\"IV\", 4),\n",
        "     (\"V\", 5),\n",
        "     (\"MCMXCIX\", 1999),\n",
        "     (\"MMXXII\", 2022),\n",
        "     (\"XM\", None),\n",
        "     (\"IG\", None)])\n",
        "def test_solution(example, expected):\n",
        "  s = HashNoRegexSolution()\n",
        "  assert s.romanToInt(example) == expected\n",
        "ipytest.run()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "4vuUZW8h_jNb",
        "outputId": "197c8291-cdf0-4ccf-da9c-7e627211aac9"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m                                                                                 [100%]\u001b[0m\n",
            "\u001b[32m\u001b[32m\u001b[1m12 passed\u001b[0m\u001b[32m in 0.11s\u001b[0m\u001b[0m\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "<ExitCode.OK: 0>"
            ]
          },
          "metadata": {},
          "execution_count": 3
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "import re\n",
        "ROM = {\"I\": 1, \"V\": 5, \"X\": 10, \"L\": 50, \"C\": 100, \"D\": 500, \"M\": 1000, \n",
        "       \"IV\": 4, \"IX\": 9, \"XL\": 40, \"XC\": 90, \"CD\": 400, \"CM\": 900}\n",
        "REX = re.compile(\"|\".join(sorted(ROM.keys(), key=len, reverse=True)))\n",
        "class CheckingRegexSolution:\n",
        "  def romanToInt(self, s: str) -> int:\n",
        "    total = 0\n",
        "    last_part = None\n",
        "    last_end = 0\n",
        "    for m in re.finditer(REX, s):\n",
        "      (b, e) = m.span()\n",
        "      print(\"s=%s, m=%s (%s, %s), le=%s\" % (s, m.group(), b, e, last_end))\n",
        "      if b != last_end:\n",
        "        return None\n",
        "      last_end = e\n",
        "      val = ROM[m.group()]\n",
        "      print(\"   %s+%s, lv=%s\" % (total, val, last_part))\n",
        "      if last_part is not None and val > last_part:\n",
        "        return None\n",
        "      total += val\n",
        "      last_part = val\n",
        "    if last_end != len(s):\n",
        "      return None\n",
        "    return total\n",
        "\n",
        "@pytest.mark.parametrize(\n",
        "    \"example,expected\", \n",
        "    [(\"I\", 1),\n",
        "     (\"II\", 2),\n",
        "     (\"IV\", 4),\n",
        "     (\"V\", 5),\n",
        "     (\"MCMXCIX\", 1999),\n",
        "     (\"MMXXII\", 2022),\n",
        "     (\"XM\", None),\n",
        "     (\"IG\", None)])\n",
        "def test_solution(example, expected):\n",
        "  s = CheckingRegexSolution()\n",
        "  assert s.romanToInt(example) == expected\n",
        "ipytest.run()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Zkc8GX38Ot63",
        "outputId": "b6727821-daff-48f4-aac8-7e0004a92337"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m                                                                                 [100%]\u001b[0m\n",
            "\u001b[32m\u001b[32m\u001b[1m12 passed\u001b[0m\u001b[32m in 0.12s\u001b[0m\u001b[0m\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "<ExitCode.OK: 0>"
            ]
          },
          "metadata": {},
          "execution_count": 4
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "But the actual problem on leetcode specifies that all inputs will indeed be valid roman numerals, so we don't need any of that checking"
      ],
      "metadata": {
        "id": "HOHaxX7rh8Bc"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "import re\n",
        "ROM = {\"I\": 1, \"V\": 5, \"X\": 10, \"L\": 50, \"C\": 100, \"D\": 500, \"M\": 1000, \n",
        "       \"IV\": 4, \"IX\": 9, \"XL\": 40, \"XC\": 90, \"CD\": 400, \"CM\": 900}\n",
        "REX = re.compile(\"|\".join(sorted(ROM.keys(), key=len, reverse=True)))\n",
        "class UnsafeRegexSolution:\n",
        "  def romanToInt(self, s: str) -> int:\n",
        "    return sum(map(lambda m: ROM[m.group()], re.finditer(REX, s)))\n",
        "\n",
        "@pytest.mark.parametrize(\n",
        "    \"example,expected\", \n",
        "    [(\"I\", 1),\n",
        "     (\"II\", 2),\n",
        "     (\"IV\", 4),\n",
        "     (\"V\", 5),\n",
        "     (\"MCMXCIX\", 1999),\n",
        "     (\"MMXXII\", 2022),\n",
        "     (\"XM\", 1010), ## WRONG!\n",
        "     (\"GIG\", 1)])   ## WRONG!\n",
        "def test_solution(example, expected):\n",
        "  s = UnsafeRegexSolution()\n",
        "  assert s.romanToInt(example) == expected\n",
        "ipytest.run()"
      ],
      "metadata": {
        "id": "vEwPtx3GiDsT",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "cf275571-3137-4591-e51c-2fa7fcf676b9"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m                                                                                 [100%]\u001b[0m\n",
            "\u001b[32m\u001b[32m\u001b[1m12 passed\u001b[0m\u001b[32m in 0.15s\u001b[0m\u001b[0m\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "<ExitCode.OK: 0>"
            ]
          },
          "metadata": {},
          "execution_count": 5
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "For the purpose of testing the performance of the above, let's create a roman numeral generator:"
      ],
      "metadata": {
        "id": "k4y1_mBtMNsG"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "ROMCONV = [(1000, \"M\"), (900, \"CM\"), (500, \"D\"), (400, \"CD\"), (100, \"C\"), (90, \"XC\"),\n",
        "           (50, \"L\"), (40, \"XL\"), (10, \"X\"), (9, \"IX\"), (5, \"V\"), (4, \"IV\"), (1, \"I\")]\n",
        "def intToRoman(i: int) -> str:\n",
        "  # Return the Roman representation for an integer in 0 < i < 4000\n",
        "  if int(i) != i or i <= 0 or i >= 4000:\n",
        "    return None\n",
        "  result = \"\"\n",
        "  for val, rom in ROMCONV:\n",
        "    while val <= i:\n",
        "      result += rom\n",
        "      i -= val\n",
        "  return result\n",
        "@pytest.mark.parametrize(\n",
        "    \"expected,example\", \n",
        "    [(\"I\", 1),\n",
        "     (\"II\", 2),\n",
        "     (\"IV\", 4),\n",
        "     (\"V\", 5),\n",
        "     (\"MCMXCIX\", 1999),\n",
        "     (\"MMXXII\", 2022),\n",
        "     (\"MX\", 1010),\n",
        "     (\"MIX\", 1009)])\n",
        "def test_solution(example, expected):\n",
        "  assert intToRoman(example) == expected\n",
        "ipytest.run()\n",
        "ALLROMS = map(intToRoman, range(1, 4000))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "ff09nAMCMLPH",
        "outputId": "ffe8c287-37d9-4068-8836-4d211bc6faee"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m.\u001b[0m\u001b[32m                                                                                 [100%]\u001b[0m\n",
            "\u001b[32m\u001b[32m\u001b[1m12 passed\u001b[0m\u001b[32m in 0.12s\u001b[0m\u001b[0m\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "%load_ext memory_profiler"
      ],
      "metadata": {
        "id": "ZICycSN1Q2aU"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "And now let's see which variant is more performant."
      ],
      "metadata": {
        "id": "xKzwL10uPOGT"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "%%timeit\n",
        "%%memit\n",
        "for r in ALLROMS:\n",
        "  s = HashNoRegexSolution()\n",
        "  s.romanToInt(r)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "7v_Pb5PqPS63",
        "outputId": "60cd392b-35ef-4c0d-8163-2feb041400d1"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "peak memory: 100.38 MiB, increment: 0.23 MiB\n",
            "peak memory: 100.47 MiB, increment: 0.06 MiB\n",
            "peak memory: 100.47 MiB, increment: 0.00 MiB\n",
            "peak memory: 100.48 MiB, increment: 0.01 MiB\n",
            "peak memory: 100.49 MiB, increment: 0.00 MiB\n",
            "peak memory: 100.50 MiB, increment: 0.00 MiB\n",
            "1 loop, best of 5: 305 ms per loop\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "%%timeit\n",
        "%%memit\n",
        "for r in ALLROMS:\n",
        "  s = CheckingRegexSolution()\n",
        "  s.romanToInt(r)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "PohvxR2XQVSc",
        "outputId": "304a62a4-b448-4ad7-b0b2-73bba0a62028"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "peak memory: 166.02 MiB, increment: 0.11 MiB\n",
            "peak memory: 166.04 MiB, increment: 0.02 MiB\n",
            "peak memory: 166.11 MiB, increment: 0.08 MiB\n",
            "peak memory: 166.11 MiB, increment: 0.00 MiB\n",
            "peak memory: 166.11 MiB, increment: 0.00 MiB\n",
            "peak memory: 166.11 MiB, increment: 0.00 MiB\n",
            "1 loop, best of 5: 349 ms per loop\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "%%timeit\n",
        "%%memit\n",
        "for r in ALLROMS:\n",
        "  s = UnsafeRegexSolution()\n",
        "  s.romanToInt(r)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "1abYhWhaQXfk",
        "outputId": "23a10b2b-3cbe-48ab-e2d9-1c808ec61cdc"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "peak memory: 166.14 MiB, increment: 0.00 MiB\n",
            "peak memory: 166.15 MiB, increment: 0.00 MiB\n",
            "peak memory: 166.15 MiB, increment: 0.00 MiB\n",
            "peak memory: 166.17 MiB, increment: 0.00 MiB\n",
            "peak memory: 166.17 MiB, increment: 0.00 MiB\n",
            "peak memory: 166.17 MiB, increment: 0.00 MiB\n",
            "1 loop, best of 5: 343 ms per loop\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.\n",
        "\n",
        "The overall run time complexity should be O(log (m+n)).\n",
        "\n",
        " \n",
        "\n",
        "Example 1:\n",
        "\n",
        "Input: nums1 = [1,3], nums2 = [2]\n",
        "Output: 2.00000\n",
        "Explanation: merged array = [1,2,3] and median is 2.\n",
        "Example 2:\n",
        "\n",
        "Input: nums1 = [1,2], nums2 = [3,4]\n",
        "Output: 2.50000\n",
        "Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.\n",
        " \n",
        "\n",
        "Constraints:\n",
        "\n",
        "nums1.length == m\n",
        "nums2.length == n\n",
        "0 <= m <= 1000\n",
        "0 <= n <= 1000\n",
        "1 <= m + n <= 2000\n",
        "-106 <= nums1[i], nums2[i] <= 106"
      ],
      "metadata": {
        "id": "35YVLYxuSLQ4"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "376. Wiggle Subsequence\n",
        "Medium\n",
        "\n",
        "3584\n",
        "\n",
        "119\n",
        "\n",
        "Add to List\n",
        "\n",
        "Share\n",
        "A wiggle sequence is a sequence where the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with one element and a sequence with two non-equal elements are trivially wiggle sequences.\n",
        "\n",
        "For example, [1, 7, 4, 9, 2, 5] is a wiggle sequence because the differences (6, -3, 5, -7, 3) alternate between positive and negative.\n",
        "In contrast, [1, 4, 7, 2, 5] and [1, 7, 4, 5, 5] are not wiggle sequences. The first is not because its first two differences are positive, and the second is not because its last difference is zero.\n",
        "A subsequence is obtained by deleting some elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.\n",
        "\n",
        "Given an integer array nums, return the length of the longest wiggle subsequence of nums.\n",
        "\n",
        " \n",
        "\n",
        "Example 1:\n",
        "\n",
        "Input: nums = [1,7,4,9,2,5]\n",
        "Output: 6\n",
        "Explanation: The entire sequence is a wiggle sequence with differences (6, -3, 5, -7, 3).\n",
        "Example 2:\n",
        "\n",
        "Input: nums = [1,17,5,10,13,15,10,5,16,8]\n",
        "Output: 7\n",
        "Explanation: There are several subsequences that achieve this length.\n",
        "One is [1, 17, 10, 13, 10, 16, 8] with differences (16, -7, 3, -3, 6, -8).\n",
        "Example 3:\n",
        "\n",
        "Input: nums = [1,2,3,4,5,6,7,8,9]\n",
        "Output: 2\n",
        " \n",
        "\n",
        "Constraints:\n",
        "\n",
        "1 <= nums.length <= 1000\n",
        "0 <= nums[i] <= 1000\n",
        " \n",
        "\n",
        "Follow up: Could you solve this in O(n) time?"
      ],
      "metadata": {
        "id": "1D6VT5E0SX4e"
      }
    },
    {
      "cell_type": "code",
      "source": [
        ""
      ],
      "metadata": {
        "id": "h746w42ETV-1"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where:\n",
        "\n",
        "'.' Matches any single character.​​​​\n",
        "'*' Matches zero or more of the preceding element.\n",
        "The matching should cover the entire input string (not partial).\n",
        "\n",
        " \n",
        "\n",
        "Example 1:\n",
        "\n",
        "Input: s = \"aa\", p = \"a\"\n",
        "Output: false\n",
        "Explanation: \"a\" does not match the entire string \"aa\".\n",
        "Example 2:\n",
        "\n",
        "Input: s = \"aa\", p = \"a*\"\n",
        "Output: true\n",
        "Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes \"aa\".\n",
        "Example 3:\n",
        "\n",
        "Input: s = \"ab\", p = \".*\"\n",
        "Output: true\n",
        "Explanation: \".*\" means \"zero or more (*) of any character (.)\".\n",
        " \n",
        "\n",
        "Constraints:\n",
        "\n",
        "1 <= s.length <= 20\n",
        "1 <= p.length <= 30\n",
        "s contains only lowercase English letters.\n",
        "p contains only lowercase English letters, '.', and '*'.\n",
        "It is guaranteed for each appearance of the character '*', there will be a previous valid character to match."
      ],
      "metadata": {
        "id": "OQ7pSPl1ShfZ"
      }
    },
    {
      "cell_type": "code",
      "source": [
        ""
      ],
      "metadata": {
        "id": "lcNj4-fETXLQ"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "23. Merge k Sorted Lists\n",
        "Hard\n",
        "\n",
        "12802\n",
        "\n",
        "490\n",
        "\n",
        "Add to List\n",
        "\n",
        "Share\n",
        "You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.\n",
        "\n",
        "Merge all the linked-lists into one sorted linked-list and return it.\n",
        "\n",
        " \n",
        "\n",
        "Example 1:\n",
        "\n",
        "Input: lists = [[1,4,5],[1,3,4],[2,6]]\n",
        "Output: [1,1,2,3,4,4,5,6]\n",
        "Explanation: The linked-lists are:\n",
        "[\n",
        "  1->4->5,\n",
        "  1->3->4,\n",
        "  2->6\n",
        "]\n",
        "merging them into one sorted list:\n",
        "1->1->2->3->4->4->5->6\n",
        "Example 2:\n",
        "\n",
        "Input: lists = []\n",
        "Output: []\n",
        "Example 3:\n",
        "\n",
        "Input: lists = [[]]\n",
        "Output: []\n",
        " \n",
        "\n",
        "Constraints:\n",
        "\n",
        "k == lists.length\n",
        "0 <= k <= 104\n",
        "0 <= lists[i].length <= 500\n",
        "-104 <= lists[i][j] <= 104\n",
        "lists[i] is sorted in ascending order.\n",
        "The sum of lists[i].length will not exceed 104."
      ],
      "metadata": {
        "id": "TUtnScOCSnFw"
      }
    },
    {
      "cell_type": "code",
      "source": [
        ""
      ],
      "metadata": {
        "id": "g8q8KRkhTYM6"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.\n",
        "\n",
        "k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.\n",
        "\n",
        "You may not alter the values in the list's nodes, only nodes themselves may be changed.\n",
        "\n",
        " \n",
        "\n",
        "Example 1:\n",
        "\n",
        "\n",
        "Input: head = [1,2,3,4,5], k = 2\n",
        "Output: [2,1,4,3,5]\n",
        "Example 2:\n",
        "\n",
        "\n",
        "Input: head = [1,2,3,4,5], k = 3\n",
        "Output: [3,2,1,4,5]\n",
        " \n",
        "\n",
        "Constraints:\n",
        "\n",
        "The number of nodes in the list is n.\n",
        "1 <= k <= n <= 5000\n",
        "0 <= Node.val <= 1000\n",
        " \n",
        "\n",
        "Follow-up: Can you solve the problem in O(1) extra memory space?"
      ],
      "metadata": {
        "id": "ywa5_9AwStHn"
      }
    },
    {
      "cell_type": "code",
      "source": [
        ""
      ],
      "metadata": {
        "id": "NJ83lQ_ITZGc"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "30. Substring with Concatenation of All Words\n",
        "Hard\n",
        "\n",
        "2107\n",
        "\n",
        "1908\n",
        "\n",
        "Add to List\n",
        "\n",
        "Share\n",
        "You are given a string s and an array of strings words of the same length. Return all starting indices of substring(s) in s that is a concatenation of each word in words exactly once, in any order, and without any intervening characters.\n",
        "\n",
        "You can return the answer in any order.\n",
        "\n",
        " \n",
        "\n",
        "Example 1:\n",
        "\n",
        "Input: s = \"barfoothefoobarman\", words = [\"foo\",\"bar\"]\n",
        "Output: [0,9]\n",
        "Explanation: Substrings starting at index 0 and 9 are \"barfoo\" and \"foobar\" respectively.\n",
        "The output order does not matter, returning [9,0] is fine too.\n",
        "Example 2:\n",
        "\n",
        "Input: s = \"wordgoodgoodgoodbestword\", words = [\"word\",\"good\",\"best\",\"word\"]\n",
        "Output: []\n",
        "Example 3:\n",
        "\n",
        "Input: s = \"barfoofoobarthefoobarman\", words = [\"bar\",\"foo\",\"the\"]\n",
        "Output: [6,9,12]\n",
        " \n",
        "\n",
        "Constraints:\n",
        "\n",
        "1 <= s.length <= 104\n",
        "s consists of lower-case English letters.\n",
        "1 <= words.length <= 5000\n",
        "1 <= words[i].length <= 30\n",
        "words[i] consists of lower-case English letters."
      ],
      "metadata": {
        "id": "BYgrM1joSzuO"
      }
    },
    {
      "cell_type": "code",
      "source": [
        ""
      ],
      "metadata": {
        "id": "hkL4jHJYTZ6T"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "32. Longest Valid Parentheses\n",
        "Hard\n",
        "\n",
        "8978\n",
        "\n",
        "291\n",
        "\n",
        "Add to List\n",
        "\n",
        "Share\n",
        "Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.\n",
        "\n",
        " \n",
        "\n",
        "Example 1:\n",
        "\n",
        "Input: s = \"(()\"\n",
        "Output: 2\n",
        "Explanation: The longest valid parentheses substring is \"()\".\n",
        "Example 2:\n",
        "\n",
        "Input: s = \")()())\"\n",
        "Output: 4\n",
        "Explanation: The longest valid parentheses substring is \"()()\".\n",
        "Example 3:\n",
        "\n",
        "Input: s = \"\"\n",
        "Output: 0\n",
        " \n",
        "\n",
        "Constraints:\n",
        "\n",
        "0 <= s.length <= 3 * 104\n",
        "s[i] is '(', or ')'."
      ],
      "metadata": {
        "id": "dDCHOe2TS3T8"
      }
    },
    {
      "cell_type": "code",
      "source": [
        ""
      ],
      "metadata": {
        "id": "ckHDyqkrTbQm"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Write a program to solve a Sudoku puzzle by filling the empty cells.\n",
        "\n",
        "A sudoku solution must satisfy all of the following rules:\n",
        "\n",
        "Each of the digits 1-9 must occur exactly once in each row.\n",
        "Each of the digits 1-9 must occur exactly once in each column.\n",
        "Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.\n",
        "The '.' character indicates empty cells.\n",
        "\n",
        " \n",
        "\n",
        "Example 1:\n",
        "\n",
        "\n",
        "Input: board = [[\"5\",\"3\",\".\",\".\",\"7\",\".\",\".\",\".\",\".\"],[\"6\",\".\",\".\",\"1\",\"9\",\"5\",\".\",\".\",\".\"],[\".\",\"9\",\"8\",\".\",\".\",\".\",\".\",\"6\",\".\"],[\"8\",\".\",\".\",\".\",\"6\",\".\",\".\",\".\",\"3\"],[\"4\",\".\",\".\",\"8\",\".\",\"3\",\".\",\".\",\"1\"],[\"7\",\".\",\".\",\".\",\"2\",\".\",\".\",\".\",\"6\"],[\".\",\"6\",\".\",\".\",\".\",\".\",\"2\",\"8\",\".\"],[\".\",\".\",\".\",\"4\",\"1\",\"9\",\".\",\".\",\"5\"],[\".\",\".\",\".\",\".\",\"8\",\".\",\".\",\"7\",\"9\"]]\n",
        "Output: [[\"5\",\"3\",\"4\",\"6\",\"7\",\"8\",\"9\",\"1\",\"2\"],[\"6\",\"7\",\"2\",\"1\",\"9\",\"5\",\"3\",\"4\",\"8\"],[\"1\",\"9\",\"8\",\"3\",\"4\",\"2\",\"5\",\"6\",\"7\"],[\"8\",\"5\",\"9\",\"7\",\"6\",\"1\",\"4\",\"2\",\"3\"],[\"4\",\"2\",\"6\",\"8\",\"5\",\"3\",\"7\",\"9\",\"1\"],[\"7\",\"1\",\"3\",\"9\",\"2\",\"4\",\"8\",\"5\",\"6\"],[\"9\",\"6\",\"1\",\"5\",\"3\",\"7\",\"2\",\"8\",\"4\"],[\"2\",\"8\",\"7\",\"4\",\"1\",\"9\",\"6\",\"3\",\"5\"],[\"3\",\"4\",\"5\",\"2\",\"8\",\"6\",\"1\",\"7\",\"9\"]]\n",
        "Explanation: The input board is shown above and the only valid solution is shown below:\n",
        "\n",
        "\n",
        " \n",
        "\n",
        "Constraints:\n",
        "\n",
        "board.length == 9\n",
        "board[i].length == 9\n",
        "board[i][j] is a digit or '.'.\n",
        "It is guaranteed that the input board has only one solution.\n",
        "Accepted\n",
        "367,969\n",
        "Submissions\n",
        "669,133"
      ],
      "metadata": {
        "id": "ckiXEjyfS86I"
      }
    },
    {
      "cell_type": "code",
      "source": [
        ""
      ],
      "metadata": {
        "id": "jUrji4vtTcWh"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "41. First Missing Positive\n",
        "Hard\n",
        "\n",
        "10264\n",
        "\n",
        "1387\n",
        "\n",
        "Add to List\n",
        "\n",
        "Share\n",
        "Given an unsorted integer array nums, return the smallest missing positive integer.\n",
        "\n",
        "You must implement an algorithm that runs in O(n) time and uses constant extra space.\n",
        "\n",
        " \n",
        "\n",
        "Example 1:\n",
        "\n",
        "Input: nums = [1,2,0]\n",
        "Output: 3\n",
        "Example 2:\n",
        "\n",
        "Input: nums = [3,4,-1,1]\n",
        "Output: 2\n",
        "Example 3:\n",
        "\n",
        "Input: nums = [7,8,9,11,12]\n",
        "Output: 1\n",
        " \n",
        "\n",
        "Constraints:\n",
        "\n",
        "1 <= nums.length <= 5 * 105\n",
        "-231 <= nums[i] <= 231 - 1"
      ],
      "metadata": {
        "id": "zJy1xoLcTAvK"
      }
    },
    {
      "cell_type": "code",
      "source": [
        ""
      ],
      "metadata": {
        "id": "NmI9q2tqTdWh"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "42. Trapping Rain Water\n",
        "Hard\n",
        "\n",
        "19699\n",
        "\n",
        "277\n",
        "\n",
        "Add to List\n",
        "\n",
        "Share\n",
        "Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.\n",
        "\n",
        " \n",
        "\n",
        "Example 1:\n",
        "\n",
        "\n",
        "Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]\n",
        "Output: 6\n",
        "Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.\n",
        "Example 2:\n",
        "\n",
        "Input: height = [4,2,0,3,2,5]\n",
        "Output: 9\n",
        " \n",
        "\n",
        "Constraints:\n",
        "\n",
        "n == height.length\n",
        "1 <= n <= 2 * 104\n",
        "0 <= height[i] <= 105"
      ],
      "metadata": {
        "id": "drsQlEKXTFsF"
      }
    },
    {
      "cell_type": "code",
      "source": [
        ""
      ],
      "metadata": {
        "id": "Ni9JtTQ8TeJH"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "44. Wildcard Matching\n",
        "Hard\n",
        "\n",
        "5036\n",
        "\n",
        "227\n",
        "\n",
        "Add to List\n",
        "\n",
        "Share\n",
        "Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*' where:\n",
        "\n",
        "'?' Matches any single character.\n",
        "'*' Matches any sequence of characters (including the empty sequence).\n",
        "The matching should cover the entire input string (not partial).\n",
        "\n",
        " \n",
        "\n",
        "Example 1:\n",
        "\n",
        "Input: s = \"aa\", p = \"a\"\n",
        "Output: false\n",
        "Explanation: \"a\" does not match the entire string \"aa\".\n",
        "Example 2:\n",
        "\n",
        "Input: s = \"aa\", p = \"*\"\n",
        "Output: true\n",
        "Explanation: '*' matches any sequence.\n",
        "Example 3:\n",
        "\n",
        "Input: s = \"cb\", p = \"?a\"\n",
        "Output: false\n",
        "Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.\n",
        " \n",
        "\n",
        "Constraints:\n",
        "\n",
        "0 <= s.length, p.length <= 2000\n",
        "s contains only lowercase English letters.\n",
        "p contains only lowercase English letters, '?' or '*'."
      ],
      "metadata": {
        "id": "KpF7uPRZTJgy"
      }
    },
    {
      "cell_type": "code",
      "source": [
        ""
      ],
      "metadata": {
        "id": "ZsQDx9DASYvH"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}