Algorithm Problems

CS_algorithms.js

// Climbing Stairs (5/13)
//  - can be modeled as a graph problem
//  - starting from 0 we can take 1 step and get to 1 or take 2 steps and get to 2
//  - then from 1 we can take 1 step and get to 2 or take 2 steps and get to 3, and so on
//  - if we get to n from a branch, we've found one way
//  - recursion can be used to count number of unique paths that can count to n
//  - to avoid repeated work, we can cache
//  - if we don't cache, it's 2^n time because we must branch out two ways, n times
//  - if we cache, it's linear time/space
//  - finally, we can reduce to constant space by computing total distinct ways
//    on the fly from n stairs down to 0 stairs given the observation that
//    there is 1 way to get to n, 2 ways to get to n-1 and 3 ways to get to n-2
//    which I believe can be summarized in f(n - 1) + f(n - 2)

// time o(n) | space o(1)
function climbStairs(n) {
  if (n === 2) return 2;
  if (n === 1) return 1;
  if (n < 1) return 0;
  let nextPlusOne = 1;
  let next = 2;
  let distinctWays = 0;
  for (let i = n - 3; i >= 0; i--) {
    distinctWays = next + nextPlusOne;
    nextPlusOne = next;
    next = distinctWays;
  }
  return distinctWays;
};

// time o(n) | space o(n)
function climbStairs(n, cache = {1: 1, 2: 2}) {
  if (n in cache) {
    return cache[n];
  }
  cache[n] = climbStairs(n - 1, cache) + climbStairs(n - 2, cache);
  return cache[n];
};


// Min Path Sum (5/9)
// DP makes it o(n)
// without it its more expensive, 2^n
function minPathSum(grid) {
  const seen = {};
  return dfs(grid, 0, 0, seen);
};

function dfs(grid, row, col, seen) {
  if (seen[`${row}_${col}`]) return seen[`${row}_${col}`];

  if (
    row < 0 ||
    col < 0 ||
    row > grid.length - 1 ||
    col > grid[row].length - 1
  ) {
    return Number.POSITIVE_INFINITY;
  }

  if (row === grid.length - 1 && col === grid[row].length - 1) {
    return grid[row][col];
  }

  seen[`${row}_${col}`] =
    grid[row][col] +
    Math.min(dfs(grid, row, col + 1, seen), dfs(grid, row + 1, col, seen));

  return seen[`${row}_${col}`];
}



// Add and Search Words (5/5)

// time - o(M) for well defined words, worse case o(M.26^N)
// space - O(1) for well defined words, worst case o(M)
class WordDictionary {
  constructor() {
    this.trie = new Trie();
  }

  addWord(word) {
    this.trie.populate(word);
  }

  search(word) {
    return this.trie.contains(word);
  }
}

class Trie {
  constructor(string) {
    this.root = {};
  }

  populate(string) {
    let node = this.root;
    for (const char of string) {
      if (!(char in node)) node[char] = {};
      node = node[char];
    }
    node.isEnd = true;
  }

  contains(string, index = 0, node = this.root) {
    if (index === string.length && node.isEnd) return true;
    if (index === string.length) return false;

    const char = string[index];

    if (char === ".") {
      for (const key in node) {
        if (this.contains(string, index + 1, node[key])) return true;
      }
    } else {
      if (node[char] !== undefined) {
        return this.contains(string, index + 1, node[char]);
      }
    }

    return false;
  }
}



// Meeting Rooms 2 (5/3)

// Traverse through each event - a meeting - (sorted by their start time)
// and track all ongoing events and the "next" one that will end.
// A min heap gives us constant time access to this (next event that will end).
// For each event:
// - Compare and remove (in log n time) the next meeting in the min heap, if it's ended.
// - Add the end time of our current meeting to the heap (also a log n time operation)
// - Finally, given the total amount of ongoing events changes, re-compute max rooms needed

const minMeetingRooms = (intervals) => {
  const compareFunc = (a, b) => a - b;
  const minHeap = new MinHeap(compareFunc);
	
  intervals.sort((a, b) => a[0] - b[0]);

  let maxRooms = 0;
  intervals.forEach((interval) => {
    if (minHeap.size > 0 && minHeap.peek() <= interval[0]) {
      minHeap.extract();
    }
    minHeap.insert(interval[1]);
    maxRooms = Math.max(maxRooms, minHeap.size);
  });

  return maxRooms;
};



// Course Schedule (5/1)
var canFinish = function (numCourses, prerequisites) {
  const graph = makeGraph(prerequisites);
  const globalSeen = new Set();

  for (const [node, _] of Object.entries(graph)) {
    const seen = new Set();
    const isNotCyclic = checkForCycle(graph, globalSeen, seen, node);
    if (!isNotCyclic) return false;
  }

  return true;
};

function checkForCycle(graph, globalSeen, seen, node) {
  if (graph[node] === undefined) return true;
  if (globalSeen.has(node)) return true;

  seen.add(node);

  for (const next of graph[node]) {
    if (seen.has(next)) return false;
    const isNotCyclic = checkForCycle(graph, globalSeen, seen, next);
    if (!isNotCyclic) return false;
  }

  globalSeen.add(node);
  seen.delete(node);

  return true;
}

function makeGraph(prerequisites) {
  const graph = {};
  for (const [course, dependency] of prerequisites) {
    if (!graph[dependency]) graph[dependency] = [];
    graph[dependency].push(course);
  }

  return graph;
}



// Word Search (4/28)
// for each char of word, we have 4 choices of neighbors to explore
// so if total # of chars is S, one invocation of dfs is 4^S time
// therefore upper bound is o(m*n*4^S) time where m is grid row and n is grid col

// can be modeled as a graph problem and a dfs approach can be used to
// explore every possible path starting from each cell to a target cell
// so a possible start of a word to the end of a word
// at each new location, slice a character off of the word if they match (2 base cases here)
// we can optimize by initializing a visited set at the beginning of every exploration
// adding to the set before visiting new locations and removing it if unsuccessful
function wordExists(board, word) {
  for (let row = 0; row < board.length; row++) {
    for (let col = 0; col < board[row].length; col++) {
      if (board[row][col] !== word[0]) continue;
      const seen = new Set();
      if (dfs(board, word, row, col, seen)) return true;
    }
  }

  return false;
};

function dfs(board, word, row, col, seen) {
  if (word.length === 0) return true;
  if (seen.has(`${row}_${col}`)) return false;
  if (row < 0 || col < 0) return false;
  if (row > board.length - 1 || col > board[row].length - 1) return false;

  const char = board[row][col];
  if (char !== word[0]) return false;

  seen.add(`${row}_${col}`);
  const newWord = word.slice(1, word.length);

  if (
    dfs(board, newWord, row + 1, col, seen) ||
    dfs(board, newWord, row - 1, col, seen) ||
    dfs(board, newWord, row, col + 1, seen) ||
    dfs(board, newWord, row, col - 1, seen)
  )
    return true;

  seen.delete(`${row}_${col}`);
  return false;
}



// IsPanlindrome (4/24)
// Basics of head/tail in recursion 
function isPalindrome(str) {
  if (str.length < 2) return true;
  const head = str[0];
  const mid = str.slice(1, str.length - 1);
  const tail = str[str.length - 1];
  return head === tail && isPalindrome(mid);
}

isPalindrome('racecar')

// Reverse (same as above)
function reverse(str) {
  if (str.length === 0) return '';
  const head = str[0];
  const tail = reverse(str.slice(1, str.length));
  return tail + head;
}

reverse('gh')

