leetCode/03. Stacks , Queues & Heap/42. Trapping Rain Water.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 42. Trapping Rain Water\n",
    "\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Example 1:**\n",
    "\n"
   ]
  },
  {
   "attachments": {
    "image.png": {
     "image/png": "iVBORw0KGgoAAAANSUhEUgAAAZwAAAChCAIAAAB8sJ6pAAAeF0lEQVR4Ae2de7BkRX3Hf919Zua+9o0Lu6K4sLxXC0wpIXF1gyAJprRIUipVIUbRyj8mlFWRMmUZ/jCkNJVIaaqSlKlQPnhqgIrxgZQghMcCJUSxXBCRALssy929e+/ufc2dOd2/1K975szMndnLPM6cnbn7PbV758yZc7p//ek+3/Prx8xPMTNhAwEQAIHVQkCvloKgHCAAAiAgBCBqaAcgAAKrigBEbVVVJwoDAiAAUUMbAAEQWFUEIGqrqjpRGBAAge5FzbEDPhAAARAYNAKqlyUd4Vql1KCVCvaAAAicsAS69NTiOJ6cnGRmKNoJ23RQcBAYTAIdixr7XudLL730xS9+8fDhw0QUjgxm8WAVCIDAiUagM1Hzrplcct999914442PPfaYFzXqpQ97ohFHeUEABPpKoDNRc04mB/bu3XvzzTcT0e233z4zM6O1ttb21UokDgIgAAJtEuhA1JjZGENE3//B9x966CEiuuWWWx588EEiUqqnCYc2bcVpIAACIPC6BDoQteCmvfzyy9/8xjeJaPv27UR0xx13TE9PG2PgrL0ua5wAAiCQAYF2RS1x0+69997du3dPTEwcPXqUiG677bZHH30UzloGVYUsQAAE2iHQbrfROae1/tWvfnXOOecQ0Zo1a6y1cRyXSqVdu3bdeuutW7ZssdaG/mk7GeMcEAABEOgHgajNRMN6tMOHD3/hC18wxtx5551PPvnkZZdddumll1prp6ent2zZonW7fl+bmeI0EAABEOiUQAeixswXXfTOiy++OI7jPXv2PPnkkxdddNF1111HRM45LMTtFD3OBwEQ6AeBdkUtjJopJbOfcRyHhWlh6kB+lQ0+Wj8qB2mCAAh0TqCzDmNQsWSpbfNO5wbgChAAARBIk0Bnorbsm57L3qZpF9ICARAAga4IdCZqXWWBi0AABEAgOwIQtexYIycQAIEMCEDUMoCMLEAABLIjAFHLjjVyAgEQyIAARC0DyMgCBEAgOwIQtexYIycQAIEMCEDUMoCMLEAABLIjAFHLjjVyAgEQyIAARC0DyMgCBEAgOwIQtexYIycQAIEMCEDUMoCMLEAABLIjAFHLjjVyAgEQyIAARC0DyMgCBEAgOwIQtexYIycQAIEMCEDUMoCMLEAABLIjAFHLjjVyAgEQyIAARC0DyMgCBEAgOwIQtexYIycQAIEMCEDUMoCMLEAABLIjAFHLjjVyAgEQyIAARC0DyMgCBEAgOwIQtexYIycQAIEMCERMpIhIXpj9i7wlJlZMxIq035dj/oMMbEIWIAACINA1gcjrWVCsRLT8TiWopyO2RJolNjt3nQ0uBAEQAIFsCEREsfhgolmq4owxObbOESllNLPSREaRI2ImdFezqRfkAgIg0CWBiCi4YJVuqBLlclpHuipflq1WxKQSR67LrHAZCIAACPSfQBQGzSQjL1rsykq7I1OTe577v/zE+nPPPWcscuSc1TkiJeNr2EAABEBggAlEXqaCVCl2rHVuduaVb95yx+zc3L6Xf7P9wks/9RdX5zWTczpx3qrlYa5oHDNXhuCqH+EVBAaKAPtNKeVnw1I2TfmhGeW3lJNGcp0TiLyDZv2FkZI3Lpcb+aMPX/3Gkzc/9uOv/9PXH/nzj/3pxrxWFPvm0NAHTWQu2encAFwBAlkQSBTHN/L0c8ToTPpMu00xIj8DIIs42BFp69TI+Ho68Mx/PnDPQw/v/vDHP74hr2O2plUGTmYTZHPOJY2m1Yk4BgLHkwAzz8/PLy0t9a8/wcyFQmFiYuJ4lhN5ewKRnwEwvhOqZGmadCgNc6xNbtNJm3695+cHf/uCzWMF65zSWpay+S3I2SuvvPLII48ERTv//PM3bNiAfija1UARsNYaY+bm5m644Ybbb7/9rLPOKhaLKUpbaPDGmH379l111VWf/9vPRybCXXB820Ak62tlSYef/WRndByXl07dfuGp2y98/2W/87vves/bL7748t96q2Nn6tZzhP7mSSedtGPHDqWUtTY8o1JsLseXC3JfHQTCsO/S0tJTTz31kt/6V649e/ZYayMT9S8LpNwOAamAZOjUWasj/eq+F39w3+NnbNv261888bZ3X3nmm98ozpvMki6f+xwdHV23bl2SDR5QCQrsDBQBrfX69euJ6Mwzz5ycnIyiNHVHKTU6Orp37961a9f0acBuoGAOvjGy+DZ8gYBJay1fMDhp89a3bN30y188PTKx5W8+94nT37CRXUlp+ULVsq1+TE1rDTdtGR+8Pe4EQptUSoW2WiqVjhw5YoyxNkyOpWCgMZUBZ2srQ8wpJIokeiDgH1kyc+P/a8XOjY5vuPyKKy+/opKq+F+ySE22ZbqWqFiyU7kGLyAAAiBwnAhEpCL5EoFffCsv2jhnmaz2yzscKz98Vvm+wXEyEtmCwOASwLz/oNVN+DKUnyvgylIbLRsTyffYtTYykbDcRRu0UsAeEAABEKgQiESy6lbUhl1FhnTlqB/7bLlMDRBBAARAYOAItJwGqhO5gTMYBoEACIDASgSqv8Wx0jn4DARAAASGhgBEbWiqCoaCAAi0QwCi1g4lnAMCIDA0BCBqQ1NVMBQEQKAdAhC1dijhHBAAgaEhAFEbmqqCoSAAAu0QgKi1QwnngAAIDA0BiNrQVBUMBQEQaIcARK0dSjgHBEBgaAhA1IamqmAoCIBAOwQgau1QwjkgAAJDQwCiNjRVBUNBAATaIQBRa4cSzgEBEBgaAhC1oakqGAoCINAOAYhaO5RwDgiAwNAQgKgNTVXBUBAAgXYIQNTaoYRzQAAEhoZAy1++Jfab/NC3rv6q99CUCIaCAAic0ARaiBoz1QLkSIA8CeB+QkNC4UFggAggtNvrVIb2UaNCjDwSD825EFQqLpedDeFAHcvnCNT6Oijx8QAT4MaIaMP1kHZMtloAJzcscxrx3STJarIeT927Aa7K1zctItIUouApKZPWFC9NP/Tww48//vMy5y/74Acv2nG2YsdUJjL+3+snijOWEfBPhWXH0n5bCXCYdrLDm550OCohbb0E1AlZ3W4q5UvqN+wkb1NJvBrtTXpQfl+FmOLy0ktBJBVHVEktpCVJyvGQQ0rmNyaTQeBzzd4FU1IM650xvTA7MzUzf8llu04/xX3pS1/eO7NAWltnfBD3BgO9Yyd+nHU27YpsyGio30gPPs2NlJIQrcuTDO0dfxMC/oZXVQUIN231b79u2uSOXV47Pb73ASs1OVLklCZpAL4NJIXtZkcpMopYq1gpJ5Z7633KPZp7zMtJHjP9gp+oRMTkJMqnSBsLLUtrN5zyJ3/8ESLavjX/nXu+MlcqEY1pNt6hazAol8v5+O0UGRmbC3dvkjR2EjlLFUV4XKea5OpNTBsJWesKUSWObXBtGlpxCoUPWmaMyefz5GOAp5BofRJittS7ko5VSmPcFS+v1v0KT4H6bFPfD+Pz/RaKiCnnpwK0YlZcYm3KXMhJaRZuve2ud1/+/rM3rxcnXjkvepViBrk9ePDg888/H+Rs69at4+PjLMpXoZU6keFK0DmntV5YWLj//vsPHDgwMjLiXFrjkmEkJCzHUcTWjK41605lafBp36/DBX2ZtUq5OC6MjEwffm3fq68R0fxCsTF497ILunnLzMWiJPvcc8/ddNNNhUIhjuPEZesmxaZrfMeTNbto3RY1tpH8+94bkxM3VpswQKcUFw/HM6949Uy/ISmlnHOO3a737Nq2bVtfdS3SchuEh7+UhJmMltmDe//7zgPFN3zm6g8Zotiykt6nl6w64nEcF4vFsP6jcsf22M+vS3zYd4OoTU1NXXvttS+88EKfi3P+BX/2aatGmGM8VGqoFamYIpPn4v59L08R0ez8kiLyDxeV1gPAWjs7Ozs+Pv6w32q592Fv3cXXbD9v52Ls3UHiZDys86wUUey0Y4q0E6dlNK9e3HP/od3f6Dypzq64++67t23b1tk1HZ4dKZlMMTI+qJTjyBCTPfzdO2/93v+88JnPXjeao/mlcqGQU86p2phi6H3T5s2bd+zYkeTYV/VNchm6nVNOOeWFF14444wzJicnc7lc72MKye0oQxcmP3fwwLZ3nLZ144TVI8Sxf0QNHaS+GexY50bj+blDeel+GKPlsSvduGQSIYWslVLz8/P5fH58fFwp1XsVL7NJa82kilOHzt160oZNG+PYKVG02tTlsvPbeKuUH0x3KpIhJ6ZcTo9s2fAUUWHDBq0j50JDSsHx97rBURQZYw4cOGD8gEAbFnZ/ip/9rHYYHTtj9P4XX/63f//2ui1nfedb/3Fo+ujVH/vEheeeaaUHutwpXVZ56brc3ZdpkK7UWodajON4dnZ2bGxsGbSejFVKG14isuwsOSetU5bh9JTm6rqYyQoOV3Qi92ENg3+CpzpgHerUWhv6oakjVDpyrIpEsgzBOrIl2e19vpsNK1ayXkQZ1s6pBSK3uGiivItLzRODXZeLmQuFQrg8A5Xwi28rd4GKZJQm3nTy6d+6/U7nqLi0xEqt37Cx8nBLPISmwoWuVtPhE/pAUnmhYx7+LiwspAvFjEgNOifzPaxlbizFtpiuqdmnJg2WDbNRMm1Y+0Zg8oWZdE2y1i4uLqabZiU1nfPdKekn+jVqSsZPxYvq2ZMSPWafmlAhomKxGOVVXJJRwhQ37bcw/p5isi2Tqn2jwBdJs+PCyGhhdG392dY5veJcbHID11+F/WYCxpi0pguY2RhjZPigMvYdHjrw0wL2hts9Kyj9uBGYOTI6ZkXe16xvVD0WyyOSRaqVqYJq0tr7gKqpZ1b9vLPXMEXQDzLHsqMmauKUy4oqIyvXXExKuvHk11jJug1nfbemR4zHMuMEOh6eh6kUuOXC8oabOZVskEjbBFKs3Hby7KWuq3dyixVCIVlfll5yaKcEfTmnJmrVxXcynKqULDX2i0qqZZcpUfFTsYEACIDAIBMIEwViYVW9grW1AYiq9eFzqFqVB15BAAQGkkDNU2scdGyUuIE0HUaBAAiAQDOBRNTq17xA0ZpB4QgIgMBwEEhErcV44XCUAFaCAAiAQB2B5rGzug+xCwIgAALDRgCiNmw1BntBAARWJABRWxEPPgQBEBg2AhC1Yasx2AsCILAiAYjainjwIQiAwLARgKgNW43BXhAAgRUJQNRWxIMPQQAEho0ARG3Yagz2ggAIrEgAorYiHnwIAiAwbAQgasNWY7AXBEBgRQIQtRXx4EMQAIFhIwBRG7Yag70gAAIrElhZ1PDraSvCw4cgAAKDR6C1qEmcVIlLJLGznLxI4Dx/ZPBKAItAAARAoI5A8tNDdcd8tAInUT61ZlY+GJdEyFv247gNV+ANCIAACAwEAU0+pukyWxRLLEBrJdKMIonG5UPLtHbrll2LtyAAAiBwHAlE/le8nQhXbWNHnPORVqT7KfGyxF+TSCwYZKtRwh4IrBoCq+rHrkP3s1Yk9oGftdavvbp3cmbh3LPOioxyvvMJQeuoCYdYih1d0sPJ4dfYpYpqddlDcs2X9rX2+2RzcylWzRFPLJU6SVpOKql1AJjFVepLzYdoUpWkfdxPKdvjD//ka//6z7zpjK/+w99PmBxJGNVciJVbb3US5dBf2Bf7mEVR+7r1J8yqkm69oQRRX4sQQnUHUP3C5RtgP6qi0q76kbQP6ihAJPH+ZNDvem2VfkpV7JOpqqMP1J4FonBHOHZKNK0v90fU+GiXUsVxKVeIPnDFzvt/MRPb0BxMy2YhQY79luy0qoKejikVwkX3lMhxuTjKiRecz+eCaPZHOitPOqV0ZCKrI1FSH147vSKHZxU75/rRAIOiKaW0qR8ASc18zRxFERvjB4VTSzbDhBp8Ca21MZEoQqWWe5IhlkEnSUiRjiJJOpSrL+6J5CQJ5/N5CS2sq3n1IbNk9tPfDUozW60Lb3/HznWFxZ88/TArT01euMqxVqHWb0opa20URc0n1E7tcC+4ps656enppdKSVmm1+PpGIGVTRE4ba3J+Pxzo0NZjnB7H8diaiZcmp5bKZXlUWHuME3s5zMyy/MaVZuMjL7LKMdu0RM1XOfnBVtaKePRkjsaUi3sxt/5a35gdk2FldPkIFw8yK05RkcMgsHMcGTt/0JaLkjuL/Yr67v7Xl7S3/XADuuBouvkDbuY3LrQlIVjfnjvLR0lo8jARyMxsI2UXDoYkQqPqJfFmU6SlOmmrk5OTMzMzi4uLKcpFkh0z5/P5IGpVB11mO3W4K4oLs+XY+uJJF9ApbaTBVSAG+/bv37979275kNT5O87fuGFjWv1QZ50x5sCBV//q2mt/dM+PzjvvvPQoJO1AkdJxcWbzmTtP2fE+y0YW4qV3Uznn8jlTPPzS3n0HiOjI0XlRH5fknlRE9zuSWmmBiPY//7/T+3/tJTrN9OX+18bGJaPovCv+euLkc2JplrVm0K3pQW8kHSaKtJ555Zlf3vOl3PjJpDR5me425RbXyd3Ldn5BQC0tzGmK/M3lF1+2OH0ADxkrDXOJST/76N25n/7QiYclNdHbFu567Z9bTpMtl8sCh2wcHgC9pZ5cHRz8YtE/VIiuv/76G2+8MQhIck4qO0qpUql02mmnJRMF4grJ9KbMfDpSufGJdaMjhfHxUZ+f0rqqZ/596G9u3rz5ggsuCJ7a2NiYTyEdbzKAmJ9feOAnD8zNzT3xxBOpFLtlIvvUWRe8KWdVjlyaosaOcpFxsyaOhYm/kXp6tLYynp1jY6Li4nxxUUSzfxuX5rQMrablzCoRNtZKcURLdvHQXJGo+Fr/7CeiKDI2ZhbdlApJntB9zTSNxJX4VFqZSB2dPUJ0JI00W6eRiyK2/lHT+vPujwYVGxkZefHFF7tPpY0rn3nmmaT76X1Z9u4/L/3sycd//KP7H3nwsbvufOuuXe/esmmTc05JJ6Qh1UKhMDExkRxKy01LEoyi6LTTTpuamjr99NMPTR2KTGJtckr3O0oGcnJzBw+8adPExKi2shov3LGp3LfsWEV5E0vX2bs3FbU3/nbq/TGbFFxZG5soZyIZqkh9Mya3VCq58gJp4yojeOKYNzaEzrL1Hpr0CVh5MmyNT68wvk4eqtam5S6HitSiXhyXSy6OvZLGSvqfKVZBZ8Xv/Gzrl8OzZZvLjyrd0LvqPLXaFfXzj0op52w5Ltf1x2pnprVXLBbXrFmTz+f7MT4bjNS6AqjBZqV4aurQpi1nf/ov3za/MLdYXAofN/c6Eh/SOae1TrOTXHX4yn5Aamlp6eiRow1WpvEmGlkbE5Xj2MqdpFP01BTJ6mXjFNtytT8lOuDdhF4EobnYkpqNyy5Of8yOyUWFEVfpjIhEiG8lpei1CEo0X0apndJOSdfAlyImF8flJdWwarK5yB0cUeTEYG2czLUZIhv8tObG3EGiWZ/qB4WcIm3LcYmo7J8plkT8q/dJVyaJ/yd8ZNRJfFclQ0+c6ghJs12zs7PNB9M9kvg+vslWHpH5977vg37oxBeVyDo/SyAPtwaIiYolO2kZl9RWsCikb4yxvQ23V8ZFfcdDy4xYxV5FWnF4olcP9VoSVs6QKxDnZWWHbD5lcQZ7VYQWpoWCpZq0mMsNLhl7AWoch2hhSxuHpEOQrOPzw9V+IigpRRrTQkG2hLWUxJKMmSqiKOQr32Uelk3WPkgvQjsZShMNElDKaumVdqfOfpbAEGnntFJO+W95E5OuzhEMC5uWdiaurAgWyxiHYaWlnclcVFnJ5JQWN9UP3vTjfmxpVp8OhrtG3KhKBkHCZHynOhPUXSOpt1dSEFGWzCzLeIhs4a8Rb7APHR95JPkcQjb15nS3HySNjZ/1D/b7ViHlWP5s6zwH+VqxVxtxo6qEwqIyn1iFWecJ11/ha1IGGbwjIj1OUk58Q9977kMl1Gee6j7LQlGlxbOQslhxOWWnh2FBYSCq6KvTybe8qxb3fgNUUzpur0HUKjd7xS3yzcx7bjIVpch4ltJZqN6bWZobdCedHJtu+XCA/UpZ5x+DvWeX3JGxv4Nsg7fTD0UTNorlMZ7eVvGjGvxKeYzLDxwEleg+r5pr5qXYd6JCRYR2KN3F7lOvXln3MPF1KmomCyNCI29qCdXLBvA11IWMPyoW78w7nkqz9U+ErgyW4W9piv7hLrTlkVhlclxu866KcYyLku5nQzOSgRORsEiW5cmV2vvwSbGPkdjAH66ruXpbq0ImQl5/vOd96fKYpCvthy28499zwk0JcM37bPqs2wOhcVebunz9V4rivdrqwa6S9umGFPyPwKjgJgd3NhyvetJdpV9/UWKojKn5bZhmCBpLIn5VrX326moyKfllMdnEXUtA1ec5pPuJqA2p/WmZXW3xaaVXSyeZMq62x6F5EIZ2XjW7MjiV3oOtT/JeI1/Zq96u1demE4bpQJqFSNJKdoaJxAq2NjhoK5yHj7olsNpaTLccmq4DmCYkOJAKAYhaKhhXSKTO01nhLHwEAiCQEgGIWkogkQwIgMBgEICoDUY9wAoQAIGUCEDUUgKJZEAABAaDAERtMOoBVoAACKREAKKWEkgkAwIgMBgEIGqDUQ+wAgRAICUCELWUQCIZEACBwSAAURuMeoAVIAACKRGAqKUEEsmAAAgMBgGI2mDUA6wAARBIiQBELSWQSAYEQGAwCEDUBqMeYAUIgEBKBCBqKYFEMiAAAoNBAKI2GPUAK0AABFIiAFFLCSSS6ZQAfpOpU2I4vz0Cx/rlW4mSy8wpB75rz6bVdRZ+C/EY9QkwxwCDwz0SaCFqPrSD0j5OgfyAuUQ4xlO1R86r5vIU4jhU1GxoftZ81dTdiVKQyAdXYyZnlTFOAl6wNpooLpfimEdGCz50M/vgGFlLW4Zi6uPFSgDE1MoY4pQ4CTno72KfsNzIQ+Wh1CIsSAwpHxhYOR8jtes7RLGPHEhsDEv0RVIuIILKdc0UF9YTCJ4as9xrEmuJJXB2+ZmnH/qv7z44M2vfecnvXXH5e/M+QGDz7e78ppSy1qYrQHEcG2PiOA7h6ZMg9boWn7C+FB3vs4T+q27s2Fkpt3PdBoetJlV7Vexix5EEmwwqFqIZKeWLkIK/U8uqb3vsaiE+HbNzyjmpbd9UupYgRZKKb20ulgDJ0vhqtSFx31Kq5b6BQcKDS4CZI2lNSmmJ5CZtSxtz+NVnb7jhK3/wkU/u3GQ//7nPbn7jze/acXZsrY508twOZcrn80FloqhFN7aXchsjUc3Hx8eDVoa/PYZnX2aPlU30RunI5EaIcsQ2xRh5jtnk81EkvrBEavSh2VwtwvxwOGzlUiVanTE5kx9lFWmKfYD1mgwtA/u6b32gbB+NlyOifGSc0dJ+yjGTjaWvIGKKDQS6JBD5kH8yfqbYxj5w9m+e/Xn+5B1XXvmHYxT//nt++PQvX3rXjrO1hD4VofEaqHK5HBEtLCwcPHiQFDkrT/AuTWh1mbV2YmJi//79+XyeiCYmJk499dS03LRahsqUZmdHTVktvqopItGd1EqhmFWc10tT69eO53hjfnS927gmXUq1gvRpTxxKJSGMy3O58mE9/7K2thL+sydQXhUlaQkpq02c57lTNhXyE5t9AL40a6FPYJDsABIIo//OOWKOZZ5TehflkrXM/NBd/3Ld3315uszM01/76vX/eNP3ZB7UWuml+TnRhYWFnTt39rtUY2Nj/c4C6YMACKw+AtVuo39oSmR7otzE2vn5mZx8MlI8MpPbIM4LU5lInCYiMsZ89KMfveSSS/L5/Pz8fDiY+l/pG0fRyMhI370bGS2yUsjUvLQqDD90prSWATvxhX0w7NRzqebWt1ffOFyZOCalWcYd/ThEtwVhcYlZURg58yNqWpGK+lABfUOChAeMQDLsPjIyEvn7jFh6l5XR2q1vOePZn37rZz/7wJvXxvc98NSnvvRJP8zBFPlbkyifz19zzTUDVqhBNmc4pgWyJNhEpOlAltYgr9VFQLGMjmsmmYNSrP3I2OJ3v/Ptu75/fxTlLr7kfR+56kNjKoy8VZeurS4EKA0IgMBqIqASty2Uin3vgmhx5vDRJcpv3LhBZgQ4rHWo9TdkNA4bCIAACAwegeWiJgomq4bKpGQEzXtxYVWRHxUavALAIhAAARCoJ1CdKKg7ppRipx3LulFZ6hFWWda8tLpTsQsCIAACA0aghaiJhTrSYS5KVhKFvueAGQ5zQAAEQKAVgWOIWsOpsuYWjloDErwBARAYVALHEjW/vIMrC5K8qIWv9UDcBrUmYRcIgIAn0PpHIr10JV/FBioQAAEQGBoCLWY/h8Z2GAoCIAACTQRae2pNp+EACIAACAwHgf8H9Tpoc1j4hAoAAAAASUVORK5CYII="
    }
   },
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![image.png](attachment:image.png)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **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."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Example 2:**\n",
    "\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **Input**: height = [4,2,0,3,2,5]\n",
    "- **Output**: 9"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Constraints**:\n",
    "\n",
    "- `n == height.length`\n",
    "- `1 <= n <= 2 * 104`\n",
    "- `0 <= height[i] <= 105`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def trap(self, height):\n",
    "        \"\"\"\n",
    "        :type height: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        ## sol1\n",
    "        \n",
    "        # area = 0\n",
    "        # for i in range(1 , len(height)): \n",
    "        #     minh=min(max(height[:i]) , max(height[i:]))\n",
    "        #     if minh  - height[i] > 0 : \n",
    "        #         area += minh  - height[i]\n",
    "        # return area \n",
    "\n",
    "        ## sol2 \n",
    "        res = 0\n",
    "        l , r = 0 , len(height) -1 \n",
    "        lmax , rmax = height[l] , height[r]\n",
    "\n",
    "        while l < r  :\n",
    "            if lmax <= rmax :\n",
    "                l +=1\n",
    "                lmax=max(lmax , height[l])\n",
    "                res += lmax - height[l] \n",
    "            else :\n",
    "                r -=1  \n",
    "                rmax=max(rmax , height[r])\n",
    "                res += rmax - height[r] \n",
    "        return res\n"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}