General purporses algorithms implemented in JavaScript.

algorithms_good_to_know.md

maximum subarray sum

Kadane's algorithm

code

/**
 * @param {number[]} arr - Array com valores arbitrários.
 * @returns {number} O valor do subarray com maior soma em `arr`.
 */
function maxSubArrSum(arr) { // O(n) em tempo e O(1) em espaço
  let maxSum = arr[0] || Number.MIN_VALUE;
  let currSum = maxSum;

  for (let i=1; i < arr.length; ++i) {
    currSum = Math.max(arr[i], currSum + arr[i]); 
    maxSum = Math.max(maxSum, currSum);
  }

  return maxSum;
}

maxSubArrSum([-2, 1, -3, 4, -1, 2, 1, -5, 4]) === 6
//                      \__________/

Knuth shuffle

code

/**
 * @param {any[]} arr - Array com valores arbitrários.
 * @returns {any[]} O mesmo array `arr` mas com os itens (potencialmente)
 * trocas de ordem de maneira aleatória.
 */
function shuffleInplace(arr) { // O(n) em tempo e O(1) em espaço
  for (let i=items.length-1; i > 0; --i) {
    const randomIdx = randomIntFromInterval(0, i)
    const randomElem = arr[randomIdx]
    // swap
    arr[randomIdx] = arr[i]
    arr[i] = randomElem
  }
  return arr;
}

function randomIntFromInterval(min, max) {
  return Math.floor(Math.random() * (max - min + 1) + min)
}

single number

code

/**
 * @param {number[]} nums - Array não vazio de inteiros,
 * onde cada elemento aparece duas vezes, exceto um.
 * @returns {number} O único elemento que não se repete em `nums`.
 */
function singleNumber(nums) { // O(n) em tempo e O(1) em espaço
  let badNum = 0
  for (const num of nums) badNum ^= num
  return badNum
}

since:

• a XOR a = 0
• a XOR 0 = a
• (a XOR b) XOR c = a XOR b XOR c

total occurrences of K in a sorted array

code

/**
 * @param {number[]} arr - Array ordenado em ordem crescente.
 * @param {number} k - Elemento a ser procurado em `arr`.
 * @returns {number} Quantidade de vezes em que `k` aparece em `arr`.
 */
function getOccurrencesOfK(arr, k) { // O(log n) em tempo; O(n) em espaço por ser recursivo
  const firstOccurrence = binarySearch('FIRST', {
    array: arr,
    value: k,
    start: 0,
    end: arr.length-1,
  })
  if (firstOccurrence < 0) return 0

  const lastOccurrence = binarySearch('LAST', {
    array: arr,
    value: k,
    start: 0,
    end: arr.length-1,
  })

  return lastOccurrence - firstOccurrence + 1
}

/**
 * @param {'FIRST' | 'LAST'} kind
 * @param {object} params
 * @returns {number}
 */
function binarySearch(kind, { array, value, start, end }) {
  if (array.length === 0 || start > end) return -1

  /**
   * @param {number} val
   * @returns {boolean}
   */
  const isInBounds = (val) => val < array.length

  const mid = start + Math.floor((end - start)/2)
  if (array[mid] === value) {
    if (kind === 'FIRST') {
      if (isInBounds(mid-1) && array[mid] === array[mid-1])
        return binarySearch(kind, {
          array, 
          value,
          start: start,
          end: mid-1,
        })
    }

    if (kind === 'LAST') {
      if (isInBounds(mid+1) && array[mid] === array[mid+1])
        return binarySearch(kind, {
          array, 
          value,
          start: mid+1,
          end: end,
        })
    }
      
    return mid
  } else if (array[mid] < value) {
    return binarySearch(kind, {
      array,
      value,
      start: mid+1,
      end: end,
    })
  } else {
    return binarySearch(kind, {
      array,
      value,
      start: start,
      end: mid-1,
    })
  }
}

find the second largest item

• pode-se usar um min-heap de capacidade 2;
• ou two pointers

code

/**
 * @param {number[]} numbers
 * @returns {number|undefined}
 */
function findSecondLargest(numbers) { // O(n) em tempo e O(1) em espaço
  if (numbers.length < 2) return numbers[0]

  let max = Number.MIN_VALUE
  let secondMax = Number.MIN_VALUE
  for (const currNum of numbers) {
    const newMax = Math.max(currNum, max)
    const newSecondMax = Math.max(max, secondMax)
    max = newMax
    secondMax = newSecondMax
    /*
    if (currNum > max) {
      secondMax = max
      max = currNum
    } else if (currNum > secondMax) {
      if (max !== currNum)
        secondMax = currNum
    }
    */
  }
 
  return secondMax
}


findSecondLargest([-1, 10, 8, 9, 10, 9, -8, 11]) === 10