// Concat (same as above)
function concat(arr) {
  console.log(COUNT)
  if (arr.length === 0) return '';
  const head = arr[0];
  const tail = concat(arr.slice(1, arr.length));
  return head + tail;
}

console.log(concat(['Hello', 'World', 'Gui', 'sa']))



// Shorten Path (3/14)

// this problem feels hard - it's important to separate out
// general structure from edge cases
// maybe you can get help from interviewer about edge cases
// so prep to set it up correctly by focusing on generalizing it
// ie. what is considered more important

// time o(n) | space o(n)
function shortenPath(path) {
  const startWithSlash = path[0] === "/";
  const tokens = path.split("/").filter(isImportantToken);
  const stack = [];
  if (startWithSlash) {
    stack.push("");
  }
  for (const token of tokens) {
    if (token === "..") {
      if (stack.length === 0 || stack[stack.length - 1] === "..") {
        stack.push(token);
      } else if (stack[stack.length - 1] !== "") {
        stack.pop();
      }
    } else {
      stack.push(token);
    }
  }

  if (stack.length === 1 && stack[0] === "") return "/";
  return stack.join("/");
}

function isImportantToken(token) {
  return token.length > 0 && token !== ".";
}



// Multi String Search (3/14)
// recognize there are various ways of solving this problem
// either using small strings or with big strings
// and maybe there would be benefits of doing it one way or another
// or perhaps we really value are space complexity and we might want to go with
// naive solution without building an auxilary data structure

// build a modified suffix tree where we dont care for endSymbol at end of suffix
// bc we'll traverse until we find just that a small string is contained in it
// not necessarily that it denotes the end of an actual string (ends with *)
// it will take o(b^2) time/space to build
// then iterate through all small strings and for each, check if its contained in the suffix trie
// since largest string in smallest strings has len s
// there are n small strings so we'll be doing o(ns) time
// so we have a time complexity of o(b^2) for building plus o(ns) for finding
// so a total time of o(b^2+ns)
// similarly space will be o(b^2+n) bc storing is b^2 space, then building same output array of len n

// time o(b^2 + ns) | space o(b^2 + n)
function multiStringSearch(bigString, smallStrings) {
  const trie = new SuffixTrie(bigString);
  return smallStrings.map((string) => trie.contains(string));
}

class SuffixTrie {
  constructor(string) {
    this.root = {};
    this.construct(string);
  }

  construct(string) {
    for (let i = 0; i < string.length; i++) this.insertAt(i, string);
  }

  insertAt(i, string) {
    let node = this.root;
    for (let j = i; j < string.length; j++) {
      if (!(string[j] in node)) node[string[j]] = {};
      node = node[string[j]];
    }
  }

  contains(string) {
    let node = this.root;
    for (const letter of string) {
      if (!(letter in node)) return false;
      node = node[letter];
    }
    return true;
  }
}



// Suffix Trie Construction (3/14)
// methods
// populate from string (string)
// insert at (string, i)
// contains (string)

// populate - calls insert at for each index of string
// insert at - initialize node as root
// for each letter in string
// if letter not in node, create new object
// update node to node[letter]
// afterwards insert end symbol in current node

// contains
// initialize node as root
// for each letter in string, if not in node, return false
// return this.endSymbol in node

// contains - where m is length of input string we're looking for
// creation - time o(n^2) | space o(n^2)
// contains - time o(m) | space o(1)
class SuffixTrie {
  constructor(string) {
    this.root = {};
    this.endSymbol = "*";
    this.populateSuffixTrieFrom(string);
  }

  populateSuffixTrieFrom(string) {
    // for each index in string, insertAt(string, index)
    for (let i = 0; i < string.length; i++) {
      this.insertAt(i, string);
    }
  }

  insertAt(i, string) {
    let node = this.root;
    for (let j = i; j < string.length; j++) {
      const letter = string[j];
      if (!(letter in node)) node[letter] = {};
      node = node[letter];
    }

    node[this.endSymbol] = true;
  }

  contains(string) {
    let node = this.root;
    for (const letter of string) {
      if (!(letter in node)) return false;
      node = node[letter];
    }

    return this.endSymbol in node;
  }
}



// Is Valid Subsequence
// create a pointer to track sequence starting from 0
// move it everytime we find it in array
// if pointer has reached end of sequence, return true
// in case we reach end of sequence prior to end, break

// [5, 1, 22, 25, 6, -1, 8, 10]
// [1, 6, -1, 10]
// true

// time o(n) | space o(1)
function isValidSubsequence(array, sequence) {
  let j = 0;
  for (let i = 0; i < array.length; i++) {
    if (array[i] === sequence[j]) {
      j++;
    }
  }

  return j === sequence.length;
}



// Merge Overlapping Intervals (3/8)
// sort first! with (a, b) => a[0] - b[0]
// then merge item by item while updating last item from results array
// recognize to use math.max (must decide between largest of two)
// wasn't obvious at first - this is the caveat:
// if prev end is greater than or equal to curr start
// then set prev end to largest between prev end and curr end

// time o(nlogn) | space o(1)
function mergeOverlappingIntervals(array) {
  array.sort((a, b) => a[0] - b[0]);

  const merged = [array[0]];
  for (let i = 1; i < array.length; i++) {
    const intervalOne = merged[merged.length - 1];
    const intervalTwo = array[i];
    if (intervalOne[1] >= intervalTwo[0]) {
      merged[merged.length - 1][1] = Math.max(intervalOne[1], intervalTwo[1]);
      continue;
    }
    merged.push(intervalTwo);
  }

  return merged;
}



// First Duplicate Value (3/8)
// we use indicies to map values to each other
// since valus are 1..n and we can modify input array
// use indicies to represent values to generate index
// if at array[index] we dont have a negative, we set it to be one
// next time we get to that same value, we'll go to the same index
// and know that we've seen that value before

// time o(n) | space o(1)
function firstDuplicateValue(array) {
  for (const value of array) {
    const absValue = Math.abs(value);
    if (array[absValue - 1] < 0) return absValue;
    array[absValue - 1] *= -1;
  }

  return -1;
}



// Array of Products (3/8)
// array fill strategy
// continue re-fill by re-computing prev vals at each index
// gets us to o(n) runtime (good hint if you're stuck on a o(n^2) solution)

// time o(n) | space o(n)
function arrayOfProducts(array) {
  const products = new Array(array.length).fill(1);
  let currentProduct = 1;
  for (let i = 0; i < array.length; i++) {
    products[i] = currentProduct;
    currentProduct *= array[i];
  }

  currentProduct = 1;
  for (let i = array.length - 1; i >= 0; i--) {
    products[i] *= currentProduct;
    currentProduct *= array[i];
  }

  return products;
}



// Longest Peak (3/8)
// instead of having i = 0 and inside while, skip if i is 0 or i === len - 1
//    just have i start at 1 and while should end at len - 1
// instead of left/right, use leftIdx/rightIdx
// longestPeakLength isn't initialized as -Infinity, just 0

// since it asks for longestPeakDistance, we don't need a `positions` array aux space
// time o(n) | space o(1)
function longestPeak(array) {
  let i = 1;
  let longestPeakLength = 0;
  while (i < array.length - 1) {
    const isPeak = array[i - 1] < array[i] && array[i] > array[i + 1];
    if (!isPeak) {
      i++;
      continue;
    }

    let leftIdx = i - 2;
    while (leftIdx >= 0 && array[leftIdx] < array[leftIdx + 1]) {
      leftIdx--;
    }

    let rightIdx = i + 2;
    while (rightIdx < array.length && array[rightIdx] < array[rightIdx - 1]) {
      rightIdx++;
    }

    const currentPeakLength = rightIdx - leftIdx - 1;
    longestPeakLength = Math.max(longestPeakLength, currentPeakLength);
    i = rightIdx;
  }

  return longestPeakLength;
}



