{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "3m9T2TG1Idvs"
   },
   "source": [
    "# Range Minimum Query (RMQ) on Google Stock Data - Assignment\n",
    "\n",
    "Your task is to implement two RMQ data structures and compare the results with naive scan.\n",
    "\n",
    "**Data-structures to implement:**\n",
    "1. Sparse Table RMQ - $O(1)$ per query\n",
    "2. Block Decomposition RMQ - $O(n^{1/3})$ per query\n",
    "\n",
    "\n",
    "**Submit:** Complete notebook with working `sparse_rmq()`  and `block_rmq()` query functions.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "vY-tfrXNIdvv",
    "outputId": "c32727f9-d232-45e2-c3bb-f51840fb09e9"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Loaded 4431 Google stock prices\n",
      "Price range: $49.64 to $3025.00\n",
      "Generated 10000 test ranges\n",
      "Sample ranges: [(3505, 3620), (988, 4026), (2012, 3016), (1800, 2372), (3902, 4007)]\n"
     ]
    }
   ],
   "source": [
    "import pandas as pd\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "import time\n",
    "import math\n",
    "import random\n",
    "\n",
    "# Load Google stock data\n",
    "df = pd.read_csv('GOOGLE-stock-price.csv')\n",
    "stock_prices = df['Price'].values.tolist()\n",
    "n = len(stock_prices)\n",
    "\n",
    "print(f\"Loaded {n} Google stock prices\")\n",
    "print(f\"Price range: ${min(stock_prices):.2f} to ${max(stock_prices):.2f}\")\n",
    "\n",
    "# Generate test ranges\n",
    "random.seed(42)\n",
    "test_ranges = []\n",
    "for _ in range(10000):\n",
    "    start = random.randint(n//5, n - 10)\n",
    "    end = random.randint(start+1, n - 1)\n",
    "    test_ranges.append((start, end))\n",
    "\n",
    "print(f\"Generated {len(test_ranges)} test ranges\")\n",
    "print(f\"Sample ranges: {test_ranges[:5]}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "JxKnzlyfIdvw"
   },
   "source": [
    "---\n",
    "\n",
    "# Method 1: Naive Scan RMQ - $O(n)$ per query"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "96g5DTC2Idvw",
    "outputId": "85db6520-1eaf-43a1-90c0-62b6c1d99456"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "=== Naive Scan RMQ ===\n",
      "Results for first 5 ranges:\n",
      "Range [3505, 3620]: Min = $  984.32\n",
      "Range [ 988, 4026]: Min = $  131.39\n",
      "Range [2012, 3016]: Min = $  323.32\n",
      "Range [1800, 2372]: Min = $  267.00\n",
      "Range [3902, 4007]: Min = $ 1056.37\n"
     ]
    }
   ],
   "source": [
    "def naive_rmq(left, right):\n",
    "    return min(stock_prices[left:right+1])\n",
    "\n",
    "print(\"=== Naive Scan RMQ ===\")\n",
    "print(\"Results for first 5 ranges:\")\n",
    "naive_results = []\n",
    "for i in range(n):\n",
    "    left, right = test_ranges[i]\n",
    "    result = naive_rmq(left, right)\n",
    "    naive_results.append(result)\n",
    "    if (i<5):\n",
    "        print(f\"Range [{left:4d}, {right:4d}]: Min = ${result:8.2f}\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "HP_CfFjDIdvw"
   },
   "source": [
    "---\n",
    "\n",
    "# Method 2: Sparse Table RMQ - $O(1)$ per query\n",
    "\n",
    "Build a table where `ST[i][j]` = minimum in range `[i, i + 2^j - 1]`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 241
    },
    "id": "3rYx9T68Idvx",
    "outputId": "6973a3cc-cc98-463d-fb96-d8d5a1068e6e"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "=== Sparse Table RMQ ===\n",
      "Results for first 5 ranges:\n"
     ]
    },
    {
     "ename": "TypeError",
     "evalue": "unsupported format string passed to NoneType.__format__",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "Cell \u001b[0;32mIn[6], line 43\u001b[0m\n\u001b[1;32m     41\u001b[0m     sparse_results\u001b[38;5;241m.\u001b[39mappend(result)\n\u001b[1;32m     42\u001b[0m     \u001b[38;5;28;01mif\u001b[39;00m (i\u001b[38;5;241m<\u001b[39m\u001b[38;5;241m5\u001b[39m):\n\u001b[0;32m---> 43\u001b[0m         \u001b[38;5;28mprint\u001b[39m(\u001b[38;5;124mf\u001b[39m\u001b[38;5;124m\"\u001b[39m\u001b[38;5;124mRange [\u001b[39m\u001b[38;5;132;01m{\u001b[39;00mleft\u001b[38;5;132;01m:\u001b[39;00m\u001b[38;5;124m4d\u001b[39m\u001b[38;5;132;01m}\u001b[39;00m\u001b[38;5;124m, \u001b[39m\u001b[38;5;132;01m{\u001b[39;00mright\u001b[38;5;132;01m:\u001b[39;00m\u001b[38;5;124m4d\u001b[39m\u001b[38;5;132;01m}\u001b[39;00m\u001b[38;5;124m]: Min = $\u001b[39m\u001b[38;5;132;01m{\u001b[39;00mresult\u001b[38;5;132;01m:\u001b[39;00m\u001b[38;5;124m8.2f\u001b[39m\u001b[38;5;132;01m}\u001b[39;00m\u001b[38;5;124m\"\u001b[39m)\n\u001b[1;32m     45\u001b[0m \u001b[38;5;66;03m# Verify correctness\u001b[39;00m\n\u001b[1;32m     46\u001b[0m \u001b[38;5;28;01mif\u001b[39;00m sparse_results \u001b[38;5;241m==\u001b[39m naive_results:\n",
      "\u001b[0;31mTypeError\u001b[0m: unsupported format string passed to NoneType.__format__"
     ]
    }
   ],
   "source": [
    "# Global variables for sparse table\n",
    "ST = []  # Sparse table\n",
    "LOG = []  # Precomputed log values\n",
    "\n",
    "def build_sparse_table():\n",
    "    \"\"\"Build sparse table for range minimum queries\"\"\"\n",
    "    global ST, LOG\n",
    "\n",
    "    k = int(math.log2(n)) + 1\n",
    "    ST = [[0] * k for _ in range(n)]\n",
    "    LOG = [0] * (n + 1)\n",
    "\n",
    "    # Build log table\n",
    "    LOG[1] = 0\n",
    "    for i in range(2, n + 1):\n",
    "        LOG[i] = LOG[i // 2] + 1\n",
    "\n",
    "    # Fill base case: intervals of length 1\n",
    "    for i in range(n):\n",
    "        ST[i][0] = stock_prices[i]\n",
    "\n",
    "    # Fill table using DP\n",
    "    for j in range(1, k):\n",
    "        for i in range(n - (1 << j) + 1):\n",
    "            ST[i][j] = min(ST[i][j-1], ST[i + (1 << (j-1))][j-1])\n",
    "\n",
    "def sparse_rmq(left, right):\n",
    "    \"\"\"Range minimum query in O(1) time\"\"\"\n",
    "    #################################\n",
    "    #    Complete this function     #\n",
    "    #################################\n",
    "\n",
    "print(\"=== Sparse Table RMQ ===\")\n",
    "build_sparse_table()\n",
    "\n",
    "print(\"Results for first 5 ranges:\")\n",
    "sparse_results = []\n",
    "for i in range(n):\n",
    "    left, right = test_ranges[i]\n",
    "    result = sparse_rmq(left, right)\n",
    "    sparse_results.append(result)\n",
    "    if (i<5):\n",
    "        print(f\"Range [{left:4d}, {right:4d}]: Min = ${result:8.2f}\")\n",
    "\n",
    "# Verify correctness\n",
    "if sparse_results == naive_results:\n",
    "    print(\"✓ Correct results\")\n",
    "else:\n",
    "    print(\"✗ Incorrect results\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "41JX7qVRIdvx"
   },
   "source": [
    "---\n",
    "\n",
    "# Method 3: Block Decomposition RMQ - $O(n^{1/2})$ per query\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "id": "Fhn4z5NOIdvx"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "=== Block Decomposition RMQ ===\n",
      "Results for first 5 ranges:\n"
     ]
    },
    {
     "ename": "TypeError",
     "evalue": "unsupported format string passed to NoneType.__format__",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "Cell \u001b[0;32mIn[7], line 29\u001b[0m\n\u001b[1;32m     27\u001b[0m     block_results\u001b[38;5;241m.\u001b[39mappend(result)\n\u001b[1;32m     28\u001b[0m     \u001b[38;5;28;01mif\u001b[39;00m (i\u001b[38;5;241m<\u001b[39m\u001b[38;5;241m5\u001b[39m):\n\u001b[0;32m---> 29\u001b[0m         \u001b[38;5;28mprint\u001b[39m(\u001b[38;5;124mf\u001b[39m\u001b[38;5;124m\"\u001b[39m\u001b[38;5;124mRange [\u001b[39m\u001b[38;5;132;01m{\u001b[39;00mleft\u001b[38;5;132;01m:\u001b[39;00m\u001b[38;5;124m4d\u001b[39m\u001b[38;5;132;01m}\u001b[39;00m\u001b[38;5;124m, \u001b[39m\u001b[38;5;132;01m{\u001b[39;00mright\u001b[38;5;132;01m:\u001b[39;00m\u001b[38;5;124m4d\u001b[39m\u001b[38;5;132;01m}\u001b[39;00m\u001b[38;5;124m]: Min = $\u001b[39m\u001b[38;5;132;01m{\u001b[39;00mresult\u001b[38;5;132;01m:\u001b[39;00m\u001b[38;5;124m8.2f\u001b[39m\u001b[38;5;132;01m}\u001b[39;00m\u001b[38;5;124m\"\u001b[39m)\n\u001b[1;32m     31\u001b[0m \u001b[38;5;66;03m# Verify correctness\u001b[39;00m\n\u001b[1;32m     32\u001b[0m \u001b[38;5;28;01mif\u001b[39;00m block_results \u001b[38;5;241m==\u001b[39m naive_results:\n",
      "\u001b[0;31mTypeError\u001b[0m: unsupported format string passed to NoneType.__format__"
     ]
    }
   ],
   "source": [
    "# Global variables for block decomposition\n",
    "L = int(math.ceil(n ** (1/2)))\n",
    "B = []  # mins of blocks of len L\n",
    "\n",
    "def build_block_decomposition():\n",
    "    global B, L, n\n",
    "    # Precompute B (blocks of L)\n",
    "    B.clear()\n",
    "    for i in range(0, n, L):\n",
    "        B.append(min(stock_prices[i: min(i + L, n)]))\n",
    "\n",
    "def block_rmq(left, right):\n",
    "    \"\"\"Range minimum query in O(n^1/2) time\"\"\"\n",
    "    #################################\n",
    "    #    Complete this function     #\n",
    "    #################################\n",
    "\n",
    "\n",
    "print(\"=== Block Decomposition RMQ ===\")\n",
    "build_block_decomposition()\n",
    "\n",
    "print(\"Results for first 5 ranges:\")\n",
    "block_results = []\n",
    "for i in range(n):\n",
    "    left, right = test_ranges[i]\n",
    "    result = block_rmq(left, right)\n",
    "    block_results.append(result)\n",
    "    if (i<5):\n",
    "        print(f\"Range [{left:4d}, {right:4d}]: Min = ${result:8.2f}\")\n",
    "\n",
    "# Verify correctness\n",
    "if block_results == naive_results:\n",
    "    print(\"✓ Correct results\")\n",
    "else:\n",
    "    print(\"✗ Incorrect results\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "colab": {
   "provenance": []
  },
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}