Calculate Trapping Rain Water.ipynb

{
 "cells": [
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "# Calculating Trapped Rainwater using Pandas\n",
    "When it rains, water naturally accumulates in low-lying areas, forming small pools between elevated terrains. This phenomenon is commonly seen in cities with poor drainage systems, uneven roads, or natural landscapes with hills and valleys. But what if we wanted to quantify exactly how much water gets trapped in such a terrain?\n",
    "\n",
    "This problem, commonly referred to as the \"Trapping Rain Water Problem,\" is a classic coding challenge in algorithm design. It requires us to analyze a 1D elevation map, determine where water can be stored, and compute the total amount of trapped rainwater.\n",
    "\n",
    "In this blog post, I’ll walk you through a Python-based approach using Pandas to efficiently compute trapped rainwater in a given elevation profile. By leveraging cumulative maximum calculations, we can determine the trapped water at each position and sum it up—all with minimal computational overhead.\n",
    "\n",
    "We’ll explore the step-by-step logic behind this solution, from understanding how water accumulates in terrain to implementing an optimized approach using Pandas. By the end, you’ll have a solid grasp of how to tackle this problem in an efficient and elegant way.\n",
    "\n",
    "Let’s dive in!\n",
    "\n",
    "## Problem Statement\n",
    "\n",
    "Given a table `Heights` representing the elevation map, we need to determine how much rainwater can be trapped between the bars in the landscape, considering that each bar has a width of 1 unit.\n",
    "\n",
    "### Table Schema\n",
    "\n",
    "**Heights Table:**\n",
    "\n",
    "| Column Name | Type |\n",
    "|-------------|------|\n",
    "| id          | int  |\n",
    "| height      | int  |\n",
    "\n",
    "- `id` is the primary key (column with unique values) for this table.\n",
    "- The `id` values are in sequential order.\n",
    "- Each row of this table contains an `id` and `height`, representing the elevation at that position.\n",
    "\n",
    "---\n",
    "\n",
    "## Example\n",
    "\n",
    "### **Input**: Heights Table\n",
    "\n",
    "| id  | height |\n",
    "|-----|--------|\n",
    "| 1   | 0      |\n",
    "| 2   | 1      |\n",
    "| 3   | 0      |\n",
    "| 4   | 2      |\n",
    "| 5   | 1      |\n",
    "| 6   | 0      |\n",
    "| 7   | 1      |\n",
    "| 8   | 3      |\n",
    "| 9   | 2      |\n",
    "| 10  | 1      |\n",
    "| 11  | 2      |\n",
    "| 12  | 1      |\n",
    "\n",
    "### **Output**:\n",
    "\n",
    "| total_trapped_water |\n",
    "|---------------------|\n",
    "| 6                   |\n",
    "\n",
    "\n",
    "\n"
   ],
   "id": "119e91da58ad58ce"
  },
  {
   "metadata": {
    "collapsed": true,
    "ExecuteTime": {
     "end_time": "2025-03-14T16:36:02.610191Z",
     "start_time": "2025-03-14T16:36:02.583118Z"
    }
   },
   "cell_type": "code",
   "source": [
    "import pandas as pd\n",
    "\n",
    "data = [[1, 0], [2, 1],\n",
    "        [3, 0], [4, 2],\n",
    "        [5, 1], [6, 0],\n",
    "        [7, 1], [8, 3],\n",
    "        [9, 2], [10, 1],\n",
    "        [11, 2], [12, 1]]\n",
    "heights = pd.DataFrame(data,\n",
    "                       columns=['id', 'height']).astype({\n",
    "                       'id':'Int64', 'height':'Int64'})\n",
    "display(heights)"
   ],
   "id": "initial_id",
   "outputs": [
    {
     "data": {
      "text/plain": [
       "    id  height\n",
       "0    1       0\n",
       "1    2       1\n",
       "2    3       0\n",
       "3    4       2\n",
       "4    5       1\n",
       "5    6       0\n",
       "6    7       1\n",
       "7    8       3\n",
       "8    9       2\n",
       "9   10       1\n",
       "10  11       2\n",
       "11  12       1"
      ],
      "text/html": [
       "<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>id</th>\n",
       "      <th>height</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>3</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>4</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>5</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>6</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>7</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>8</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>9</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>10</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>10</th>\n",
       "      <td>11</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>11</th>\n",
       "      <td>12</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "execution_count": 26
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "Step 1: Sorting the Data by 'id'\n",
    "- This sorts the DataFrame by the 'id' column in ascending order."
   ],
   "id": "2c3230206bad7af3"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-14T16:36:02.669905Z",
     "start_time": "2025-03-14T16:36:02.641443Z"
    }
   },
   "cell_type": "code",
   "source": [
    "heights= heights.sort_values(by='id')\n",
    "display(heights)"
   ],
   "id": "3f9a73d2bc6a3c36",
   "outputs": [
    {
     "data": {
      "text/plain": [
       "    id  height\n",
       "0    1       0\n",
       "1    2       1\n",
       "2    3       0\n",
       "3    4       2\n",
       "4    5       1\n",
       "5    6       0\n",
       "6    7       1\n",
       "7    8       3\n",
       "8    9       2\n",
       "9   10       1\n",
       "10  11       2\n",
       "11  12       1"
      ],
      "text/html": [
       "<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>id</th>\n",
       "      <th>height</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>3</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>4</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>5</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>6</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>7</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>8</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>9</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>10</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>10</th>\n",
       "      <td>11</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>11</th>\n",
       "      <td>12</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "execution_count": 27
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "Step 2: Computing the Left Maximum Height at Each Position\n",
    "- cummax() computes the cumulative maximum from left to right.\n",
    "- This means at each position, it stores the maximum height encountered so far."
   ],
   "id": "4f01cd9c755f154"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-14T16:36:02.754321Z",
     "start_time": "2025-03-14T16:36:02.737626Z"
    }
   },
   "cell_type": "code",
   "source": [
    "heights['left_max'] = heights['height'].cummax()\n",
    "display(heights)"
   ],
   "id": "c97e7fdd7006e96",
   "outputs": [
    {
     "data": {
      "text/plain": [
       "    id  height  left_max\n",
       "0    1       0         0\n",
       "1    2       1         1\n",
       "2    3       0         1\n",
       "3    4       2         2\n",
       "4    5       1         2\n",
       "5    6       0         2\n",
       "6    7       1         2\n",
       "7    8       3         3\n",
       "8    9       2         3\n",
       "9   10       1         3\n",
       "10  11       2         3\n",
       "11  12       1         3"
      ],
      "text/html": [
       "<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>id</th>\n",
       "      <th>height</th>\n",
       "      <th>left_max</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>3</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>4</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>5</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>6</td>\n",
       "      <td>0</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>7</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>8</td>\n",
       "      <td>3</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>9</td>\n",
       "      <td>2</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>10</td>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>10</th>\n",
       "      <td>11</td>\n",
       "      <td>2</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>11</th>\n",
       "      <td>12</td>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "execution_count": 28
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "Step 3: Computing the Right Maximum Height at Each Position\n",
    "- [::-1] reverses the DataFrame to compute the cumulative max from right to left.\n",
    "- .cummax() computes the maximum height encountered from the right.\n",
    "- The array is then reversed back to match the original order."
   ],
   "id": "17c14fe67e232c63"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-14T16:36:02.879630Z",
     "start_time": "2025-03-14T16:36:02.863379Z"
    }
   },
   "cell_type": "code",
   "source": [
    "heights['right_max'] = heights['height'][::-1].cummax()[::-1].values\n",
    "display(heights)"
   ],
   "id": "27e5d399ebe187be",
   "outputs": [
    {
     "data": {
      "text/plain": [
       "    id  height  left_max  right_max\n",
       "0    1       0         0          3\n",
       "1    2       1         1          3\n",
       "2    3       0         1          3\n",
       "3    4       2         2          3\n",
       "4    5       1         2          3\n",
       "5    6       0         2          3\n",
       "6    7       1         2          3\n",
       "7    8       3         3          3\n",
       "8    9       2         3          2\n",
       "9   10       1         3          2\n",
       "10  11       2         3          2\n",
       "11  12       1         3          1"
      ],
      "text/html": [
       "<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>id</th>\n",
       "      <th>height</th>\n",
       "      <th>left_max</th>\n",
       "      <th>right_max</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>3</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>4</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>5</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>6</td>\n",
       "      <td>0</td>\n",
       "      <td>2</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>7</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>8</td>\n",
       "      <td>3</td>\n",
       "      <td>3</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>9</td>\n",
       "      <td>2</td>\n",
       "      <td>3</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>10</td>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>10</th>\n",
       "      <td>11</td>\n",
       "      <td>2</td>\n",
       "      <td>3</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>11</th>\n",
       "      <td>12</td>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "execution_count": 29
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "Step 4: Computing the Minimum of Left and Right Maximums\n",
    "- This finds the minimum between the left max and right max for each position.\n",
    "- This represents the maximum water level that can be held at each position."
   ],
   "id": "cceee0a3d45dabc6"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-14T16:36:02.986631Z",
     "start_time": "2025-03-14T16:36:02.971279Z"
    }
   },
   "cell_type": "code",
   "source": [
    "heights['min_of_right_left'] = heights[['left_max','right_max']].min(axis=1)\n",
    "display(heights)"
   ],
   "id": "df30ba721181648b",
   "outputs": [
    {
     "data": {
      "text/plain": [
       "    id  height  left_max  right_max  min_of_right_left\n",
       "0    1       0         0          3                  0\n",
       "1    2       1         1          3                  1\n",
       "2    3       0         1          3                  1\n",
       "3    4       2         2          3                  2\n",
       "4    5       1         2          3                  2\n",
       "5    6       0         2          3                  2\n",
       "6    7       1         2          3                  2\n",
       "7    8       3         3          3                  3\n",
       "8    9       2         3          2                  2\n",
       "9   10       1         3          2                  2\n",
       "10  11       2         3          2                  2\n",
       "11  12       1         3          1                  1"
      ],
      "text/html": [
       "<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>id</th>\n",
       "      <th>height</th>\n",
       "      <th>left_max</th>\n",
       "      <th>right_max</th>\n",
       "      <th>min_of_right_left</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>3</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>3</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>4</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>3</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>5</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>3</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>6</td>\n",
       "      <td>0</td>\n",
       "      <td>2</td>\n",
       "      <td>3</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>7</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>3</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>8</td>\n",
       "      <td>3</td>\n",
       "      <td>3</td>\n",
       "      <td>3</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>9</td>\n",
       "      <td>2</td>\n",
       "      <td>3</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>10</td>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>10</th>\n",
       "      <td>11</td>\n",
       "      <td>2</td>\n",
       "      <td>3</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>11</th>\n",
       "      <td>12</td>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "execution_count": 30
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "Step 5: Computing the Trapped Water at Each Position\n",
    "- Since height is always less than or equal to min_of_right_left, abs() isn't needed."
   ],
   "id": "73837f85374bbeac"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-14T16:36:03.126623Z",
     "start_time": "2025-03-14T16:36:03.102456Z"
    }
   },
   "cell_type": "code",
   "source": [
    "heights['trapped'] = abs(heights['height'] - heights['min_of_right_left'])\n",
    "display(heights)"
   ],
   "id": "654f0d3dbb567c17",
   "outputs": [
    {
     "data": {
      "text/plain": [
       "    id  height  left_max  right_max  min_of_right_left  trapped\n",
       "0    1       0         0          3                  0        0\n",
       "1    2       1         1          3                  1        0\n",
       "2    3       0         1          3                  1        1\n",
       "3    4       2         2          3                  2        0\n",
       "4    5       1         2          3                  2        1\n",
       "5    6       0         2          3                  2        2\n",
       "6    7       1         2          3                  2        1\n",
       "7    8       3         3          3                  3        0\n",
       "8    9       2         3          2                  2        0\n",
       "9   10       1         3          2                  2        1\n",
       "10  11       2         3          2                  2        0\n",
       "11  12       1         3          1                  1        0"
      ],
      "text/html": [
       "<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>id</th>\n",
       "      <th>height</th>\n",
       "      <th>left_max</th>\n",
       "      <th>right_max</th>\n",
       "      <th>min_of_right_left</th>\n",
       "      <th>trapped</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>3</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>3</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>4</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>3</td>\n",
       "      <td>2</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>5</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>3</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>6</td>\n",
       "      <td>0</td>\n",
       "      <td>2</td>\n",
       "      <td>3</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>7</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>3</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>8</td>\n",
       "      <td>3</td>\n",
       "      <td>3</td>\n",
       "      <td>3</td>\n",
       "      <td>3</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>9</td>\n",
       "      <td>2</td>\n",
       "      <td>3</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>10</td>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>10</th>\n",
       "      <td>11</td>\n",
       "      <td>2</td>\n",
       "      <td>3</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>11</th>\n",
       "      <td>12</td>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "execution_count": 31
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "Step 6: Computing the Total Trapped Water\n",
    "- heights['trapped'].sum() calculates the total trapped water across all positions.\n",
    "- The result is stored in a new DataFrame df with a single column 'total_trapped_water'."
   ],
   "id": "f795815f73a712f6"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-14T16:36:03.266926Z",
     "start_time": "2025-03-14T16:36:03.238107Z"
    }
   },
   "cell_type": "code",
   "source": [
    "df = pd.DataFrame({'total_trapped_water':[heights['trapped'].sum()]})\n",
    "display(df)"
   ],
   "id": "3f2db22d6d0ba56f",
   "outputs": [
    {
     "data": {
      "text/plain": [
       "   total_trapped_water\n",
       "0                    6"
      ],
      "text/html": [
       "<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>total_trapped_water</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>6</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "execution_count": 32
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "Reference: [1] https://leetcode.com/problems/calculate-trapping-rain-water/description/",
   "id": "abc246b3a75b4f01"
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}