optimistiks

export function jumpGameTwo(nums) {
  if (nums.length === 1) {
    return 0;
  }

  // our current position in the array
  let current = 0;
  // the farthest index that is reachable from elements iterated up until now
  let farthest = 0;
  // number of jumps done

optimistiks

// to check diagonals,
// row - col for neg diag,
// row + col for pos diag,
// those values will remain constant along the whole diagonal
function canPlace(row, col, result) {
  for (let boardRow = 0; boardRow < row; ++boardRow) {
    const boardCol = result[boardRow];
    if (col === boardCol) {
      // col is taken
      return false;

optimistiks

export function wordSearch(grid, word) {
  for (let row = 0; row < grid.length; ++row) {
    for (let col = 0; col < grid[row].length; ++col) {
      const result = wordSearchRec(grid, word, row, col, 0);
      if (result) {
        return true;
      }
    }
  }
  return false;

optimistiks

export function rob(root) {
  const result = robRec(root);
  return Math.max(...result);
}

function robRec(node) {
  if (!node.left && !node.right) {
    return [node.data, 0];
  }
  const [includingRootLeft, excludingRootLeft] = node.left

optimistiks

export function restoreIpAddresses(s) {
  const addresses = [];
  const segments = [];
  restoreIpRec(s, 0, 3, segments, addresses);
  return addresses;
}

function restoreIpRec(s, pos, dots, segments, addresses) {
  if (dots === 0) {
    // base case, dots === 0 meaning there are no dots left to place

optimistiks

let DIGITS = ["1", "2", "3", "4", "5", "6", "7", "8", "9"];

export function solveSudoku(board) {
  const sets = createSets();
  const emptyCells = [];
  // iterate board, add empty cells to the list of empty cells,
  // add values of nonempty cells to row, col and subbox sets,
  // so we can later check if value present in a row / col / subbox
  // by checking the corresponding set
  for (let row = 0; row < board.length; ++row) {

optimistiks

function floodFill(grid, sr, sc, target) {
    // last argument is the original value that was in the source cell
    // (which is the value that an adjacent cell must have for the fill to continue)
    // since its our first call we pass null
    // so this value can be initialized
    floodFillRec(grid, sr, sc, target, null) 
    return grid
}

function floodFillRec(grid, sr, sc, target, prevV) {

optimistiks

export function matchstickToSquare(matchsticks) {
  // find total sum of matchsticks lengths
  const sum = matchsticks.reduce((sum, len) => sum + len, 0);
  // if sum cant be divided by 4 or there are less than 4 matchsticks, not possible
  if (sum % 4 !== 0 || matchsticks.length < 4) {
    return false;
  }
  // target is our square side length
  const target = sum / 4;
  // initialize sides lengths with zeros

optimistiks

export function findMaxKnapsackProfit(capacity, weights, values) {
  // a single array version,
  // it's an optimized two-array version (repeatedly swap two arrays to hold previous and current row)
  // which is in itself an optimized 2d array solution
  const dp = Array(capacity + 1).fill(0);

  // first we build an array of solutions for each possible capacity with only the first item considered
  // then we update the array by considering the second item
  // after that array contains optimal solutions with both items considered, so we can move to third, and so on
  for (let item = 0; item < weights.length; ++item) {

optimistiks

export function coinChange(coins, total) {
  // we make a total + 1 counter,
  // so later when we need to "ask" this array for a subproblem solution
  // it will look more natural, counter[total] (give me solution for total),
  // instead of doing -1 every time for index offset (counter[total-1])
  const counter = Array(total + 1).fill(null);
  // your code will replace this placeholder return statement
  return coinsChangeRec(coins, total, counter);
}