Neetcode—Two Pointers.ipynb

{
 "cells": [
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "# Valid Palindrome\n",
    "\n",
    "> Given a string s, return true if it is a palindrome, otherwise return false.\n",
    ">\n",
    "> A palindrome is a string that reads the same forward and backward. It is also case-insensitive and ignores all non-alphanumeric characters.\n",
    ">\n",
    "> Note: Alphanumeric characters consist of letters (A-Z, a-z) and numbers (0-9).\n",
    "\n",
    "## Examples\n",
    "\n",
    "### Example 1\n",
    "\n",
    "Input: `s = \"Was it a car or a cat I saw?\"`\n",
    "\n",
    "Output: `true`\n",
    "Explanation: After considering only alphanumerical characters we have \"wasitacaroracatisaw\", which is a palindrome.\n",
    "\n",
    "### Example 2\n",
    "\n",
    "Input: `s = \"tab a cat\"`\n",
    "\n",
    "Output: `false`\n",
    "Explanation: \"tabacat\" is not a palindrome.\n",
    "\n",
    "## Constraints:\n",
    "\n",
    "- 1 <= s.length <= 1000\n",
    "- s is made up of only printable ASCII characters."
   ],
   "id": "c481d24b58218a07"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## Solution 1 - 2 Pointers\n",
    "\n",
    "- Time complexity:\n",
    "$O(n)$\n",
    "\n",
    "- Space complexity:\n",
    "$O(n)$\n",
    "\n",
    "    _We can reduce to $O(1)$ space by not creating a new string and just using parameter (i.e. skip if not\n",
    "    `isLetterOrDigit()`._\n",
    "\n",
    "_Where $n$ is the number of `char`s in `s`._"
   ],
   "id": "19da626e0761338b"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "fun isPalindrome(s: String): Boolean {\n",
    "    val palindrome = s.replace(Regex(\"[^a-zA-Z0-9]\"), \"\").lowercase()\n",
    "    var l = 0\n",
    "    var r = palindrome.lastIndex\n",
    "    while (l < r) {\n",
    "        if (palindrome[l]!=palindrome[r]) return false\n",
    "        l++\n",
    "        r--\n",
    "    }\n",
    "    return true\n",
    "}"
   ],
   "id": "9107dab1371b5c45",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "# Two Integer Sum 2\n",
    "\n",
    "> Given an array of integers numbers that is sorted in non-decreasing order.\n",
    ">\n",
    "> Return the indices (1-indexed) of two numbers, [index1, index2], such that they add up to a given target number target and index1 < index2. Note that index1 and index2 cannot be equal, therefore you may not use the same element twice.\n",
    ">\n",
    "> There will always be exactly one valid solution.\n",
    ">\n",
    "> Your solution must use $O(1)$ additional space.\n",
    "\n",
    "## Constraints\n",
    "\n",
    "- `2 <= numbers.length <= 1000`\n",
    "- `1000 <= numbers [1] <= 1000`\n",
    "- `1000 <= target <= 1000`"
   ],
   "id": "8d07504c22f5137b"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## Solution 1 - Nested Loops/Brute Force\n",
    "\n",
    "- Time complexity:\n",
    "$O(n^2)$\n",
    "\n",
    "- Space complexity:\n",
    "$O(1)$\n",
    "\n",
    "_Where $n$ is the size of `nums`._"
   ],
   "id": "7dd3571b7c294a4e"
  },
  {
   "metadata": {
    "executionRelatedData": {
     "compiledClasses": [
      "Line_5_jupyter",
      "Line_6_jupyter",
      "Line_4_jupyter",
      "Line_7_jupyter"
     ]
    }
   },
   "cell_type": "code",
   "source": [
    "fun twoSum(numbers: IntArray, target: Int): IntArray {\n",
    "    for (i in 0 until numbers.lastIndex) {\n",
    "        for (j in i + 1 until numbers.size) {\n",
    "            if (numbers[i] + numbers[j] == target) return intArrayOf(i + 1, j + 1)\n",
    "        }\n",
    "    }\n",
    "    return intArrayOf(0, 0)\n",
    "}\n",
    "\n",
    "val nums = intArrayOf(1, 2, 3, 4)\n",
    "twoSum(nums, 3).joinToString(\",\", \"[\", \"]\")"
   ],
   "id": "147d26e995a76cd5",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## Solution 2 - 2 Pointers\n",
    "\n",
    "- Time complexity:\n",
    "$O(n)$\n",
    "\n",
    "- Space complexity:\n",
    "$O(1)$\n",
    "\n",
    "_Where $n$ is the size of nums._"
   ],
   "id": "1c16519edf06aac9"
  },
  {
   "metadata": {
    "executionRelatedData": {
     "compiledClasses": [
      "Line_8_jupyter"
     ]
    }
   },
   "cell_type": "code",
   "source": [
    "fun twoSum(numbers: IntArray, target: Int): IntArray {\n",
    "    var l = 0\n",
    "    var r = numbers.lastIndex\n",
    "    while (l < r) {\n",
    "        if (numbers[l] + numbers[r] == target) break\n",
    "        else if (numbers[l] + numbers[r] < target) l++\n",
    "        else if (numbers[l] + numbers[r] > target) r--\n",
    "    }\n",
    "    return intArrayOf(l+1, r+1)\n",
    "}\n",
    "\n",
    "val nums = intArrayOf(1, 2, 3, 4)\n",
    "twoSum(nums, 3).joinToString(\",\", \"[\", \"]\")"
   ],
   "id": "693ff6575763c8ba",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "# 3 Sum\n",
    "\n",
    "<!-- threesome lol ;p -->\n",
    "\n",
    "> Given an integer array `nums` return all the triplets, `[nums[i], nums[j], nums[k]]` where `nums[i] + nums[j] +\n",
    "> nums[k] == 0`\n",
    "\n",
    "## Solution 1 — Brute Force — Triple-nested loops\n",
    "\n",
    "- Time complexity:\n",
    "$O(n^3)$\n",
    "\n",
    "- Space complexity:\n",
    "$O(n^3)$\n",
    "\n",
    "_Where $n$ is the number of elements._"
   ],
   "id": "37c909c03107958e"
  },
  {
   "metadata": {
    "executionRelatedData": {
     "compiledClasses": [
      "Line_13_jupyter",
      "Line_10_jupyter",
      "Line_11_jupyter",
      "Line_9_jupyter",
      "Line_14_jupyter"
     ]
    }
   },
   "cell_type": "code",
   "source": [
    "fun threeSum(nums: IntArray): List<List<Int>> {\n",
    "    val result = MutableList(0) { listOf<Int>() }\n",
    "    val sort = nums.sorted()\n",
    "    for (i in 0..sort.lastIndex - 1) {\n",
    "        for (j in i + 1 until sort.lastIndex) {\n",
    "            for (k in j + 1..sort.lastIndex) {\n",
    "                if (sort[i] + sort[j] + sort[k] == 0) {\n",
    "                    result.add(listOf(sort[i], sort[j], sort[k]))\n",
    "                }\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "    return result.distinct()\n",
    "}\n",
    "\n",
    "val nums1 = intArrayOf(-1, 0, 1, 2, -1, -4)\n",
    "println(threeSum(nums1).joinToString(\",\"))\n",
    "\n",
    "val out1 = listOf(listOf(-1, -1, 2), listOf(-1, 0, 1))\n",
    "\n",
    "val nums2 = intArrayOf(0, 1, 1)\n",
    "val out2 = emptyList<List<Int>>()\n",
    "\n",
    "val nums3 = intArrayOf(0, 0, 0)\n",
    "val out3 = listOf(listOf(0, 0, 0))"
   ],
   "id": "d29c676cc7c0e441",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## Solution 2 - Two Pointers\n",
    "\n",
    "- Time complexity:\n",
    "$O(n^2)$\n",
    "\n",
    "- Space complexity:\n",
    "  - $O(1)$ or $O(n)$ extra space depending on the sorting algorithm.\n",
    "  - $O(m)$ space for the output list.\n",
    "\n",
    "_Where $n$ is the number of elements in `nums` and $m$ is the number of triplets._"
   ],
   "id": "ef4829869770e139"
  },
  {
   "metadata": {
    "executionRelatedData": {
     "compiledClasses": [
      "Line_13_jupyter",
      "Line_20_jupyter",
      "Line_21_jupyter",
      "Line_5_jupyter",
      "Line_11_jupyter",
      "Line_4_jupyter",
      "Line_9_jupyter",
      "Line_12_jupyter",
      "Line_18_jupyter",
      "Line_17_jupyter",
      "Line_10_jupyter",
      "Line_16_jupyter",
      "Line_8_jupyter",
      "Line_19_jupyter",
      "Line_15_jupyter",
      "Line_6_jupyter",
      "Line_14_jupyter",
      "Line_23_jupyter"
     ]
    }
   },
   "cell_type": "code",
   "source": [
    "fun threeSum(nums: IntArray): List<List<Int>> {\n",
    "    val result = mutableListOf<List<Int>>()\n",
    "    nums.sort()\n",
    "    for (i in 0 until nums.lastIndex) {\n",
    "        if (i > 0 && nums[i] == nums[i - 1]) continue\n",
    "        val complement = 0 - nums[i]\n",
    "        var l = i + 1\n",
    "        var r = nums.lastIndex\n",
    "        while (l < r) {\n",
    "            if (l > (i + 1) && nums[l] == nums[l - 1]) l++\n",
    "            else if (r < nums.lastIndex && nums[r] == nums[r + 1]) r--\n",
    "            else if (nums[l] + nums[r] == complement) {\n",
    "                result.add(listOf(nums[i], nums[l], nums[r]))\n",
    "                l++\n",
    "            } else if (nums[l] + nums[r] < complement) l++\n",
    "            else if (nums[l] + nums[r] > complement) r--\n",
    "        }\n",
    "    }\n",
    "    return result\n",
    "}\n",
    "\n",
    "val nums1 = intArrayOf(-1, 0, 1, 2, -1, -4)\n",
    "println(threeSum(nums1).joinToString(\",\"))\n",
    "\n",
    "val nums3 = intArrayOf(0, 0, 0, 0)\n",
    "println(threeSum(nums3).joinToString(\",\"))"
   ],
   "id": "28b63439f615edf8",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "### Hint\n",
    "\n",
    "> Think about what changes you'd need so that:\n",
    ">\n",
    "> 1. You find **all** triplets for a given `i`, not just the first one.\n",
    "> 2. You skip duplicate values of `sort[i]`, `sort[l]`, and `sort[r]`."
   ],
   "id": "b3326f565fa485fc"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "### Solution from Neetcode.io\n",
    "\n",
    "_This seems cleaner to me. Little confused on the `a` val. I think the `break` check acts as a way to short-circuit\n",
    "because when `a > 0`, due to the sorted property, we know `nums[l]` & `nums[r]` will also be positive and because we\n",
    "are trying to sum to 0, it is no longer possible to reach it if we are dealing only with positive values._"
   ],
   "id": "8135b464c316db2c"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "fun threeSum(nums: IntArray): List<List<Int>> {\n",
    "    val res = mutableListOf<List<Int>>()\n",
    "    nums.sort()\n",
    "\n",
    "    for (i in nums.indices) {\n",
    "        val a = nums[i]\n",
    "        if (a > 0) break\n",
    "        if (i > 0 && a == nums[i - 1]) continue\n",
    "\n",
    "        var l = i + 1\n",
    "        var r = nums.size - 1\n",
    "        while (l < r) {\n",
    "            val threeSum = a + nums[l] + nums[r]\n",
    "            when {\n",
    "                threeSum > 0 -> r--\n",
    "                threeSum < 0 -> l++\n",
    "                else         -> {\n",
    "                    res.add(listOf(a, nums[l], nums[r]))\n",
    "                    l++\n",
    "                    r--\n",
    "                    while (l < r && nums[l] == nums[l - 1]) {\n",
    "                        l++\n",
    "                    }\n",
    "                }\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "\n",
    "    return res\n",
    "}"
   ],
   "id": "eb9f4210e56c779e",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "# Container with Most Water\n",
    "\n",
    "> You are given an integer array `heights` where `heights[i]` represents the height of the $i^{th}$ bar.\n",
    ">\n",
    "> You may choose any two bars to form a container. Return the _maximum_ amount of water a container can store.\n",
    "\n",
    "## Examples\n",
    "\n",
    "### Example 1\n",
    "\n",
    "```kotlin\n",
    "val heights = [1,7,2,5,4,7,3,6]\n",
    "val result = 36\n",
    "```"
   ],
   "id": "6a3b71922328618b"
  },
  {
   "metadata": {
    "executionRelatedData": {
     "compiledClasses": [
      "Line_14_jupyter"
     ]
    },
    "tags": [
     "data vis"
    ]
   },
   "cell_type": "code",
   "source": "%use lets-plot\nimport org.jetbrains.letsPlot.*\nimport org.jetbrains.letsPlot.geom.*\nimport org.jetbrains.letsPlot.scale.*\nimport org.jetbrains.letsPlot.themes.*\nimport kotlin.math.min\n\n// Heights matching the screenshot\nval heights = listOf(1, 7, 2, 5, 4, 7, 3, 6)\n\n// Two green \"container edge\" bars (same positions as the screenshot)\nval left = 1\nval right = 7\nval waterH = min(heights[left], heights[right])\n\nval df = mapOf(\n    \"x\" to heights.indices.toList(),\n    \"h\" to heights,\n    \"kind\" to heights.indices.map { if (it == left || it == right) \"edge\" else \"bar\" },\n)\n\nval waterDf = mapOf(\n    \"xmin\" to listOf(left + 0.5),\n    \"xmax\" to listOf(right - 0.5),\n    \"ymin\" to listOf(0),\n    \"ymax\" to listOf(waterH),\n)\n\nletsPlot(df) + geomRect(\n    data = waterDf,\n    fill = \"#8ecbff\",\n    alpha = 0.55,\n) {\n    xmin = \"xmin\"; xmax = \"xmax\"\n    ymin = \"ymin\"; ymax = \"ymax\"\n} + geomBar(\n    stat = Stat.identity,\n    width = 0.35,\n    color = \"black\",\n) {\n    x = \"x\"\n    y = \"h\"\n    fill = \"kind\"\n} + scaleFillManual(\n    values = listOf(\"#000000\", \"#7fbf56\"),\n    limits = listOf(\"bar\", \"edge\"),\n    guide = \"none\",\n) + scaleYContinuous(\n    breaks = listOf(0, 2, 4, 6, 8),\n    limits = Pair(0, 8),\n) + scaleXContinuous(breaks = emptyList<Int>()) + themeClassic() + theme(\n    axisTitleX = elementBlank(),\n    axisTitleY = elementBlank(),\n    axisTicksX = elementBlank(),\n    axisTextX = elementBlank(),\n    panelGrid = elementBlank(),\n    axisLine = elementLine(size = 1.2),\n)",
   "id": "6fe0349d38a8c8a2",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## Solution 1 - Brute Force - Nested Loops\n",
    "\n",
    "- Time complexity:\n",
    "$O(n^2)$\n",
    "\n",
    "- Space complexity:\n",
    "$O(1)$\n",
    "\n",
    "_Where $n$ is the size of the array._"
   ],
   "id": "6b2e5ee6fe5bc0b6"
  },
  {
   "metadata": {
    "executionRelatedData": {
     "compiledClasses": [
      "Line_17_jupyter",
      "Line_19_jupyter",
      "Line_15_jupyter",
      "Line_20_jupyter"
     ]
    }
   },
   "cell_type": "code",
   "source": [
    "fun maxArea(heights: IntArray): Int {\n",
    "    var maxArea = 0\n",
    "    for (i in 0 until heights.lastIndex) {\n",
    "        for (j in i + 1 until heights.size) {\n",
    "            val area = (j - i) * minOf(heights[i], heights[j])\n",
    "            maxArea = maxOf(area, maxArea)\n",
    "        }\n",
    "    }\n",
    "    return maxArea\n",
    "}\n",
    "\n",
    "var heights = intArrayOf(1, 7, 2, 5, 4, 7, 3, 6)\n",
    "maxArea(heights)"
   ],
   "id": "bd77461ded67b9c",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## Solution 2 -\n",
    "\n",
    "- Time complexity:\n",
    "$O(n)$\n",
    "\n",
    "- Space complexity:\n",
    "$O(1)$\n",
    "\n",
    "_Where $n$ is the size of the array._"
   ],
   "id": "4fba26f05867ab12"
  },
  {
   "metadata": {
    "executionRelatedData": {
     "compiledClasses": [
      "Line_25_jupyter",
      "Line_31_jupyter",
      "Line_28_jupyter",
      "Line_30_jupyter",
      "Line_27_jupyter",
      "Line_22_jupyter",
      "Line_23_jupyter",
      "Line_26_jupyter",
      "Line_29_jupyter",
      "Line_32_jupyter"
     ]
    }
   },
   "cell_type": "code",
   "source": [
    "fun maxArea(heights: IntArray): Int {\n",
    "    var maxArea = 0\n",
    "    var l = 0;\n",
    "    var r = heights.lastIndex;\n",
    "    while (l < r) {\n",
    "        val area = (r - l) * minOf(heights[l], heights[r])\n",
    "        maxArea = maxOf(area, maxArea)\n",
    "        if (heights[l] > heights[r]) r--\n",
    "        else l++\n",
    "    }\n",
    "    return maxArea\n",
    "}\n",
    "\n",
    "var heights = intArrayOf(1, 7, 2, 5, 4, 7, 3, 6)\n",
    "maxArea(heights)\n",
    "\n",
    "heights = intArrayOf(\n",
    "    1,\n",
    "    7,\n",
    "    2,\n",
    "    5,\n",
    "    12,\n",
    "    3,\n",
    "    500,\n",
    "    500,\n",
    "    7,\n",
    "    8,\n",
    "    4,\n",
    "    7,\n",
    "    3,\n",
    "    6,\n",
    ")\n",
    "maxArea(heights)"
   ],
   "id": "87d26992a3a138b8",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "# Trapping Rainwater\n",
    "\n",
    "> You are given an array of non-negative integers height which represent an elevation map. Each value `height[i]` represents the height of a bar, which has a width of 1.\n",
    ">\n",
    "> Return the maximum area of water that can be trapped between the bars.\n",
    "\n",
    "## Examples\n",
    "\n",
    "```\n",
    "Input: height = [0,2,0,3,1,0,1,3,2,1]\n",
    "Output: 9\n",
    "```\n",
    "\n",
    "## Solution 1 - Brute Force\n",
    "\n",
    "- Time complexity:\n",
    "$O(n^2)$\n",
    "\n",
    "- Space complexity:\n",
    "$O(n)$\n",
    "\n",
    "_Where $n$ is the size of the array._"
   ],
   "id": "bfbee9c384ad35"
  },
  {
   "metadata": {
    "executionRelatedData": {
     "compiledClasses": [
      "Line_20_jupyter",
      "Line_18_jupyter",
      "Line_17_jupyter",
      "Line_21_jupyter",
      "Line_16_jupyter",
      "Line_19_jupyter",
      "Line_22_jupyter"
     ]
    }
   },
   "cell_type": "code",
   "source": [
    "fun trap(height: IntArray): Int {\n",
    "    if (height.size <= 2) return 0\n",
    "    val volumes = IntArray(height.size)\n",
    "    for (i in 1 until height.lastIndex) {\n",
    "        val l = height.slice(0 until i).max()\n",
    "        val r = height.slice(i until height.size).max()\n",
    "        volumes[i] = minOf(l,r) - height[i]\n",
    "        print(\"|$i: $l,$r|\\t\")\n",
    "    }\n",
    "    println()\n",
    "    println(volumes.joinToString(\",\"))\n",
    "    return volumes.sum()\n",
    "}\n",
    "\n",
    "val input = intArrayOf(0, 2, 0, 3, 1, 0, 1, 3, 2, 1)\n",
    "trap(input)"
   ],
   "id": "9069ca5f4a032073",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## Solution 2 - Prefix & Suffix Array\n",
    "\n",
    "- Time complexity:\n",
    "$O(n)$\n",
    "\n",
    "- Space complexity:\n",
    "$O(n)$\n",
    "\n",
    "_Where $n$ is the size of `heights` array._"
   ],
   "id": "15a0bdf49c643838"
  },
  {
   "metadata": {
    "executionRelatedData": {
     "compiledClasses": [
      "Line_13_jupyter",
      "Line_5_jupyter",
      "Line_11_jupyter",
      "Line_4_jupyter",
      "Line_9_jupyter",
      "Line_12_jupyter",
      "Line_25_jupyter",
      "Line_24_jupyter",
      "Line_10_jupyter",
      "Line_8_jupyter",
      "Line_15_jupyter",
      "Line_6_jupyter",
      "Line_14_jupyter",
      "Line_23_jupyter",
      "Line_26_jupyter"
     ]
    }
   },
   "cell_type": "code",
   "source": [
    "fun trap(height: IntArray): Int {\n",
    "    if (height.size <= 2) return 0\n",
    "    val maxima = IntArray(height.size) { 0 }\n",
    "    var currMax = height[0]\n",
    "    maxima[0] = height[0]\n",
    "    for (i in 1 until height.lastIndex) { // forward pass\n",
    "        currMax = maxOf(currMax, height[i])\n",
    "        maxima[i] = currMax\n",
    "    }\n",
    "    currMax = height.last()\n",
    "    maxima[maxima.lastIndex] = height.last()\n",
    "    for (i in height.lastIndex - 1 downTo 1) {\n",
    "        currMax = maxOf(currMax, height[i])\n",
    "        maxima[i] = minOf(maxima[i], currMax)\n",
    "    }\n",
    "    for(i in maxima.indices) {\n",
    "        maxima[i] -= height[i]\n",
    "    }\n",
    "    return maxima.sum()\n",
    "}\n",
    "\n",
    "val input = intArrayOf(0, 2, 0, 3, 1, 0, 1, 3, 2, 1)\n",
    "trap(input)"
   ],
   "id": "137a995a0d97efac",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## Solution 3 - Stack\n",
    "\n",
    "- Time complexity:\n",
    "$O(n)$\n",
    "\n",
    "- Space complexity:\n",
    "$O(n)$\n",
    "\n",
    "_Where $n$ is the size of `heights` array._"
   ],
   "id": "8ff5e06e71f106f"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "fun trap(height: IntArray): Int {\n",
    "    if (height.size <= 2) return 0\n",
    "    var res = 0\n",
    "    val stack = ArrayDeque<Int>()\n",
    "\n",
    "    for (i in height.indices) {\n",
    "        while (stack.isNotEmpty() && height[i] > height[stack.first()]) {\n",
    "            val top = stack.removeFirst()\n",
    "            if (stack.isNotEmpty()) {\n",
    "                val left = stack.first()\n",
    "                val right = height[i]\n",
    "                val h = minOf(right, height[left]) - height[top]\n",
    "                val w = i - left - 1\n",
    "                res += h * w\n",
    "            }\n",
    "        }\n",
    "        stack.addFirst(i)\n",
    "    }\n",
    "    return res\n",
    "}"
   ],
   "id": "9969280d674f9b8c",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## Solution 4 - 2 Pointers\n",
    "\n",
    "- Time complexity:\n",
    "$O(n)$\n",
    "\n",
    "- Space complexity:\n",
    "$O(1)$\n",
    "\n",
    "_Where $n$ is the size of `heights` array._"
   ],
   "id": "ca64aba18fadc653"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "fun trap(height: IntArray): Int {\n",
    "    if (height.size <= 2) return 0\n",
    "    var res = 0\n",
    "    var l = 0\n",
    "    var r = height.lastIndex\n",
    "    var leftMax = height[l]\n",
    "    var rightMax = height[r]\n",
    "    while (l < r) {\n",
    "        if (leftMax < rightMax) {\n",
    "            l++\n",
    "            leftMax = maxOf(leftMax, height[l])\n",
    "            res += leftMax - height[l]\n",
    "        } else {\n",
    "            r--\n",
    "            rightMax = maxOf(rightMax, height[r])\n",
    "            res += rightMax - height[r]\n",
    "        }\n",
    "    }\n",
    "    return res\n",
    "}"
   ],
   "id": "1379f8740c5382c1",
   "outputs": [],
   "execution_count": null
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Kotlin",
   "language": "kotlin",
   "name": "kotlin"
  },
  "language_info": {
   "name": "kotlin",
   "version": "2.2.20",
   "mimetype": "text/x-kotlin",
   "file_extension": ".kt",
   "pygments_lexer": "kotlin",
   "codemirror_mode": "text/x-kotlin",
   "nbconvert_exporter": ""
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}