optimistiks

export function search(arr, t) {
  // start as normal binary search
  let low = 0;
  let high = arr.length - 1;

  while (low <= high) {
    const mid = Math.floor((high - low) / 2) + low;
    // if we found our target at mid, return true
    if (arr[mid] === t) {
      return true;

optimistiks

export function findAllSubsets(v) {
  if (v.length === 0) {
    return [[]];
  }

  const sets = [];

  // total number of subsets is 2^n
  const subsetsCount = 2 ** v.length;
  console.log("total subsets", subsetsCount);

optimistiks

function swap(word, i, j) {
  let swapIndex = word.split("");
  let temp = swapIndex[j];
  swapIndex[j] = swapIndex[i];
  swapIndex[i] = temp;
  return swapIndex.join("");
}

function permuteStringRec(word, pointer, result) {
  // pointer is a number indication an index of a character in the string

optimistiks

const lettersMap = {
  1: [" "],
  2: ["a", "b", "c"],
  3: ["d", "e", "f"],
  4: ["g", "h", "i"],
  5: ["j", "k", "l"],
  6: ["m", "n", "o"],
  7: ["p", "q", "r", "s"],
  8: ["t", "u", "v"],
  9: ["w", "x", "y", "z"],

optimistiks

function generateCombinationsRec(n, numOpen, numClosed, combo, result) {
  // base case - length of the combination is n * 2
  if (combo.length === n * 2) {
    result.push(combo);
    return;
  }

  // can we add an opening bracket to the current combination?
  // yes if number of opening brackets in the combination is less than n
  // so we add it, and pass it further to add more brackets, incrementing numOpen

optimistiks

export function jumpGame(nums) {
  // take last element as our target
  let target = nums.length - 1;
  // start iterating from the element preceding the last, backwards
  for (let i = nums.length - 2; i >= 0; --i) {
    const preceding = i;
    const diff = target - preceding;
    // the target element is reachable from the preceding element,
    // if preceding element value is greater or equal to the difference between target and preceding index
    // for example, element at index 5 is reachable from element at index 4 if value at index 4 is 1 or more

optimistiks

// people is an array of numbers, each number represents a person's weight
// limit is the max weight of a boat
// the number of boats is unlimited
// find minimum number of boats
export function rescueBoats(people, limit) {
  // sort people by weight
  people.sort();

  // set first pointer to point at the lightest person
  let light = 0;

optimistiks

// gas is an array of numbers, where each number represents the amount of gas we can put in our car fuel tank on ith gas station.
// cost is how much gas we need to spend to move from gas station i to gas station i+1.
// we need to find an index of the gas station from which we can start our journey and visit every gas station.
export function gasStationJourney(gas, cost) {
  // first, calculate total amount of gas in all gas stations
  const totalGas = gas.reduce((acc, amount) => acc + amount, 0);
  // second, calculate the gas cost of the whole journey
  const totalCost = cost.reduce((acc, amount) => acc + amount, 0);

  if (totalCost > totalGas) {

optimistiks

export function twoCityScheduling(costs) {
  // create an array of cost differences and sort it ascending
  const diffs = costs.map(([costA, costB]) => costA - costB);
  diffs.sort((a, b) => a - b);

  // get a sum of all costs to city A (like we sent all people to city A)
  let sumA = costs.reduce((sum, [costA]) => sum + costA, 0);

  // since we are actually sending the second half of people (by diffs) to city B
  // subtract their differences (think refunds) from the sumA

optimistiks

export function minRefuelStops(target, startFuel, stations) {
  if (startFuel >= target) {
    // if we have enough fuel to cover the target
    return 0;
  }

  // we're going to store fuels of reachable stations in a max heap
  const heap = new MaxHeap();
  // max distance that we can cover in the current moment (equals to amount of fuel since 1 mile = 1 fuel)
  let maxDistance = startFuel;