Math and Geometry.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "868a71ab",
   "metadata": {},
   "source": [
    "# Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0bf45d3e",
   "metadata": {},
   "source": [
    "## Happy Number\n",
    "\n",
    "* https://leetcode.com/problems/happy-number/description/\n",
    "***\n",
    "* Time Complexity: N/A\n",
    "    - not easily determined due to how calculating the Happy Number works\n",
    "    - since you continually sum the square of the digits until you either reach a number you've seen or 1, you cannot determine the time complexity easily\n",
    "* Space Complexity: O(1)\n",
    "    - only requires a couple of variables\n",
    "***\n",
    "* my initial algorithm was to do follow the steps for finding the Happy Number but keeping track of numbers we've seen using a Set\n",
    "    - this led to an O(n) space algorithm\n",
    "* but this can be improved upon by realizing that we're trying to find a cycle and can use the Floyd Cycle Detection algorithm (Tortoise and Hare)\n",
    "    - to do this, we have a slow pointer and a fast pointer\n",
    "    - the slow pointer only does a single Happy Number operation once while the fast pointer does it twice\n",
    "    - if they both end up being equal, you'll know that you've detected a cycle\n",
    "    - else, if either slow or fast are 1, then you've found the Happy Number"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "93fcbff7",
   "metadata": {},
   "outputs": [],
   "source": [
    "/**\n",
    " * @param {number} n\n",
    " * @return {boolean}\n",
    " */\n",
    "\n",
    "\n",
    "// time: # of times it takes to get a happy number or loop\n",
    "// space: O(time)\n",
    "var isHappy = function(n) {\n",
    "    if (n === 1) return true;\n",
    "\n",
    "    const seen = new Set();\n",
    "\n",
    "    do {\n",
    "        seen.add(n);\n",
    "\n",
    "        // stringify\n",
    "        const num = `${n}`;\n",
    "\n",
    "        // for every digit square it and stringify\n",
    "        let sum = 0;\n",
    "        for (let i = 0; i < num.length; i++) {\n",
    "            sum += Math.pow(Number(num[i]), 2);\n",
    "        }\n",
    "\n",
    "        // console.log({sum})\n",
    "        if (sum === 1) return true;\n",
    "\n",
    "        n = sum;\n",
    "    } while(!seen.has(n));\n",
    "\n",
    "    return false;\n",
    "};\n",
    "\n",
    "var squareSum = function(n) {\n",
    "    let sum = 0;\n",
    "    let temp;\n",
    "\n",
    "    while (n) {\n",
    "        // grabs the rightmost digit\n",
    "        temp = n % 10;\n",
    "\n",
    "        // adds square of digit\n",
    "        sum += temp * temp;\n",
    "\n",
    "        // does a right shift >>\n",
    "        n = Math.trunc(n / 10);\n",
    "    }\n",
    "\n",
    "    return sum;\n",
    "}\n",
    "\n",
    "// time: same as above\n",
    "// space: O(1)\n",
    "var isHappy = function(n) {\n",
    "    if (n === 1) return true;\n",
    "    let slow = n;\n",
    "    let fast = n;\n",
    "\n",
    "    do {\n",
    "        slow = squareSum(slow);\n",
    "        fast = squareSum(fast);\n",
    "        fast = squareSum(fast);\n",
    "\n",
    "        if (slow === 1 || fast === 1) return true;\n",
    "    } while(slow !== fast);\n",
    "\n",
    "    return false;\n",
    "};"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c0dfa7d3",
   "metadata": {},
   "source": [
    "## Plus One\n",
    "\n",
    "* https://leetcode.com/problems/plus-one/submissions/948120431/\n",
    "***\n",
    "* Time Complexity: O(n)\n",
    "    - might have to traverse through every digit in the arr, O(n)\n",
    "    - unshift operation is O(n)\n",
    "* Space Complexity: O(1)\n",
    "    - no extra memory was used\n",
    "    - all operations were done with the digits arr that was given\n",
    "***\n",
    "* looping from the end of the arr, if we find a digit that is less than 9, we can add 1 to it and return the digit arr\n",
    "    - this is b/c we don't have to carry the one\n",
    "    - if we do find a 9, we continue iterating but replace its position with a 0\n",
    "* if we make it all the way to the beginning of the arr, we know that we must add a 1 to the beginning of it\n",
    "    - e.g. [9,9,9] + 1 = [1,0,0,0]\n",
    "    - unshift is faster than spread operator (...)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f2b05a50",
   "metadata": {},
   "outputs": [],
   "source": [
    "/**\n",
    " * @param {number[]} digits\n",
    " * @return {number[]}\n",
    " */\n",
    "\n",
    "// the JavaScript way\n",
    "var plusOne = function(digits) {\n",
    "    // turn into number and add 1\n",
    "    // we have a case where the number is too big to use with Number()\n",
    "    // BigInt will handle that case\n",
    "    let num = BigInt(digits.join(\"\"));\n",
    "    num++;\n",
    "\n",
    "    // turn back into num arr\n",
    "    num = `${num}`.split(\"\");\n",
    "    num.forEach(val => Number(val));\n",
    "\n",
    "    return num;\n",
    "};\n",
    "\n",
    "// the smarter way\n",
    "var plusOne = function(digits) {\n",
    "    for (let i = digits.length - 1; i >= 0; i--) {\n",
    "        // we can add 1 to it \n",
    "        if (digits[i] < 9) {\n",
    "            // we can return immediately if it's not 9 b/c we do not need to carry over any 1s\n",
    "            digits[i]++;\n",
    "            return digits;\n",
    "        }\n",
    "\n",
    "        // or set current digit to 0\n",
    "        digits[i] = 0;\n",
    "    }\n",
    "\n",
    "    // we know that if we made it all the way to the first digit without returning\n",
    "    // that we must have to carry something over\n",
    "    digits.unshift(1);\n",
    "    return digits;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9574626a",
   "metadata": {},
   "source": [
    "# Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aeb9e1c7",
   "metadata": {},
   "source": [
    "## Rotate Image\n",
    "\n",
    "* https://leetcode.com/problems/rotate-image/description/\n",
    "***\n",
    "* Time Complexity: O(n$^{2}$)\n",
    "    - you're traversing around half of the matrix which is (n * n) / 2\n",
    "* Space Complexity: O(1)\n",
    "    - only requires space for a couple of variables\n",
    "***\n",
    "* we can think of this like peeling an onion layer by layer\n",
    "* we start off with the outermost layer and work in until we reach the halfway point\n",
    "    - reason being, if we go any further, we would've already rotated those indices and it would return an incorrect answer\n",
    "* we also rotate starting from the bottom-left first\n",
    "    - if we start rotating from the top-left, we would have to keep reassigning a temp variable\n",
    "    - but if we start from the bottom-left, we would only need a temp variable for the top-left\n",
    "        * this is a slight optimization\n",
    "* in order to rotate, we have to do 2 things:\n",
    "    1. we switch the current column and row. so row = column and column = row\n",
    "    2. we then calculate a new column using the old row\n",
    "        * n - r - 1\n",
    "        * this represents how much the cell is offset from one of the corners\n",
    "            - e.g. how offset from top-left corner, top-right corner, bottom-right corner, and bottom-left corner respectively"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "f9d18b04",
   "metadata": {},
   "outputs": [],
   "source": [
    "/**\n",
    " * @param {number[][]} matrix\n",
    " * @return {void} Do not return anything, modify matrix in-place instead.\n",
    " */\n",
    "\n",
    "const rotatePos = (n, r, c) => {\n",
    "    // n - r - 1 represents how much to offset from one of the corners\n",
    "    // so if we have [0, 1], we would rotate to [1, 2]\n",
    "    // [0, 1] is one position away from [0,0], the top-left corner\n",
    "    // so if we rotate it 90 degrees, [1,2] is 1 position away from [0,2], which is the top-right corner\n",
    "    return [c, n - r - 1];\n",
    "}\n",
    "\n",
    "var rotate = function(matrix) {\n",
    "    const n = matrix.length;\n",
    "\n",
    "    // don't have to rotate anything\n",
    "    if (n === 1) return;\n",
    "\n",
    "    // you only care about the top half of the rows\n",
    "    // this is b/c by the time you reach the 2nd half, the matrix is already rotated there\n",
    "    for (let r = 0; r < ((n - 1) / 2); r++) {\n",
    "        \n",
    "        // think of it like the layers of an onion\n",
    "        // if you rotated the outer layer of an onion first\n",
    "        // you only care about the inner layers now\n",
    "        // in this case, n - r - 1 accounts for the outer layers that you've already seen\n",
    "        // e.g. if you started at layer 1, which is at r = 0, c: range(0, n)\n",
    "        // then when you look at layer 2, you look at r = 1, c: range(1, n - 0 - 1);\n",
    "        for (let c = r; c < n - r - 1; c++) {\n",
    "            let temp = matrix[r][c];\n",
    "            let [rR, cR] = rotatePos(n ,r, c);\n",
    "            let [rB, cB] = rotatePos(n, rR, cR);\n",
    "            let [rL, cL] = rotatePos(n, rB, cB);\n",
    "\n",
    "            // starts rotating from bottom-left to top-left\n",
    "            // this is so that only 1 temp variable is needed rather than having to reassign it\n",
    "            // multiple times\n",
    "            matrix[r][c] = matrix[rL][cL];\n",
    "            matrix[rL][cL] = matrix[rB][cB];\n",
    "            matrix[rB][cB] = matrix[rR][cR];\n",
    "            matrix[rR][cR] = temp;\n",
    "        }\n",
    "    }\n",
    "};"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "153b35a7",
   "metadata": {},
   "source": [
    "## Spiral Matrix\n",
    "\n",
    "* https://leetcode.com/problems/spiral-matrix/description/\n",
    "***\n",
    "* Time Complexity: O(n * m), n = numRows, m = numCols\n",
    "    - have to traverse through every cell in the matrix at most once to add it to the res array\n",
    "* Space Complexity: O(n * m)\n",
    "    - res array contains all cells in the matrix but in spiral order\n",
    "***\n",
    "* have multiple variables to denote the top, bottom, left, and right boundaries that will be updated\n",
    "* think of this algorithm like peeling an onion\n",
    "    - left --> right @ top row\n",
    "    - top --> bottom @ right col\n",
    "    - right --> left @ bottom row\n",
    "    - bottom --> top @ left col\n",
    "* once we are done with the outer layer of the matrix, we move inwards by updating the variables"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "16ca5465",
   "metadata": {},
   "outputs": [],
   "source": [
    "/**\n",
    " * @param {number[][]} matrix\n",
    " * @return {number[]}\n",
    " */\n",
    "\n",
    "var spiralOrder = function(matrix) {\n",
    "    const res = [];\n",
    "    const numRows = matrix.length;\n",
    "    const numCols = matrix[0].length;\n",
    "    const matrixSize = numRows * numCols;\n",
    "\n",
    "    let top = 0;\n",
    "    let bottom = numRows - 1;\n",
    "    let left = 0;\n",
    "    let right = numCols - 1;\n",
    "\n",
    "    while (res.length < matrixSize) {\n",
    "        \n",
    "        // left --> right at top row\n",
    "        for (let c = left; c <= right && res.length < matrixSize; c++) {\n",
    "            res.push(matrix[top][c]);\n",
    "        }\n",
    "\n",
    "        // top --> bottom at rightmost column\n",
    "        // top + 1 is essentially us moving down a row\n",
    "        // this is so that we do not count the top-right corner twice\n",
    "\n",
    "        // this is also why we do bottom - 1\n",
    "        // we do not want to count the bottom-right corner twice\n",
    "        // and allows the next for-loop to go from right --> left without +/- 1\n",
    "        for (let r = top + 1; r <= bottom - 1 && res.length < matrixSize; r++) {\n",
    "            res.push(matrix[r][right]);\n",
    "        }\n",
    "\n",
    "        // right --> left at bottom row\n",
    "        for (let c = right; c >= left && res.length < matrixSize; c--) {\n",
    "            res.push(matrix[bottom][c]);\n",
    "        }\n",
    "\n",
    "        // bottom --> top at leftmost column\n",
    "        \n",
    "        // bottom - 1 so that we do not count the bottom-left corner twice\n",
    "        // top + 1 so that we do not count the top-left corner twice\n",
    "        for (let r = bottom - 1; r >= top + 1 && res.length < matrixSize; r--) {\n",
    "            res.push(matrix[r][left]);\n",
    "        }\n",
    "\n",
    "        // similar to Rotate Image\n",
    "        // once we are done getting the spiral order of the matrix's outer layer\n",
    "        // we peel it like an onion and move onto the inner layers\n",
    "        top++;\n",
    "        bottom--;\n",
    "        left++;\n",
    "        right--;\n",
    "    }\n",
    "\n",
    "    return res;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6487bf12",
   "metadata": {},
   "source": [
    "## Set Matrix Zeroes\n",
    "\n",
    "* https://leetcode.com/problems/set-matrix-zeroes/description/\n",
    "***\n",
    "* Time Complexity: O(n * m), where n = numRows, m = numCols\n",
    "    - have to traverse the entire matrix to determine which cells have a 0 in them\n",
    "    - also need to traverse the matrix and 0 out any cells with a 0 in its col/row\n",
    "* Space Complexity: O(1)\n",
    "    - we use the matrix itself to keep track of the state of rows/cols that need to be zeroed out\n",
    "    - we also use a variable, isCol0, to determine if any cells in col 0 need to be zeroed out\n",
    "***\n",
    "* we traverse the matrix and take note of which cells have a 0 in them\n",
    "    - we use the 0th col to mark the rows that we need zeroed out and the 0th row to mark the cols\n",
    "    - but we also need a variable, isCol0, to determine if col 0 needs to be zeroed out as well\n",
    "        * reason being, since we use col 0 to keep track of rows, any time we check it, there's ALWAYS going to be a 0 in that column, so it would always be zeroed out by default if we aren't careful\n",
    "        * therefore, we need that boolean to make sure that col 0 is zeroed out only if there was a 0 in there originally\n",
    "* once we've done that first traversal, we do a bottom-up traversal of the matrix\n",
    "    - reason being, we use the top row to keep track of the 0s in each column so it wouldn't make sense to write over it and potentially make the whole matrix into 0s\n",
    "    - we also only go from [numCols - 1...1] and not to 0 b/c we already have isCol0 to check if col 0 needs to be zeroed out\n",
    "    - if we check at c = 0 in the loop and we zeroed out a previous row already, then it would automatically zero it out even though it shouldn't have"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "e4563aae",
   "metadata": {},
   "outputs": [],
   "source": [
    "/**\n",
    " * @param {number[][]} matrix\n",
    " * @return {void} Do not return anything, modify matrix in-place instead.\n",
    " */\n",
    "\n",
    " // time: O(m * n)\n",
    " // space: O(m + n)\n",
    "var setZeroes = function(matrix) {\n",
    "    const numRows = matrix.length;\n",
    "    const numCols = matrix[0].length;\n",
    "\n",
    "    const rows = new Set();\n",
    "    const cols = new Set();\n",
    "\n",
    "    // traverse through matrix and add rows/cols to their set if matrix[r][c] = 0;\n",
    "    for (let r = 0; r < numRows; r++) {\n",
    "        for (let c = 0; c < numCols; c++) {\n",
    "            if (matrix[r][c] === 0) {\n",
    "                rows.add(r);\n",
    "                cols.add(c);\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "\n",
    "    for (let r = 0; r < numRows; r++) {\n",
    "        for (let c = 0; c < numCols; c++) {\n",
    "            if (rows.has(r) || cols.has(c)) {\n",
    "                matrix[r][c] = 0;\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "};\n",
    "\n",
    " // time: O(m * n)\n",
    " // space: O(1)\n",
    "var setZeroes = function(matrix) {\n",
    "    const numRows = matrix.length;\n",
    "    const numCols = matrix[0].length;\n",
    "\n",
    "    // col = 0 keeps track of the state of the rows\n",
    "    // so we require this variable to keep track of col0 to make sure\n",
    "    // that 0s are not assigned here unnecessarily\n",
    "    // for example, if you have to zero out the bottom row b/c a 0 was at matrix[n - 1][0]\n",
    "    // THIS DOES NOT MEAN THAT YOU SHOULD ZERO OUT THE COL 0, even though there is a zero there\n",
    "    // but it's a zero there AFTER you've zeroed out that row\n",
    "    let isCol0 = false;\n",
    "\n",
    "    // traverse through matrix and add rows/cols to their set if matrix[r][c] = 0;\n",
    "    for (let r = 0; r < numRows; r++) {\n",
    "        // check if the first column has a 0 in it\n",
    "        if (matrix[r][0] === 0) {\n",
    "            isCol0 = true;\n",
    "        }  \n",
    "        for (let c = 1; c < numCols; c++) {\n",
    "            if (matrix[r][c] === 0) {\n",
    "                // leftmost col marks the rows\n",
    "                matrix[r][0] = 0;\n",
    "\n",
    "                // topmost row marks the cols\n",
    "                matrix[0][c] = 0;\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "\n",
    "    // traverse the matrix from the bottom-up\n",
    "    // then you want to check if matrix is 0 at row or col level\n",
    "    for (let r = numRows - 1; r >= 0; r--) {\n",
    "\n",
    "        // we already have a col0 bool so we do not have to iterate to c = 0\n",
    "        // if we go from numCols - 1 ... 0, we would actually zero out the col 0 unnecessarily\n",
    "        // this is b/c if we have recently zeroed out a row at the bottom, then every row\n",
    "        // at the top will count that 0 even though it was added recently and not part of the\n",
    "        // original matrix!!!\n",
    "\n",
    "        // that's why we require the isCol0 bool\n",
    "        // b/c we do not go to col 0 in this for loop we need some way to set it\n",
    "        // if a 0 is supposed to be there\n",
    "        for (let c = numCols - 1; c >= 1; c--) {\n",
    "            if (matrix[r][0] === 0 || matrix[0][c] === 0) {\n",
    "                matrix[r][c] = 0;\n",
    "            }\n",
    "        }\n",
    "\n",
    "        if (isCol0) {\n",
    "            matrix[r][0] = 0; \n",
    "        }\n",
    "    } \n",
    "};"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "becca2fb",
   "metadata": {},
   "source": [
    "## Pow(x,n)\n",
    "\n",
    "* https://leetcode.com/problems/powx-n/description/\n",
    "***\n",
    "* Time Complexity: O(logn)\n",
    "    - using bit manipulation to right shift (>>) n until it reaches 0\n",
    "* Space Complexity: O(1)\n",
    "    - only requires space for a couple of variables\n",
    "***\n",
    "* similar to how you generate the power set using bit manipulation\n",
    "* using the binary representation of n (the exponent), you can look at its digit places and multiply x (the number we want the power of) to the result every time a bit is set at its place\n",
    "    - e.g. if x = 2 and n = 5, our binary representation of n = 101\n",
    "        * which means we would do (2^4) * (2^1) only\n",
    "        * every right shift builds that number up,\n",
    "            - e.g. 101\n",
    "                * 101 = 2^1\n",
    "                * 010 = (2^1) * (2^1) = (2^2)\n",
    "                * 001 = (2^2) * (2^2) = (2^4)\n",
    "    - this allows for logarithmic performance rather than linear\n",
    "        * in the case where n = the max int for a 32 bit integer, this would yield 31 iterations until n reaches 0 rather than doing about ~2 billion"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "393f085a",
   "metadata": {},
   "outputs": [],
   "source": [
    "/**\n",
    " * @param {number} x\n",
    " * @param {number} n\n",
    " * @return {number}\n",
    " */\n",
    "\n",
    " // time: O(logn)\n",
    " // space: O(1)\n",
    "var myPow = function(x, n) {\n",
    "    \n",
    "    // if the base is negative\n",
    "    // make it positive\n",
    "    // and do the inverse for pow\n",
    "    // so if we have 2^-2, we do (1/2)^2\n",
    "    if (n < 0) {\n",
    "        n = Math.abs(n);\n",
    "        x = (1 / x);\n",
    "    }\n",
    "\n",
    "    // the general algorithm is this:\n",
    "    // given x = 2, and pow = 3,\n",
    "    // we first turn pow into binary representation of itself: 011\n",
    "    \n",
    "    // we know that 2^3 = 2 * 2 * 2\n",
    "    // using the binary representation of the pow, we can condense this: (2^2) * (2^1)\n",
    "    // we basically use the digits of the binary representation as flags\n",
    "    // and there place values as exponents\n",
    "    // 0th place and 1st place are set, so 2^0 = 1, and 2^1 = 2\n",
    "    // thus (2^2) * (2^1) = (2^3)\n",
    "    let res = 1;\n",
    "    while (n !== 0) {\n",
    "        let lsb = n & 1;\n",
    "\n",
    "        // if a flag is set at any digit, we multiply that to the res\n",
    "        if (lsb === 1) {\n",
    "            res *= x;\n",
    "        }\n",
    "\n",
    "        // this is the accumulator\n",
    "        // so if we have 7^3, binary of 3 = 011\n",
    "        // we are able to keep track of 7^1 and 7^2\n",
    "        // this will also go up to 7^4 but it is not multiplied with our res b/c that bit is not set\n",
    "        x *= x;\n",
    "\n",
    "        // unsigned right shift to remove any negatives\n",
    "        n >>>= 1;\n",
    "    }\n",
    "\n",
    "    return res;\n",
    "};"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bc4c2127",
   "metadata": {},
   "source": [
    "## Multiply Strings\n",
    "\n",
    "* https://leetcode.com/problems/multiply-strings/description/\n",
    "***\n",
    "* Time Complexity: O(n * m), n = length of num1, m = length of num2\n",
    "    - we're multiplying each digit one by one like in school so it is n * m\n",
    "* Space Complexity: O(n + m)\n",
    "    - if we multiply 2 numbers with two digits each, the max # of digits that product would have is 4\n",
    "        * e.g. 99 x 99 = 9801\n",
    "***\n",
    "* we follow the same algorithm that we would use to multiply 2 numbers by hand\n",
    "* we start at the end of one number and multiply those digits to the other number\n",
    "* in order to create the string, we use an arr, res, to keep track of the product so far for each digit product\n",
    "    - to get the number of the digit without converting to an integer directly, we use charCodes and subtract by an offset, \"0\".charCodeAt()\n",
    "* we then keep track of 2 indices: [i + j, i + j + 1]\n",
    "    - [i + j + 1] represents the current index that the product will take place on\n",
    "    - [i + j] will represent any carries if the product for [i + j + 1] > 9"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "66cc6c0f",
   "metadata": {},
   "outputs": [],
   "source": [
    "/**\n",
    " * @param {string} num1\n",
    " * @param {string} num2\n",
    " * @return {string}\n",
    " */\n",
    "\n",
    "// Time: O(n * m)\n",
    "// Space: O(n + m)\n",
    "var multiply = function(num1, num2) {\n",
    "    if (num1 === \"0\" || num2 === \"0\") {\n",
    "        return \"0\";\n",
    "    }\n",
    "\n",
    "    const n = num1.length;\n",
    "    const m = num2.length;\n",
    "    const res = Array.from({ length: m + n });\n",
    "    const offset = '0'.charCodeAt();\n",
    "\n",
    "    for (let i = n - 1; i >= 0; i--) {\n",
    "        for (let j = m - 1; j >= 0; j--) {\n",
    "            // can't convert inputs to integers directly so using their charCode is better\n",
    "            let product = (num1[i].charCodeAt() - offset) * (num2[j].charCodeAt() - offset);\n",
    "            let sum = (res[i + j + 1] || 0) + product;\n",
    "\n",
    "            // res[i + j + 1] = ensures that we have leading zeroes rather than trailing zeroes\n",
    "            // gives us the rightmost position for the product\n",
    "            res[i + j + 1] = sum % 10;\n",
    "            let carry = Math.trunc(sum / 10);\n",
    "\n",
    "            // keeps track of any carries we have\n",
    "            res[i + j] = (res[i + j] || 0) + carry;\n",
    "\n",
    "            /**\n",
    "             * e.g. say we have num1 = \"3\" num2 = \"5\"\n",
    "             * res.length = [1, 5]\n",
    "             * i = n - 1 = 1 - 1 = 0, and j = m - 1 = 1 - 1 = 0;\n",
    "             * res[0 + 0 + 1] = res[1] which is where the 5 is\n",
    "             * res[0 + 0] = res[0] which is where the 1 is\n",
    "             \n",
    "             * we know that the max # of digits we get from multiplying 2 numbers of length 1 = 2\n",
    "                - e.g. 9 x 9 = 81, only occupies 2 indices\n",
    "             * so we use indices [i + j, i + j + 1]\n",
    "                - i + j + 1 is where we actually add the product\n",
    "                - i + j is where we add the carry if there is any from i + j + 1\n",
    "                - e.g. res = [], product = 3 * 5 = 15\n",
    "                - sum = 0 + (15) = 15\n",
    "                - res[i + j + 1] = (15 % 10) = 5\n",
    "                - res[i + j] = (15 // 10) = 1;\n",
    "                - res = [1, 5]\n",
    "             */\n",
    "        }\n",
    "    }\n",
    "\n",
    "    // O(m + n)\n",
    "    // much faster to build it like this than to do a res.join(\"\")\n",
    "    // and then having to decide if we want to return resStr or resStr.slice(1)\n",
    "    // reason why we would need to slice for that solution is b/c we will have a leading zero\n",
    "    let resStr = \"\";\n",
    "    for (let i = 0; i < res.length; i++) {\n",
    "        if (i === 0 && res[i] === 0) {\n",
    "            continue;\n",
    "        }\n",
    "\n",
    "        resStr += res[i];\n",
    "    }\n",
    "\n",
    "    return resStr;\n",
    "};"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f58f3d31",
   "metadata": {},
   "source": [
    "## Detect Squares\n",
    "\n",
    "* https://leetcode.com/problems/detect-squares/\n",
    "***\n",
    "* Time Complexity:\n",
    "    - add(): O(1)\n",
    "        * we just add the points to a hash map\n",
    "        * key = \"x_y\", value = # of occurrences of this point\n",
    "            - e.g. [3,2] = \"3_2\"\n",
    "    - count(): O(n)\n",
    "        * must iterate through every point in the hash map and compare it with the current point we want to make a square with\n",
    "* Space Complexity:\n",
    "    - add(): O(n)\n",
    "        * requires space for a hash map\n",
    "    - count(): O(1)\n",
    "        * we don't require any additional space to do this method but if we were to count the hash map, it would be O(n)\n",
    "***\n",
    "* add:\n",
    "    - we add all the points into a hash map\n",
    "    - key = \"x_y\", value = # of occurences of (x,y)\n",
    "        * reason why we use a string is b/c we cannot just add the points as the key\n",
    "        * if we do [x,y]: # of occurences, the hash map cannot check x and y inside that arr\n",
    "* count:\n",
    "    - we essentially iterate through every point in the hash map and treat the current point, (x,y) as a DIAGONAL point to the current point, (px,py)\n",
    "    - this is b/c we can use this to check whether we can even make a square with that point\n",
    "    - we can do this by doing __Math.abs(x - px) === Math.abs(y - py), if (x !== px) && (y !== py)__\n",
    "    - reason being, in order for something to be a SQUARE it has to have the length of all of its sides being equal so if the difference between these 2 points is not even equal, then it cannot make a square\n",
    "        * it'll probably be some other quadrilateral\n",
    "    - once we've identified that we CAN make a square with that point, we just have to find 2 other diagonal points to make it\n",
    "        * diagonal 1: (x, py)\n",
    "        * diagonal 2: (px, y)\n",
    "        * if we can find these in our hash map, we know we can make a square\n",
    "    - now in order to count the # of ways we can make a square using those points, since the question allows duplicate points, is to multiply the # of occurrences of every diagonal and add it to our count\n",
    "        * __count += freq(diag1) * freq(diag2) * freq(current diag)__\n",
    "* e.g.:\n",
    "    - add: [3,2], [3,10], [3,10], [11,2], [11,2]\n",
    "        * hash map: \"3_2\": 1, \"11_2\": 2, \"3_10\": 2\n",
    "    - count: [11, 10]\n",
    "        * current key = \"3_2\"\n",
    "        * [x,y] = [3, 2], [px,py] = [11, 10]\n",
    "        * does it fit our condition?\n",
    "            - Math.abs(3 - 11) === Math.abs(2 - 10) => Math.abs(8) === Math.abs(8) => true!\n",
    "            - x !== px => true, y !== py => true\n",
    "            - so all conditions are met and we can potentially make a square with them!\n",
    "        * now, can we find 2 diagonal points that can make a square with our points?\n",
    "            - [x, py] = [3, 10]\n",
    "            - [px, y] = [11, 2]\n",
    "            - our hash map does contain those diagonals\n",
    "        * now all we have to do is multiply the diagonals' frequencies together and add it to our count\n",
    "            - count += freq([3,10] * freq([11,2]) * freq([3,2]) => (2) * (2) * 1 = 4\n",
    "            - we can visualize this as a probability tree where each branch chooses a different duplicate point, if there are any\n",
    "                * [11,10], [3,10]<sub>1</sub>, [11,2]<sub>1</sub>, [3,2]\n",
    "                * [11,10], [3,10]<sub>1</sub>, [11,2]<sub>2</sub>, [3,2]\n",
    "                * [11,10], [3,10]<sub>2</sub>, [11,2]<sub>1</sub>, [3,2]\n",
    "                * [11,10], [3,10]<sub>2</sub>, [11,2]<sub>2</sub>, [3,2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "517c9b39",
   "metadata": {},
   "outputs": [],
   "source": [
    "/** \n",
    " * Your DetectSquares object will be instantiated and called as such:\n",
    " * var obj = new DetectSquares()\n",
    " * obj.add(point)\n",
    " * var param_2 = obj.count(point)\n",
    " */\n",
    "\n",
    " /**\n",
    "    Intuition: We keep track of points along with the counter in a hashmap during the add method. \n",
    "    Every time count method is called, we iterate through each of the points in the hashmap. \n",
    "    We consider each point from the HashMap (say (x,y)) as a diagonal point to the query \n",
    "    point (say (px, py)). \n",
    "    Since it is given the square needs to be axis-aligned , the condition for two points to \n",
    "    form a axis-aligned square is that, the absolute distance between the x and y coordinates \n",
    "    distances should be equal. If they are not equal it means they will form a rectangle instead\n",
    "    of a square. This is a typical geometry property. Try to visualize it with couple of examples. \n",
    "    Eg: Valid square diagonals are : (3,2) and (11,10) . The absolute coordinate distance \n",
    "    differences are (11 - 3) and (10 - 2) which is 8 is both cases . So these points can form a square. \n",
    "    So assuming these two diagonal points form a square , we construct two other diagonal points for eg: \n",
    "    for diagonal points (x , y) , (px, py) other two diagonal points will be (x, py) , (px, y)\n",
    "    So we check if these two diagonal points are present in map . If they are present we just \n",
    "    count the total squares that can be formed by usign product of each of the diagonal points counts. \n",
    "    \n",
    "    Time Complexity: O(N)\n",
    "    Space Complexity: O(N)\n",
    "    \n",
    "**/\n",
    " var DetectSquares = class {\n",
    "     constructor() {\n",
    "         this.points = new Map();\n",
    "     }\n",
    "\n",
    "    /** \n",
    "    * @param {number[]} point\n",
    "    * @return {void}\n",
    "    */\n",
    "     add(point, {points} = this) {\n",
    "         const [x, y] = point;\n",
    "         const key = `${x}_${y}`\n",
    "         points.set(key, points.has(`${x}_${y}`) ? points.get(`${x}_${y}`) + 1 : 1);\n",
    "     }\n",
    "\n",
    "    /** \n",
    "    * @param {number[]} point\n",
    "    * @return {number}\n",
    "    */\n",
    "     count(point, {points} = this) {\n",
    "         const [px, py] = point;\n",
    "         let count = 0;\n",
    "\n",
    "         for (const [key, _] of points) {\n",
    "             const x = parseInt(key.split(\"_\")[0], 10);\n",
    "             const y = parseInt(key.split(\"_\")[1], 10);\n",
    "\n",
    "             if (Math.abs(x - px) === Math.abs(y - py) && (x !== px) && (y !== py)) {\n",
    "                 const diag1 = `${px}_${y}`;\n",
    "                 const diag2 = `${x}_${py}`;\n",
    "\n",
    "                 if (points.has(diag1) && points.has(diag2)) {\n",
    "                     count += (points.get(diag1) * points.get(diag2)) * points.get(key);\n",
    "                 }\n",
    "             }\n",
    "         }\n",
    "\n",
    "         return count;\n",
    "     }\n",
    " }"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "aa4b117b",
   "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
}