// Spiral Traverse (3/7)
// loop 3 and 4 need to break if there's a single row/row left
// second loop is row = startRow + 1, everything else is minus one
// last loop is row >, not row >=
// last loop is row > startRow, not row > endRow
// time o(n) | space o(n)
function spiralTraverse(array) {
  let startRow = 0;
  let endRow = array.length - 1;
  let startCol = 0;
  let endCol = array[0].length - 1;
  const result = [];

  while (startRow <= endRow && startCol <= endCol) {
    for (let col = startCol; col <= endCol; col++) {
      result.push(array[startRow][col]);
    }
    for (let row = startRow + 1; row <= endRow; row++) {
      result.push(array[row][endCol]);
    }
    for (let col = endCol - 1; col >= startCol; col--) {
      if (startRow === endRow) break;
      result.push(array[endRow][col]);
    }
    for (let row = endRow - 1; row > startRow; row--) {
      if (startCol === endCol) break;
      result.push(array[row][startCol]);
    }
    startRow++;
    endRow--;
    startCol++;
    endCol--;
  }

  return result;
}



// Monotonic Array (3/7)
// time o(n) | space o(1)
function isMonotonic(array) {
  let isNonDecreasing = true;
  let isNonIncreasing = true;
  for (let i = 1; i < array.length; i++) {
    if (array[i] > array[i - 1]) isNonDecreasing = false;
    if (array[i] < array[i - 1]) isNonIncreasing = false;
  }

  return isNonDecreasing || isNonIncreasing;
}



// Move to Element (3/7)
// we need some left and right idx, i and j
// iterate through array while incrementing i
// decrement j while its j is greater than i and array[j] === toMove
// if array[i] equals toMove, swap

// time o(n) - we only visit every index once
// space o(1)
function moveElementToEnd(array, toMove) {
  let i = 0;
  let j = array.length - 1;
  while (i < j) {
    while (j > i && array[j] === toMove) j--;
    if (array[i] === toMove) swap(i, j, array);
    i++;
  }

  return array;
}

function swap(i, j, array) {
  const temp = array[i];
  array[i] = array[j];
  array[j] = temp;
}



// Smallest Difference (3/7)
// technique takes advantage of properties of a sorting array
// either dec/inc to bring nums closer to each other
// javascript .sort needs .((a, b) => a - b)
// ask interviewer
// is it ok to sort in place, otherwise account for extra space complexity

// time - sorting (quicksort or mergesort)
// time o(nlog(n) + mlog(m))
// space - constant
function smallestDifference(arrayOne, arrayTwo) {
  arrayOne.sort((a, b) => a - b);
  arrayTwo.sort((a, b) => a - b);
  let idxOne = 0;
  let idxTwo = 0;
  let smallest = Infinity;
  let smallestPair = [];
  while (idxOne < arrayOne.length && idxTwo < arrayTwo.length) {
    const firstNum = arrayOne[idxOne];
    const secondNum = arrayTwo[idxTwo];
    let current = Math.abs(firstNum - secondNum);
    if (firstNum === secondNum) {
      return [firstNum, secondNum];
    } else if (firstNum < secondNum) {
      idxOne++;
    } else {
      idxTwo++;
    }
    if (current < smallest) {
      smallest = current;
      smallestPair = [firstNum, secondNum];
    }
  }

  return smallestPair;
}



// Three Number Sum (3/7)
// left/right inc/dec based on currentSum
// but inside a for i loop from 0 through array.length - 2
// while resetting left to i + 1 and right to array.length - 1

// time - iterate through main array once and left/right pointer need to iterate through main array once
// space - might store every number in array if they are used in some triplets
// time o(n^2) | space o(n)
function threeNumberSum(array, targetSum) {
  const triplets = [];
  array.sort((a, b) => a - b);
  for (let i = 0; i < array.length - 2; i++) {
    let left = i + 1;
    let right = array.length - 1;
    while (left < right) {
      let currentSum = array[i] + array[left] + array[right];
      if (currentSum === targetSum) {
        triplets.push([array[i], array[left], array[right]]);
        left++;
        right--;
      } else if (currentSum < targetSum) {
        left++;
      } else {
        right--;
      }
    }
  }

  return triplets;
}



// Merge Linked List (2/16)

// n length of 1st, m length of 2nd
// time o(n+m) | space o(1)

// class LinkedList {...}

function mergeLinkedLists(headOne, headTwo) {
  let p1 = headOne;
  let p1Prev = null;
  let p2 = headTwo;
  while (p1 !== null && p2 !== null) {
    if (p1.value < p2.value) {
      p1Prev = p1;
      p1 = p1.next;
    } else {
      if (p1Prev !== null) p1Prev.next = p2;
      p1Prev = p2;
      p2 = p2.next;
      p1Prev.next = p1;
    }
  }
  // we've runned out of p1 but still have values in p2
  if (p1 === null) p1Prev.next = p2;
  // what is the new correct head of merged linked list
  return headOne.value < headTwo.value ? headOne : headTwo;
}



// Reverse Linked List (2/15)
// three pointers, move them together
// so long as p2 isnt null, do operations
// p2 is analogous to "current node" so initialize p1 to null and p2 to head
// p3 = p2.next, then p2.next = p1, then p1 = p2, then p2 = p3
// notice the order (reading in reverse helps)
// we loose p1 the second we do p1 = p2, so before we override p1, we do p2.next = p1, etc

// time o(n) | space o(1)

// class LinkedList {...}

function reverseLinkedList(head) {
  let prevNode = null;
  let currentNode = head;
  while (currentNode !== null) {
    const nextNode = currentNode.next;
    currentNode.next = prevNode;
    prevNode = currentNode;
    currentNode = nextNode;
  }
  return prevNode;
}



// Find Loop (2/14)
// set first/second node to head
// make second node travel 2x as fast until they meet
// reset first to head
// then make both travel together until they meet

// 1st pointer travels D + P distance
// try to visualize this where D is linear distance before loop
// and P is some arc
// 2nd pointer travels 2D + 2P distance
// so total distance is whatever 2nd pointer travelled minus P (so minus the arc)
// which turns out to be 2D + P
// and then R equals 2D + P - P - D (which is what F travelled)
// so R = D
// but we're almost done
// now we know we need to traverse distance D from where our pointers are
// that's why we reset first to head and move them together until they meet again

// 2nd pointer doesn't matter, it's travelling at a faster than normal pace
// time o(n) | space o(1)

// class LinkedList {...}

function findLoop(head) {
  let first = head.next;
  let second = head.next.next;
  while (first !== second) {
    first = first.next;
    second = second.next.next;
  }
  first = head;

  while (first !== second) {
    first = first.next;
    second = second.next;
  }

  return first;
}




// Sum of Linked Lists (2/14)
// it's ok to start from left to right from least significant digits
// get sum per column (sumOfValues % 10), get carry per column (sumOfValues // 10)
// create new linked list node per column
// add pointers from the last node we had to this next new node
// move current node to new node

// things to watch out for:
// (1)
// lots of variables
// carry, nodeOne/Two, valueOne/Two, sumOfValues, newValue, newNode
// (2)
// set current node's pointer to next linked list node we just created (currentNode.next = newNode)
// update current node to be last node we created (currentNode = newNode)
// (3)
// while loop contains three OR conditions (keeps running if truthy values found)
// so instead of creating inner conditions, we conditionalize our values to 0 if null

