Stack.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "e1e18c56",
   "metadata": {},
   "source": [
    "# Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cf057a1a",
   "metadata": {},
   "source": [
    "## Valid Parentheses\n",
    "\n",
    "* https://leetcode.com/problems/valid-parentheses/\n",
    "***\n",
    "* Time Complexity: O(n)\n",
    "    - have to traverse through the entire string in order to determine if it's valid\n",
    "* Space Complexity: O(n)\n",
    "    - on average, you'll probably add n/2 elements into the stack and in the worst case scenario in which the whole string is open brackets, it'll have n elements\n",
    "***\n",
    "* when you want to look at the last thing that happened, like what was the last open parentheses, in order, use a stack\n",
    "    - LIFO order\n",
    "    - helps reverse things and looks at a timeline of most recent --> oldest\n",
    "* in our case, we want to know what the most recent open bracket was added so we can simply pop from the stack and compare it to the current closing bracket"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "f25e9fe2",
   "metadata": {},
   "outputs": [],
   "source": [
    "/**\n",
    " * @param {string} s\n",
    " * @return {boolean}\n",
    " */\n",
    "var isValid = function(s) {\n",
    "    if (s.length === 1) return false;\n",
    "    \n",
    "    const closingBracket = {\n",
    "        '(' : ')',\n",
    "        '{' : '}',\n",
    "        '[' : ']'\n",
    "    };\n",
    "    \n",
    "    const stack = [];\n",
    "    \n",
    "    for (let i = 0; i < s.length; i++) {\n",
    "        let bracket = s[i];\n",
    "        \n",
    "        if (bracket === '(' || bracket === '{' || bracket === '[') {\n",
    "            stack.push(bracket);\n",
    "        }\n",
    "        else {\n",
    "            let lastOpen = stack.pop();\n",
    "            if (closingBracket[lastOpen] !== bracket) return false;\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    return stack.length === 0;\n",
    "};"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c4999814",
   "metadata": {},
   "source": [
    "## Min Stack\n",
    "\n",
    "* https://leetcode.com/problems/min-stack/\n",
    "***\n",
    "* Time Complexity of getMin(): O(1)\n",
    "    - we keep track of the the most recent minimum to the oldest minimum so all we have to do is return the last item in the min stack which is O(1)\n",
    "* Space Complexity: O(n)\n",
    "    - since we add elements into the min stack, we'll have at most O(n) elements since if the elements are in descending order, you'll be adding all elements into the stack\n",
    "***\n",
    "* like with the Valid Parentheses problem, we want to look at the current minimum but also the minimums that were added BEFORE as well\n",
    "    - this is b/c if you pop the latest minimum from the stack, then you'll be able to know the minimum that was added before it\n",
    "    - so if you added -2, 0, -3 and popped -3, the latest minimum is -2.\n",
    "    - using just 1 variable to keep track of it would not work!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "11475337",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function (anonymous)]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "var MinStack = function() {\n",
    "    this.min = [];\n",
    "    this.stack = [];\n",
    "};\n",
    "\n",
    "/** \n",
    " * @param {number} val\n",
    " * @return {void}\n",
    " */\n",
    "MinStack.prototype.push = function(val) {\n",
    "    this.stack.push(val);\n",
    "    \n",
    "    if (this.min.length === 0) {\n",
    "        this.min.push(val);\n",
    "    }\n",
    "    else if (val <= this.min[this.min.length - 1]) {\n",
    "        this.min.push(val);\n",
    "    }\n",
    "};\n",
    "\n",
    "/**\n",
    " * @return {void}\n",
    " */\n",
    "MinStack.prototype.pop = function() {\n",
    "    const retVal = this.stack.pop();\n",
    "    if (retVal === this.min[this.min.length - 1]) this.min.pop();\n",
    "    return retVal;\n",
    "};\n",
    "\n",
    "/**\n",
    " * @return {number}\n",
    " */\n",
    "MinStack.prototype.top = function() {\n",
    "    return this.stack[this.stack.length - 1]; \n",
    "};\n",
    "\n",
    "/**\n",
    " * @return {number}\n",
    " */\n",
    "MinStack.prototype.getMin = function() {\n",
    "    return this.min[this.min.length - 1];\n",
    "};\n",
    "\n",
    "/** \n",
    " * Your MinStack object will be instantiated and called as such:\n",
    " * var obj = new MinStack()\n",
    " * obj.push(val)\n",
    " * obj.pop()\n",
    " * var param_3 = obj.top()\n",
    " * var param_4 = obj.getMin()\n",
    " */"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f2d0d0b2",
   "metadata": {},
   "source": [
    "# Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a8bdd9ca",
   "metadata": {},
   "source": [
    "## Evaluate Reverse Polish Notation\n",
    "\n",
    "* https://leetcode.com/problems/evaluate-reverse-polish-notation/\n",
    "***\n",
    "* Time Complexity: O(n)\n",
    "    - have to iterate through the array in order to evaluate it\n",
    "    - pushing/popping from the stack is an O(1) operation\n",
    "* Space Complexity: O(1)\n",
    "    - you'll have at most 2 items in the stack b/c if you reach an operator, those 2 items will be popped out of the stack and its result will be pushed in\n",
    "***\n",
    "* READ IT FROM LEFT TO RIGHT\n",
    "* IF IT'S A NUMBER, PUSH IT TO THE STACK\n",
    "* ELSE, WE POP 2 NUMBERS FROM THE STACK B/C WE NEED 2 OPERANDS FOR AN OPERATOR TO WORK\n",
    "* THEN WE PUSH THAT RESULT BACK INTO THE STACK"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "02cc5afd",
   "metadata": {},
   "outputs": [],
   "source": [
    "/**\n",
    " * @param {string[]} tokens\n",
    " * @return {number}\n",
    " */\n",
    "\n",
    "var evalRPN = function(tokens) {\n",
    "    const operations = {\n",
    "        \"+\": function(op1, op2) {return op1 + op2},\n",
    "        \"-\": function(op1, op2) {return op1 - op2},\n",
    "        \"*\": function(op1, op2) {return op1 * op2},\n",
    "        \"/\": function(op1, op2) {return Math.trunc(op1 / op2)}\n",
    "    }\n",
    "    \n",
    "    let stack = [];\n",
    "    for (let i = 0; i < tokens.length; i++) {\n",
    "        let item = tokens[i];\n",
    "        if (operations[item] !== undefined) {\n",
    "            let op2 = stack.pop();\n",
    "            let op1 = stack.pop();\n",
    "            stack.push(operations[item](op1, op2));\n",
    "        }\n",
    "        else {\n",
    "            stack.push(Number(item));\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    return stack.pop();\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "54c1339e",
   "metadata": {},
   "source": [
    "## Generate Parentheses\n",
    "\n",
    "* https://leetcode.com/problems/generate-parentheses/\n",
    "***\n",
    "* Time Complexity: O(2$^{2n}$)\n",
    "    - reason being, when you create the recursion tree, you'll decide whether to add a ( or a ) so you have 2 options for every node\n",
    "* Space Complexity: O(n)\n",
    "    - since we are using recursion, the function stack will only be called at most n times. you can see this when you're doing the recursion tree.\n",
    "***\n",
    "* ANY TIME YOU NEED TO DO SOMETHING WITH STACKS, DRAW OUT A RECURSION TREE AND THINK ABOUT DOING IT RECURSIVELY\n",
    "* ONCE YOU HAVE THAT FIGURED OUT, THEN ACTUALLY TRY TO DO IT ITERATIVELY WITH A STACK\n",
    "* IT IS SO MUCH EASIER ONCE YOU VISUALIZE THE TREE AND USE BACKTRACKING!!!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "bb6b1a95",
   "metadata": {},
   "outputs": [],
   "source": [
    "/**\n",
    " * @param {number} n\n",
    " * @return {string[]}\n",
    " */\n",
    "var generateParenthesis = function(n) {\n",
    "    let res = [];\n",
    "    const traverse = (str, open, close) => {\n",
    "        // if there are more open parentheses than close,\n",
    "        // then the combination is NOT valid\n",
    "        if (open > close) {\n",
    "            return;\n",
    "        }\n",
    "        \n",
    "        // if there are no more parentheses to push\n",
    "        // then add it to the output array\n",
    "        if (open === 0 && close === 0) {\n",
    "            res.push(str);\n",
    "            return;\n",
    "        }\n",
    "        \n",
    "        // if there are open parentheses left\n",
    "        // add it to the string\n",
    "        // b/c this will always be valid\n",
    "        if (open > 0) {\n",
    "            traverse(`${str}(`, open - 1, close);\n",
    "        }\n",
    "        // if there are no more open parentheses left\n",
    "        // then we can start closing them\n",
    "        if (close > 0) {\n",
    "            traverse(`${str})`, open, close - 1);\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    traverse(\"\", n, n);\n",
    "    return res;\n",
    "};"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0d779399",
   "metadata": {},
   "source": [
    "## Daily Temperatures\n",
    "\n",
    "* https://leetcode.com/problems/daily-temperatures/\n",
    "***\n",
    "* Time Complexity: O(n)\n",
    "    - traverse through the array from 0 ... n\n",
    "    - and you might have to backtrack a little with the stack but the stack's size is always gonna be < n \n",
    "* Space Complexity: O(n)\n",
    "    - the size of the stack is bounded by n. it will never be bigger than that\n",
    "    - as you traverse through the temperature array, you'll also be popping things from the stack\n",
    "***\n",
    "* USE A STACK TO KEEP TRACK OF ANY PROBLEMS THAT YOU HAVEN'T SOLVED BEFORE\n",
    "* IF YOU CAN'T SOLVE THE CURRENT PROBLEM, PUT IT INTO THE STACK\n",
    "* THEN ONCE YOU CAN SOLVE IT, CONTINUALLY POP IT FROM THE STACK, SOLVE IT, THEN MOVE ON"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "59c98f73",
   "metadata": {},
   "outputs": [],
   "source": [
    "/**\n",
    " * @param {number[]} temperatures\n",
    " * @return {number[]}\n",
    " */\n",
    "\n",
    "var dailyTemperatures = function(temperatures) {\n",
    "    const output = [];\n",
    "    const stack = [];\n",
    "\n",
    "    for (let i = 0; i < temperatures.length; i++) {\n",
    "        output.push(0);\n",
    "        while (stack.length > 0) {\n",
    "            // check top of stack\n",
    "            // if the current temp is greater than stack, then pop it off\n",
    "            // and update the output\n",
    "            let stackTop = stack[stack.length - 1];\n",
    "            if (temperatures[i] > temperatures[stackTop]) {\n",
    "                output[stackTop] = i - stackTop;\n",
    "                stack.pop();\n",
    "            }\n",
    "            else {\n",
    "                break;\n",
    "            }\n",
    "        }\n",
    "\n",
    "        // push current index into the stack\n",
    "        stack.push(i);\n",
    "    }\n",
    "    return output;\n",
    "};"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b0904b5d",
   "metadata": {},
   "source": [
    "## Car Fleet\n",
    "\n",
    "* https://leetcode.com/problems/car-fleet/\n",
    "***\n",
    "* Time Complexity: O(nlogn)\n",
    "    - you need to sort the position array in descending order (largest items at front of the array)\n",
    "    - then you loop through the position array and calculate the amount of time it would take to get there\n",
    "* Space Complexity: O(n)\n",
    "    - create a hash table to map newly sorted positions with their speeds\n",
    "    - and you need an output stack\n",
    "***\n",
    "* sort the position array to make things easier\n",
    "* use a stack and check the top of the stack and either append to it or pop it"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "178c15d6",
   "metadata": {},
   "outputs": [],
   "source": [
    "/**\n",
    " * @param {number} target\n",
    " * @param {number[]} position\n",
    " * @param {number[]} speed\n",
    " * @return {number}\n",
    " */\n",
    "var carFleet = function(target, position, speed) {\n",
    "    let hash = {};\n",
    "    \n",
    "    // creates a hash table to map positions to speed\n",
    "    // since we can't rely on the index anymore\n",
    "    // once we sort the positions array\n",
    "    for (let i = 0; i < position.length; i++) {\n",
    "        hash[position[i]] = speed[i];\n",
    "    }\n",
    "    \n",
    "    position.sort((a, b) => b - a);\n",
    "    \n",
    "    let stack = [];\n",
    "    for (let i = 0; i < position.length; i++) {\n",
    "        // basically the amount of time it takes for cars to get to their destination\n",
    "        // for example, target = 12, pos = [10] speed = [2];\n",
    "        // (12 - 10) / 2 = 1, so that car is 2 miles away and it's going at 2 mph\n",
    "        // it'll take 1 hour to get there\n",
    "        let diff = (target - position[i]) / hash[position[i]];\n",
    "        \n",
    "        if (stack.length === 0) {\n",
    "            stack.push(diff);\n",
    "        }\n",
    "        // if the current car is way behind the cars in front of it\n",
    "        // it'll never catch up and be its own car fleet\n",
    "        // but if the current car is moving very fast and will catch up,\n",
    "        // then it'll join the car in front as a fleet\n",
    "        else if (diff > stack[stack.length - 1]) {\n",
    "            stack.push(diff);\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    return stack.length;\n",
    "};"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d238789d",
   "metadata": {},
   "source": [
    "## Validate Stack Sequences\n",
    "\n",
    "* https://leetcode.com/problems/validate-stack-sequences/description/\n",
    "***\n",
    "* Time Complexity: O(n)\n",
    "    - pushed and popped are the same length since they're just permutations of each other\n",
    "    - you will traverse all of pushed and all of popped so it's O(2n) = O(n)\n",
    "* Space Complexity: O(n) with stack, O(1) using pushed as stack\n",
    "    - you can push/pop from a stack to find the answer\n",
    "    - using pushed as a stack will just overwrite its earlier values\n",
    "***\n",
    "* we iterate through pushed and push the values into a stack\n",
    "* we also keep a pointer in popped as well\n",
    "* if we get to a pushed value that was also popped, so if pushed[i] === popped[j]\n",
    "    - we will not push that value but instead see if there are others in the stack that can be popped after j\n",
    "    - so we enter a while loop for this where we continually pop from the stack and increment j\n",
    "* for the space-optimized version, the concept is the same except pushed can be used as the stack\n",
    "    - we just have another pointer to keep track of where the top of the stack is and rewrite the values with later values of pushed\n",
    "    - then once we meet the condition of pushed === popped, instead of actually popping, we just decrement pointer that points to the top of the stack\n",
    "        * this effectively pops b/c we overwrite those values anyway\n",
    "    - then once we've finished traversing both, we check if i === 0.\n",
    "        * when i = 0 that means the stack is empty"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "bc11b464",
   "metadata": {},
   "outputs": [],
   "source": [
    "/**\n",
    " * @param {number[]} pushed\n",
    " * @param {number[]} popped\n",
    " * @return {boolean}\n",
    " */\n",
    "var validateStackSequences = function(pushed, popped) {\n",
    "    const stack = [];\n",
    "\n",
    "    let j = 0;\n",
    "    for (let i = 0; i < pushed.length; i++) {\n",
    "        // remember that pushed and popped are INTEGER ARRAYS, NOT STACKS\n",
    "        // so if we traverse them from L --> R, we can see the order of pushed and popped\n",
    "\n",
    "        // if we pushed and then immediately popped, then this will guarantee\n",
    "        // the items we pushed beforehand will also be popped off\n",
    "\n",
    "        // e.g. \n",
    "        // pushed = [1, 2, 0, 3, 4]\n",
    "        // popped = [0, 2, 1, 4, 3]\n",
    "        // stack = [1, 2]\n",
    "        // and once we get to i = 2 and j = 0, we see that pushed (0) === popped (0)\n",
    "        // so then we enter our while loop\n",
    "        // j = 1, 2 is at the top of our stack so we pop\n",
    "        // j = 2, 1 is now at the top of our stack so we pop\n",
    "        // j = 3, stack is empty now []\n",
    "        if (pushed[i] === popped[j]) {\n",
    "            j++;\n",
    "            while((stack.length > 0) && (stack[stack.length - 1] === popped[j])) {\n",
    "                stack.pop();\n",
    "                j++;\n",
    "            }\n",
    "        }\n",
    "        else {\n",
    "            stack.push(pushed[i]);\n",
    "        }\n",
    "    }\n",
    "\n",
    "    return stack.length === 0;\n",
    "}\n",
    "\n",
    "// space - efficient\n",
    "var validateStackSequences = function(pushed, popped) {\n",
    "    let i = 0;\n",
    "    let j = 0;\n",
    "\n",
    "    for (const val of pushed) {\n",
    "        // this overwrites pushed and treats it as a stack\n",
    "        pushed[i] = val;\n",
    "        i++;\n",
    "\n",
    "        // essentially the same as above\n",
    "        while (i > 0 && pushed[i - 1] === popped[j]) {\n",
    "            // decrementing i effectively removes a value from our \"stack\"\n",
    "            // since we overwrite it later\n",
    "            i--;\n",
    "            j++;\n",
    "        }\n",
    "    }\n",
    "\n",
    "    // if we are back at i, that means we have \"popped\" everything from our \"stack\"\n",
    "    return i === 0;\n",
    "}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f800b524",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5c279eb9",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e5e99a2d",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "JavaScript (Node.js)",
   "language": "javascript",
   "name": "javascript"
  },
  "language_info": {
   "file_extension": ".js",
   "mimetype": "application/javascript",
   "name": "javascript",
   "version": "16.14.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}