// whatever the longest linked list dictates the length
// plus 1 is if we have a carry at end, there's another loop
// time o(max(n, m)) + 1 | space o(max(n, m) + 1)

// class LinkedList {...}

function sumOfLinkedLists(linkedListOne, linkedListTwo) {
  const newLinkedListHeaderPointer = new LinkedList(0);
  let currentNode = newLinkedListHeaderPointer;
  let carry = 0;

  let nodeOne = linkedListOne;
  let nodeTwo = linkedListTwo;
  while (nodeOne !== null || nodeTwo !== null || carry !== 0) {
    const valueOne = nodeOne !== null ? nodeOne.value : 0;
    const valueTwo = nodeTwo !== null ? nodeTwo.value : 0;
    const sumOfValues = valueOne + valueTwo + carry;

    const newValue = sumOfValues % 10;
    const newNode = new LinkedList(newValue);
    currentNode.next = newNode;
    currentNode = newNode;

    carry = Math.floor(sumOfValues / 10);
    nodeOne = nodeOne !== null ? nodeOne.next : null;
    nodeTwo = nodeTwo !== null ? nodeTwo.next : null;
  }

  return newLinkedListHeaderPointer.next;
}



// Remove Kth Node from From End (2/14)
// move first/second pointer, remember to stop on items prev to your "targets"
// start by moving second to k (counter from 1 to k inclusive)
// if second is null, remove first (update head.value and head.next), return
// otherwise, move first and second together
// lastly, remove first by updating it entirely (first.next = first.next.next)

// time o(length) | space o()
class LinkedList {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

function removeKthNodeFromEnd(head, k) {
  let counter = 1;
  let first = head;
  let second = head;
  while (counter <= k) {
    second = second.next;
    counter++;
  }
  if (second === null) {
    head.value = head.next.value;
    head.next = head.next.next;
    return;
  }
  while (second.next !== null) {
    first = first.next;
    second = second.next;
  }
  first.next = first.next.next;
}



// Number of Binary Tree Topologies (2/10)
// time o(n^2) | space o(n)
function numberOfBinaryTreeTopologies(n, cache = { 0: 1 }) {
  if (n in cache) return cache[n];
  let numOfTrees = 0;
  for (let leftSize = 0; leftSize < n; leftSize++) {
    const rightSize = n - 1 - leftSize;
    const totalLeft = numberOfBinaryTreeTopologies(leftSize, cache);
    const totalRight = numberOfBinaryTreeTopologies(rightSize, cache);
    numOfTrees += totalLeft * totalRight;
  }
  cache[n] = numOfTrees;
  return cache[n];
}



// Ambiguous Measurements (2/10)

// time o(low * high * n) | space o(low * high) - where n is
// the number of measuring cups
function ambiguousMeasurements(measuringCups, low, high) {
  const cache = {};
  return helper(measuringCups, low, high, cache);
}

function helper(cups, low, high, cache) {
  const key = getHashableKey(low, high);
  if (key in cache) return cache[key];

  if (low < 0 && high < 0) return false;

  let canMeasure = false;
  for (const cup of cups) {
    const [cupLow, cupHigh] = cup;
    if (low <= cupLow && cupHigh <= high) {
      canMeasure = true;
      break;
    }

    canMeasure = helper(cups, low - cupLow, high - cupHigh, cache);
    if (canMeasure) break;
  }

  cache[key] = canMeasure;
  return canMeasure;
}

function getHashableKey(low, high) {
  return `${low}:${high}`;
}



// Generate Div Tags (2/10)
// question not really designed to test time complexity explanation 
// incrementally build solutions, tack on open/close tags
// to start generating a valid string
// we need at least an opening tag
// what can we do
// add <div></div> to end of valid string
// or surround valid string with opening/closing tag

// add opening tag before we close it
// so we have an opening tag to be added on other tail of recursion

// catalan number - (2n)!/((n!((n+1)!)))
// string generation grows exponentially
// time ~o(catalanNum) | space ~o(catalanNum)
function generateDivTags(numberOfTags) {
  const result = [];
  helper(numberOfTags, numberOfTags, "", result);
  return result;
}

function helper(opening, closing, prefix, result) {
  if (opening > 0) helper(opening - 1, closing, prefix + "<div>", result);
  if (opening < closing)
    helper(opening, closing - 1, prefix + "</div>", result);
  if (closing === 0) result.push(prefix);
}



// Sudoku Solver (2/10)
// computationally intentive task to brute force 81 squares * 9 possibilities
// see https://en.wikipedia.org/wiki/Mathematics_of_Sudoku

// for recursive matrix traversal
// inner loop (col++) will finish first
// so base case means we col=0 and increment outer loop (row++)
// there's also an inner second base case
// if outer loop is *also* finished, then, we exit recursion (return true)

// for backtracking, mutate board state if it passes validation
// then return true, otherwise, reset board state and return false

// for validating row, call includes on board[row]
// for validating col, call includes on board.map(r => r[col])

// for sub-dividing a 9x9 grid into three 3x3 grids
// set a sub grid col/row start variable to row - row % sqrt
// to validate subgrids, use outer/inner row/col loop but from 0-3 only

// things to remember:
//   - pass your startings 0's
//   - when calling tryIt helper (1) don't mutate state; (2) immediatly return itself;
//     (3) mutate state from tryIt helper
//   - use initialized currentRow/currentCol in recursive cases
//   - for isRowValid, it's board[row].includes, not board.includes
//   - subgrid for loops is up to subgrid len (ie. 3), not board len

// constant board size, so constant time
// time o(1) | space o(1)
function solveSudoku(board) {
  solver(0, 0, board);
  return board;
}

function solver(row, col, board) {
  let currentRow = row;
  let currentCol = col;

  if (currentCol === board[row].length) {
    currentRow++;
    currentCol = 0;
    if (currentRow === board.length) return true;
  }

  if (board[currentRow][currentCol] === 0) {
    return tryDigitsAtPosition(currentRow, currentCol, board);
  }

  return solver(currentRow, currentCol + 1, board);
}

function tryDigitsAtPosition(row, col, board) {
  for (let digit = 1; digit < 10; digit++) {
    if (isValidAtPosition(row, col, board, digit)) {
      board[row][col] = digit;
      if (solver(row, col + 1, board)) return true;
    }
  }

  board[row][col] = 0;
  return false;
}

function isValidAtPosition(row, col, board, value) {
  const isColValid = !board[row].includes(value);
  const isRowValid = !board.map((r) => r[col]).includes(value);

  if (!isColValid || !isRowValid) return false;

  const sqrt = Math.floor(Math.sqrt(board.length));
  const subgridRowStart = row - (row % sqrt);
  const subgridColStart = col - (col % sqrt);
  for (let rowIdx = 0; rowIdx < 3; rowIdx++) {
    for (let colIdx = 0; colIdx < 3; colIdx++) {
      const rowToCheck = subgridRowStart + rowIdx;
      const colToCheck = subgridColStart + colIdx;
      const existingValue = board[rowToCheck][colToCheck];

      if (existingValue === value) return false;
    }
  }

  return true;
}



// Lowest Common Manager (2/8)
// dfs post-order traversal
// retrieve sub-tree info by starting from leaf nodes and returning related info
// the return - an object (org info) - gets assigned to variable
// if org info contains answer (isn't null), return again so we exit (base case 2)
// base case 1 happens else where - at the bottom of post-order traversal
// most interesting here are the two counter instances
// the main one, initialized at root
// but we interpret it in reverse
// first at the bottom (base case 1), where we increment itself
// then in middle (if we can't process base case 2)
// where we increment it based on counter retrieved from recursion (a return of itself)

// where n is people in org chart and d is depth (height) of org chart
// time o(n) | space o(d)
function getLowestCommonManager(topManager, reportOne, reportTwo) {
  return getOrgInfo(topManager, reportOne, reportTwo).lowestCommonManager;
}

function getOrgInfo(manager, reportOne, reportTwo) {
  let numImportantReports = 0;
  for (const directReport of manager.directReports) {
    const orgInfo = getOrgInfo(directReport, reportOne, reportTwo);
    if (!!orgInfo.lowestCommonManager) return orgInfo;
    numImportantReports += orgInfo.numImportantReports;
  }

  if (manager === reportOne || manager === reportTwo) {
    numImportantReports += 1;
  }
  const lowestCommonManager = numImportantReports === 2 ? manager : null;
  return { lowestCommonManager, numImportantReports };
}

class OrgChart {
  constructor(name) {
    this.name = name;
    this.directReports = [];
  }
}



// Min Heap (1/28)
// order of implementation - peak, swap, insert, remove, siftUp, siftDown
// remove - swap root/last, pop off heap, siftDown
// siftUp - needs currIdx, heap
// siftDown - needs currIdx, *endIdx*, heap 
//   remember to exit method with return on if else statement of heap[idxToSwap] < heap[currIdx]
//   less than or equal to - not just less than
//   prevents calling on leaf nodes
//   while loop expression is while currIdx <= endIdx, not heap[currIdx]...

// siftDown/siftUp - time o(logn) - everytime we swap a node, we eliminate half of tree
// buildHeap - time o(n) - we call siftDown on n nodes
// it's not o(nlogn) bc that "distance" isn't equal for every node
// but implementing buildHeap siftUp would be nlogn
// space - 0(1) all happens in-space

// time o(logn) | space o(1)
class MinHeap {
  constructor(array) {
    this.heap = this.buildHeap(array);
  }

  buildHeap(array) {
    let pIdx = Math.floor((array.length - 2) / 2);
    for (let currIdx = pIdx; currIdx >= 0; currIdx--) {
      this.siftDown(currIdx, array.length - 1, array);
    }
    return array;
  }
	
  siftDown(currIdx, endIdx, heap) {
    let childOneIdx = currIdx * 2 + 1;
    while (currIdx <= endIdx) {
      const childTwoIdx = currIdx * 2 + 2 <= endIdx ? currIdx * 2 + 2 : -1;
      let idxToSwap;
      if (childTwoIdx !== -1 && heap[childTwoIdx] < heap[childOneIdx]) {
        idxToSwap = childTwoIdx;
      } else {
        idxToSwap = childOneIdx;
      }
      if (heap[idxToSwap] < heap[currIdx]) {
        this._swap(idxToSwap, currIdx, heap);
        currIdx = idxToSwap;
        childOneIdx = currIdx * 2 + 1;
      } else {
        return;
      }
    }
  }

  siftUp(currIdx, heap) {
    let pIdx = Math.floor((currIdx - 1) / 2);
    while (currIdx > 0 && heap[currIdx] < heap[pIdx]) {
      this._swap(currIdx, pIdx, heap);
      currIdx = pIdx;
      pIdx = Math.floor((currIdx - 1) / 2);
    }
  }

  peek() {
    return this.heap[0];
  }

  remove() {
    this._swap(0, this.heap.length - 1, this.heap);
    const removedItem = this.heap.pop();
    this.siftDown(0, this.heap.length - 1, this.heap);
    return removedItem;
  }

  insert(value) {
    this.heap.push(value);
    this.siftUp(this.heap.length - 1, this.heap);
  }

  _swap(i, j, heap) {
    const temp = heap[i];
    heap[i] = heap[j];
    heap[j] = temp;
  }
}



// Boggle Board (1/28)
// create/populate trie
// finalWords hash - for words that appear multiple times, also we return all keys from it as final answer
// visited - identical to board, but for bool of false
// traverse board - for row, col - "explore" method that modifies finalWords

// space - building a tree, contain all words list of words with at most "S" chars where "S" len of longest word
// for suffix trie, we have at least ws auxilary space
// we are also building am aux matrix of booleans
// so ws + nm where n is width, m is height

// time - ws - bc we iterate through words and they have s chars in them
// then we iterate through entire matrix, so a total of nm nodes to travese matrix
// for all nm node explored, we go through all their neighbors, and all their neighbor's neighbors, until we exhaust this list
// question is "how many neighbors does one node have?" - worst case, it's 8 neighbors
// worst case is going to be 8*8*8 a total of s times - so 8^s - therefore ws+nm*8^s

// time o(nm*8^s + ws) | space o(nm + ws)
function boggleBoard(board, words) {
  const trie = new Trie();
  for (const word of words) {
    trie.add(word);
  }
  const visited = board.map((row) => row.map((_) => false));
  const finalWords = {};
  for (let row = 0; row < board.length; row++) {
    for (let col = 0; col < board[row].length; col++) {
      explore(row, col, trie.root, board, visited, finalWords);
    }
  }
  return Object.keys(finalWords);
}

function explore(row, col, node, board, visited, finalWords) {
  if (visited[row][col]) return;
  const letter = board[row][col];
  if (!(letter in node)) return;
  visited[row][col] = true;
  node = node[letter];
  if ("*" in node) finalWords[node["*"]] = true;
  const neighbors = getNeighbors(board, row, col);
  for (const neighbor of neighbors) {
    explore(neighbor[0], neighbor[1], node, board, visited, finalWords);
  }
  visited[row][col] = false;
}

function getNeighbors(board, row, col) {
  const positions = [];

  if (row < board.length - 1) positions.push([row + 1, col]);
  if (row > 0) positions.push([row - 1, col]);
  if (col < board[0].length - 1) positions.push([row, col + 1]);
  if (col > 0) positions.push([row, col - 1]);

  if (row > 0 && col > 0) {
    positions.push([row - 1, col - 1]); // north-west
  }
  if (row < board.length - 1 && col < board[0].length - 1) {
    positions.push([row + 1, col + 1]); // south-east
  }
  if (row > 0 && col < board[0].length - 1) {
    positions.push([row - 1, col + 1]); // north-east
  }
  if (row < board.length - 1 && col > 0) {
    positions.push([row + 1, col - 1]); // south-west
  }

  return positions;
}

class Trie {
  constructor() {
    this.root = {};
    this.endSymbol = "*";
  }

  add(string) {
    let node = this.root;
    for (let i = 0; i < string.length; i++) {
      const char = string[i];
      if (!(char in node)) node[char] = {};
      node = node[char];
    }
    node[this.endSymbol] = string;
  }
}



// Class Photos (1/26)
// between 2 lists of student "heights", which are the tallest?
// to find out, sort it, then iterate until condition is invalid, otherwise it's valid
// valid means a class photo can  be taken bc tallest students are in the back
// and in the front the student must be strictly smaller than their back counterpart

// sorting is needed
// time o(nlogn) | space o(1)
function classPhotos(redShirtHeights, blueShirtHeights) {
  redShirtHeights.sort((a, b) => a - b);
  blueShirtHeights.sort((a, b) => a - b);

  let isRedLargest = redShirtHeights[0] > blueShirtHeights[0];
  for (let i = 0; i < redShirtHeights.length; i++) {
    if (isRedLargest !== redShirtHeights[i] >= blueShirtHeights[i])
      return false;
  }

  return true;
}



// Minimum Waiting Time (1/26)
// find waiting time per query, given specific order
// say query in order 6,1,2, durations would be 0,6,6+1, respectively
// to minimize waiting time, find optimal "order"
// in this case, test two orders: 6,1 vs 1,6 give durations 0,6 vs 0,1
// so it doesn't make sense to process largest queries first
//
// every query needs to wait the remaining amount of queries left
// multiplied by the total waiting time so far

// first thing is ordering, best is nlogn
// time o(nlogn) | space o(1)
function minimumWaitingTime(queries) {
  queries.sort((a, b) => a - b);
  let totalWaitingTime = 0;

  for (let i = 0; i < queries.length; i++) {
    const remainingQueries = queries.length - (i + 1);
    totalWaitingTime += remainingQueries * queries[i];
  }

  return totalWaitingTime;
}


// Minimum Passes of Matrix (1/26)
// return passes - 1 if no negative vals after convertMatrix, else -1
// maintain nextQueue/currentQueue in a nested while loop fashion (won't affect runtime complexity)
// get all positive positions, assign to nextQueue
// make currentQueue nextQueue and empty out nextQueue, clear out currentQueue before starting 2nd outer loop
// get adjacent positions, loop through them, if -1 is found, flip, push pos as [row][col] to *emptied* nextQueue
// increment passes before next outer loop cycle

// time - we do a wh operation in beginning to look for positive intergers
// but then we'll never have to look at the same item more than once
// time o(wh) | space o(wh)
function minimumPassesOfMatrix(matrix) {
  const passes = convertMatrix(matrix);
  return !containsNegatives(matrix) ? passes - 1 : -1;
}

function convertMatrix(matrix) {
  let nextQueue = getAllPositivePositions(matrix);
  let passes = 0;

  while (nextQueue.length > 0) {
    const currentQueue = nextQueue;
    nextQueue = [];

    while (currentQueue.length > 0) {
      const [currentRow, currentCol] = currentQueue.shift();
      const positions = getAdjacentPositions(currentRow, currentCol, matrix);

      for (const [row, col] of positions) {
        if (matrix[row][col] < 0) {
          matrix[row][col] *= -1;
          nextQueue.push([row, col]);
        }
      }
    }

    passes++;
  }

  return passes;
}

function containsNegatives(matrix) {
  for (const row of matrix) {
    for (const value of row) {
      if (value < 0) return true;
    }
  }

  return false;
}

function getAllPositivePositions(matrix) {
  const positivePositions = [];

  for (let row = 0; row < matrix.length; row++) {
    for (let col = 0; col < matrix[row].length; col++) {
      if (matrix[row][col] > 0) positivePositions.push([row, col]);
    }
  }

  return positivePositions;
}

function getAdjacentPositions(row, col, matrix) {
  const positions = [];

  if (row > 0) positions.push([row - 1, col]);
  if (row < matrix.length - 1) positions.push([row + 1, col]);
  if (col > 0) positions.push([row, col - 1]);
  if (col < matrix[row].length - 1) positions.push([row, col + 1]);

  return positions;
}



// Cycle in Graph (1/25)
// create visited/inStack auxilary arrays, run dfs, mark node as visited and inStack
// recursive case sends in neighbor as node
// where neighbor element from iterable neighbors edges[node]
// recursion returns cycleExists bool so we can do early return if true
// as we finish processing, we unmark form inStack
// if we visit something still "inStack", its a cycle

// reminder: adjacency list - index itself represents vertex (node) while interior list represents outbound edges

// time - dfs considers all vertices + edges, space - auxilary DS
// there will never be more than v concurrent recursive calls on the call stack
// since there are v vertices in the graph and since our algorithm naturally stops at cycles
// thus, the recursive calls won't change the O(v) space complexity
// time o(v + e) | space o(v)
function cycleInGraph(edges) {
  const visited = edges.map((_) => 0);
  const inStack = edges.map((_) => 0);

  for (let node = 0; node < edges.length; node++) {
    const cycleExists = dfs(node, edges, visited, inStack);
    if (cycleExists) return true;
  }

  return false;
}

function dfs(node, edges, visited, inStack) {
  visited[node] = true;
  inStack[node] = true;

  const neighbors = edges[node];

  for (const neighbor of neighbors) {
    if (!visited[neighbor]) {
      const cycleExists = dfs(neighbor, edges, visited, inStack);
      if (cycleExists) return true;
    } else if (inStack[neighbor]) {
      return true;
    }
  }

  inStack[node] = false;
  return false;
}


// Remove Islands (1/25)
// problem asks to remove interior islands (1s to 0s) if they aren't connected to borders
// so run dfs starting at borders, replacing 1s with 2s
// then traverse matrix, setting 1's to 0's and 2's to 1's

// o(wh) space b/c we need a stack w/ potentially every single item on it
// it's better avg space complexity than v1 (not here) with auxilary array
// bc our stack might not always be as big as the matrix itself
// time o(wh) | space o(wh)
function removeIslands(matrix) {
  for (let row = 0; row < matrix.length; row++) {
    for (let col = 0; col < matrix[row].length; col++) {
      const rowIsBorder = row === 0 || row === matrix.length - 1;
      const colIsBorder = col === 0 || col === matrix[row].length - 1;
      const isBorder = rowIsBorder || colIsBorder;
      if (!isBorder) continue;
      dfs(matrix, row, col);
    }
  }

  for (let row = 0; row < matrix.length; row++) {
    for (let col = 0; col < matrix[row].length; col++) {
      const rowIsBorder = row === 0 || row === matrix.length - 1;
      const colIsBorder = col === 0 || col === matrix[row].length - 1;
      const isBorder = rowIsBorder || colIsBorder;
      const color = matrix[row][col];
      if (color === 1) {
        matrix[row][col] = 0;
      } else if (color === 2) {
        matrix[row][col] = 1;
      }
    }
  }

  return matrix;
}

function dfs(matrix, row, col) {
  const stack = [[row, col]];
  while (stack.length > 0) {
    const curr = stack.pop();
    const [row, col] = curr;
    if (matrix[row][col] === 1) {
      matrix[row][col] = 2;
      pushIfValid(matrix, row + 1, col, stack);
      pushIfValid(matrix, row - 1, col, stack);
      pushIfValid(matrix, row, col + 1, stack);
      pushIfValid(matrix, row, col - 1, stack);
    }
  }
}

function pushIfValid(matrix, row, col, stack) {
  if (row >= 0 && row < matrix.length && col >= 0 && col < matrix[row].length) {
    stack.push([row, col]);
  }
}



// Node Depths (1/24)
// at root node, depth is 0. have all parents inform child (my depth + 1)

// time o(n) | space o(n)
function nodeDepths(root) {
  let sum = 0;
  const stack = [{ node: root, depth: 0 }];
  while (stack.length > 0) {
    const curr = stack.pop();
    if (!curr.node) continue;
    sum += curr.depth;
    stack.push({ node: curr.node.left, depth: curr.depth + 1 });
    stack.push({ node: curr.node.right, depth: curr.depth + 1 });
  }
  return sum;
}

// to avoid having to store a global sum variable, we can pass sums as returns

// time o(n) | space o(h)
// time - we're traversing through every node in the tree, n nodes
// at every node, we're only doing constant time operations
// space - where h is height - max function calls in the call stack at one point
// is the height of the tree (or depth of deepest node in tree)
// fyi, for an unbalanced tree, o(h) starts looking like o(n)
function nodeDepthsRecursive(node, depth = 0) {
  if (!node) return 0;
  return (
    depth + nodeDepths(node.left, depth + 1) + nodeDepths(node.right, depth + 1)
  );
}



// Branch Sums (1/24)
// pre-order traversal, don't forget to return after array.push
// we'll have as many branches as we have branchSums
// in other words, !node.left && !node.right condition counts n branches (space complexity)

// time o(n) | space o(n)
function branchSums(root) {
  const branchSums = [];
  helper(root, 0, branchSums);
  return branchSums;
}

function helper(node, currentSum, branchSums) {
  if (!node) return;

  currentSum += node.value;
  if (!node.left && !node.right) {
    branchSums.push(currentSum);
    return;
  }
  helper(node.left, currentSum, branchSums);
  helper(node.right, currentSum, branchSums);
}



// Shifted Binary Search (1/14)
// move to the sorted side, negate the premise that target should be there

// time o(log n) | space o(log n)
function shiftedBinarySearch(array, target) {
  return helper(array, target, 0, array.length - 1);
}

function helper(array, target, left, right) {
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const leftVal = array[left];
    const rightVal = array[right];
    const potentialMatch = array[mid];
    console.log(potentialMatch);
    if (target === potentialMatch) return mid;
    if (leftVal < potentialMatch) {
      if (target < potentialMatch && target >= leftVal) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    } else {
      if (target > potentialMatch && target <= rightVal) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }
  return -1;
}



// Reverse Words In String (1/12)

// time o(n) | space o(n)
function reverseWordsInString(string) {
  if (string.length === "") return "";

  const result = [];
  const sections = splitHelper(string);

  for (let i = sections.length; i >= 0; i--) {
    result.push(sections[i]);
  }

  return result.join("");
}

function splitHelper(string) {
  const result = [];
  let left = 0;
  for (let i = 0; i < string.length; i++) {
    const prev = string[i - 1];
    const curr = string[i];
    if ((prev !== " " && curr === " ") || (prev === " " && curr !== " ")) {
      result.push(string.slice(left, i));
      left = i;
    }
  }

  result.push(string.slice(left));

  return result;
}



// Valid IP Addresses (1/12)
// 3 nested loops using Max.min as limits gives behavior we want
// slice 1 -> 0, i / slice 2 -> i, j / slice 3 -> j, k / slice 4 -> k, end
// reminder about data types (parseInt, toString) during validation

// time o(1) | space o(1)
function validIPAddresses(string) {
  const results = [];

  for (let i = 0; i < Math.min(string.length, 4); i++) {
    const ipAddressSections = [[], [], [], []];

    ipAddressSections[0] = string.slice(0, i);
    if (!isValid(ipAddressSections[0])) continue;

    for (let j = i + 1; j < i + Math.min(string.length - i, 4); j++) {
      ipAddressSections[1] = string.slice(i, j);
      if (!isValid(ipAddressSections[1])) continue;

      for (let k = j + 1; k < j + Math.min(string.length - j, 4); k++) {
        ipAddressSections[2] = string.slice(j, k);
        ipAddressSections[3] = string.slice(k);

        if (!isValid(ipAddressSections[2])) continue;
        if (!isValid(ipAddressSections[3])) continue;

        results.push(ipAddressSections.join("."));
      }
    }
  }

  return results;
}



function isValid(section) {
	if (section === '') return false;
	if (section.length > 1 && section[0] === '0') return false;
	if (parseInt(section) < 0 || parseInt(section) > 255) return false;
	return true;
}


// Longest Palindromic Substring (1/12)
// odd palindrome - left/right is i - i, i + 1
// even palindrome - left/right is i - 1, i
// expand left/right while chars are equal, return leftIdx, rightIdx
// compute longest based on length of even vs odd variables

// time o(n^2) | space(n)
function longestPalindromicSubstring(string) {
  let currentLongest = [0, 1];

  for (let i = 1; i < string.length; i++) {
    const odd = getLongestPalindromeFrom(string, i - 1, i + 1);
    const even = getLongestPalindromeFrom(string, i - 1, i);
    const longest = even[1] - even[0] > odd[1] - odd[0] ? even : odd;
    if (longest[1] - longest[0] > currentLongest[1] - currentLongest[0])
      currentLongest = longest;
  }

  return string.slice(currentLongest[0], currentLongest[1]);
}

function getLongestPalindromeFrom(string, leftIdx, rightIdx) {
  while (leftIdx >= 0 && rightIdx < string.length) {
    if (string[leftIdx] !== string[rightIdx]) break;
    leftIdx--;
    rightIdx++;
  }
  return [leftIdx + 1, rightIdx];
}



// Longest Substring Without Duplicating (1/6)
// ensure we account for old duplicates using max of lastSeen + 1 vs charIdx
// use location = [left, right], no need for extra auxilary space

// time o(n) | space o(n)
function longestSubstringWithoutDuplication(string) {
  let longest = [0, 1];
  const lastSeen = {};
  let left = 0;

  for (let i = 0; i < string.length; i++) {
    const char = string[i];

    if (char in lastSeen) {
      left = Math.max(left, lastSeen[char] + 1);
    }

    if (longest[1] - longest[0] < i + 1 - left) {
      longest = [left, i + 1];
    }

    lastSeen[char] = i;
  }

  return string.slice(longest[0], longest[1]);
}



// Apartment Hunting (1/5)
// precompute list of min distances per req
//   for req in reqs
//     initialize distances list with 0s per block
//     initialize lastSeen as Infinity, this saves index i from 0 to blocks.length the the loops below
//     move forward, then backwards - tracking the last seen location per req
//       forward (left/right for i loop), save lastSeen as i if blocks[i][req]
//          then continue to compute distances list with distance between i vs lastSeen location of the current req
//       backwards (right/left for i loop), save lastSeen as i if blocks[i][req]
//          then continue to compute distances list as distances[i] = distanceBetween(i, lastSeen)
//	      and distance between current vs lastSeen from right/left
//          this ensures right to left distances are computed and compared with previous computations...
//		   
//
// initialize/fill maxDistancePerBlock to -Infinity, same size as we have blocks
// for minDistances in minDistancesPerReq, compute maxDistancePerBlock
// for distance in maxDistancePerBlock, compute minDistance and track its idx
// return minDistance's idx

// time | space o(B + BR) = B(R+1) = o(BR)
function apartmentHunting(blocks, reqs) {
  const minDistances = getMinDistancesPerReq(blocks, reqs); // o(B*R) space
  const maxDistancePerBlock = blocks.map((_) => -Infinity); // o(B) space
  blocks.forEach((block, idx) => {
    minDistances.forEach((minDistance) => {
      maxDistancePerBlock[idx] = Math.max(
        maxDistancePerBlock[idx],
        minDistance[idx]
      );
    });
  });

  return getMinDistanceIdx(maxDistancePerBlock);
}

function getMinDistancesPerReq(blocks, reqs) {
  const results = [];
  reqs.forEach((req) => {
    const distances = blocks.map((_) => 0);
    let lastSeen = Infinity;
    for (let i = 0; i < blocks.length; i++) {
      if (blocks[i][req]) lastSeen = i;
      distances[i] = distanceBetween(i, lastSeen);
    }
    for (let i = blocks.length - 1; i >= 0; i--) {
      if (blocks[i][req]) lastSeen = i;
      distances[i] = Math.min(distances[i], distanceBetween(i, lastSeen));
    }

    results.push(distances);
  });

  return results;
}

function distanceBetween(a, b) {
  return Math.abs(a - b);
}

function getMinDistanceIdx(maxDistancePerBlock) {
  let min = Infinity;
  let minIdx = 0;
  for (let i = 0; i < maxDistancePerBlock.length; i++) {
    if (maxDistancePerBlock[i] < min) {
      min = maxDistancePerBlock[i];
      minIdx = i;
    }
  }
  return minIdx;
}



// Min Rewards (12/30)
// reset everything to 1 knowing all students get at least that
// in a left/right pass-throguh, compute rewards as curr is prev + 1 (if curr is bigger)
// in a right/left pass-through, re-compute as max of curr vs prev + 1

// time o(n) | space o(n)
function minRewards(scores) {
  const rewards = scores.map((_) => 1);
  for (let i = 1; i < scores.length; i++) {
    if (scores[i] > scores[i - 1]) rewards[i] = rewards[i - 1] + 1;
  }
  for (let i = scores.length - 2; i >= 0; i--) {
    if (scores[i] > scores[i + 1])
      rewards[i] = Math.max(rewards[i], rewards[i + 1] + 1);
  }
  return rewards.reduce((a, b) => a + b);
}



// Largest Range (12/28)
// store every num in visited table pointing to a bool true
// if marked as true, expand outwards to find range it contains
// as we expand, check if new nums are in visited and if so, mark as visited (set false)

// time o(n) | space o(n)
function largestRange(array) {
  let longestLength = 0;
  let bestRange = [];
  const nums = {};
  for (num of array) {
    nums[num] = true;
  }
  for (num of array) {
    if (!(num in nums)) continue;
    nums[num] = false;
    let currentLength = 1;
    let left = num - 1;
    let right = num + 1;
    while (left in nums) {
      nums[left] = false;
      left--;
      currentLength++;
    }
    while (right in nums) {
      nums[right] = false;
      right++;
      currentLength++;
    }
    if (currentLength > longestLength) {
      longestLength = currentLength;
      bestRange = [left + 1, right - 1];
    }
  }
  return bestRange;
}



// Sub Array Sort (12/28)
// first pass - find min/max values within out of order indicies
// sec/third pass - from left/right and right/left, find final positions

// time o(n) | space o(1)
function subarraySort(array) {
  let min = Infinity;
  let max = -Infinity;

  for (let i = 0; i < array.length; i++) {
    const num = array[i];
    if (isOutOfOrder(num, array, i)) {
      min = Math.min(min, array[i]);
      max = Math.max(max, array[i]);
    }
  }

  if (min === Infinity) return [-1, -1];

  let start = 0;
  let end = array.length - 1;

  while (min >= array[start]) start++;
  while (max <= array[end]) end--;

  return [start, end];
}

function isOutOfOrder(num, array, i) {
  if (i === 0) return num > array[i + 1];
  if (i === array.length - 1) return num < array[i - 1];
  return num > array[i + 1] || num < array[i - 1];
}



// Four Number Sum (12/26)
// 1st inner for loop - check for results
// 2nd inner for loop - create quadruplets

// avg: o(n^2) time | o(n^2) space
// worst: o(n^3) time | o(n^2) space
function fourNumberSum(array, targetSum) {
  const results = [];
  const hash = {};
  for (let i = 0; i < array.length; i++) {
    for (let k = i + 1; k < array.length; k++) {
      const currentSum = array[i] + array[k];
      const remainder = targetSum - currentSum;
      if (hash[remainder]) {
        const pairs = hash[remainder];
        pairs.forEach((pair) => results.push([...pair, array[i], array[k]]));
      }
    }
    for (let j = 0; j < i; j++) {
      const currentSum = array[i] + array[j];
      if (hash[currentSum]) {
        hash[currentSum].push([array[i], array[j]]);
      } else {
        hash[currentSum] = [[array[i], array[j]]];
      }
    }
  }
  return results;
}



// Merge Overlapping Intervals (12/26)
// sort first!
// merge item by item while updating last item from results array

// time o(n log n)| space o(n)
function mergeOverlappingIntervals(array) {
  array.sort((a, b) => a[0] - b[0]);
  const results = [];
  results.push(array[0]);

  for (let i = 1; i < array.length; i++) {
    const intervalOne = results[results.length - 1];
    const intervalTwo = array[i];
    if (intervalTwo[0] <= intervalOne[1]) {
      results[results.length - 1][1] = Math.max(intervalOne[1], intervalTwo[1]);
    } else {
      results.push(array[i]);
    }
  }

  return results;
}



// Min Height BST (12/07)
// remember to pass null as that's when we arrive at null children nodes

// o(n) time | o(n) space
function minHeightBst(array) {
  return constructMinHeightBst(array, 0, array.length - 1);
}

function constructMinHeightBst(array, startIdx, endIdx) {
  if (endIdx < startIdx) return null;

  const midIdx = Math.floor((startIdx + endIdx) / 2);

  const bst = new BST(array[midIdx]);

  bst.left = constructMinHeightBst(array, startIdx, midIdx - 1);
  bst.right = constructMinHeightBst(array, midIdx + 1, endIdx);

  return bst;
}



// Insertion Sort (12/07)
// divide into two subarrays (sorted, non-sorted), swap as needed until item 0

// best: o(n) time | o(1) space
// avg: o(n^2) time | o(1) space
// worst: o(n^2) time | o(1) space
function insertionSort(array) {
  for (let i = 1; i < array.length; i++) {
    let j = i;
    while (j > 0 && array[j] < array[j - 1]) {
      swap(j, j - 1, array);
      j--;
    }
  }
  return array;
}

function swap(j, i, array) {
  const temp = array[j];
  array[j] = array[i];
  array[i] = temp;
}



// Run Length Encoding (12/07)

// use array, not string
// use for i loop, not while, no need to handle incrementing i separately
// good variable names perfect to avoid cryptic code
// push when 9 or when they don't match
// handle last run explicitly
// o(n) time | o(n) space - where n is length of input

function runLengthEncoding(string) {
  const encodedStringCharacters = [];
  let currentRunLength = 1;
  for (let i = 1; i < string.length; i++) {
    const currentCharacter = string[i];
    const previousCharacter = string[i - 1];

    if (currentCharacter !== previousCharacter || currentRunLength === 9) {
      encodedStringCharacters.push(currentRunLength.toString());
      encodedStringCharacters.push(previousCharacter);
      currentRunLength = 0;
    }

    currentRunLength++;
  }

  encodedStringCharacters.push(currentRunLength.toString());
  encodedStringCharacters.push(string[string.length - 1]);

  return encodedStringCharacters.join("");
}



// Binary tree diameter (12/06)

class BinaryTree {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class TreeInfo {
  constructor(diameter, height) {
    this.diameter = diameter;
    this.height = height;
  }
}

function binaryTreeDiameter(tree) {
  return helper(tree).diameter;
}

function helper(node) {
  if (node === null) return new TreeInfo(0, 0);

  const left = helper(node.left);
  const right = helper(node.right);

  const longestPathThroughRoot = left.height + right.height;
  const maxDiameterSoFar = Math.max(left.diameter, right.diameter);
  const currentDiameter = Math.max(longestPathThroughRoot, maxDiameterSoFar);
  const currentHeight = 1 + Math.max(left.height, right.height);

  return new TreeInfo(currentDiameter, currentHeight);
}



// Group Anagrams (12/06)

function groupAnagrams(words) {
  const anagrams = {};
  for (const word of words) {
    const sortedWord = word.split("").sort().join("");
    if (sortedWord in anagrams) {
      anagrams[sortedWord].push(word);
    } else {
      anagrams[sortedWord] = [word];
    }
  }
  return Object.values(anagrams);
}



// Breath-first search (12/06)

class Node {
  constructor(name) {
    this.name = name;
    this.children = [];
  }

  addChild(name) {
    this.children.push(new Node(name));
    return this;
  }

  breadthFirstSearch(array) {
    const queue = [this];
    while (queue.length > 0) {
      const curr = queue.shift();
      array.push(curr.name);
      curr.children.forEach((child) => {
        queue.push(child);
      });
    }
    return array;
  }
}