optimistiks

export function wordBreak(s, wordDict){
    // so the idea of the bottom up solution is 
    // that we have a 2d dp array,
    // where dp[i] is an array of all possible sentences that can be formed from an ith prefix of s
    // where ith prefix of s is a substring of s from index 0 to index i [0, i)
    // we also add a 0th element to the dp which is an "empty string" prefix,
    // with the value of [""], since the only sentence you can make out of an empty string is an empty string
    const dp = Array(s.length + 1).fill().map(() => []);
    dp[0] = [""];
    // now we are going to iterate prefixes of s

optimistiks

function numOfDecodings(decodeStr) {
  const dp = Array(decodeStr.length + 1).fill(0);
  dp[0] = 1;

  // when we are at character (i-1)
  // if it's a valid character, it means that
  // at this point, the number of ways to decode remains the same as it was
  // prior to that character
  // however, if we can also form a double digit from this character (by going left)
  // and if the double digit is valid

optimistiks

export function climbStairs(nums) {
  const dp = Array.from(nums).fill(0);
  dp[0] = 1;
  dp[1] = 1;
  // ways to reach step i = ways to reach step i-1 + ways to reach step i-2
  for (let i = 2; i <= nums; ++i) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[nums];
}

optimistiks

export function findMissingNumber(nums) {
  let i = 0;

  // apply cyclic sort to place values at their indexes (e.g. value 2 goes to index 2)
  while (i < nums.length) {
    if (nums[i] !== i && nums[nums[i]] != null) {
      const tmp = nums[nums[i]];
      nums[nums[i]] = nums[i];
      nums[i] = tmp;
    } else {

optimistiks

import { cyclicSort } from "./cyclic_sort.js";

export function smallestMissingPositiveInteger(nums) {
  // we're going to apply cyclic sort
  // we only apply it to items between 1 and n, to keep the O(n)
  // we ignore items that are less than 0, as well as items that are greater than nums.length
  // this way we will place items in a way that value === index - 1
  // so item with value 1 will end up at index 0, value 2 at index 1 and so on
  // so after we do that, it will be easy to find the first missing positive element
  // it will be the first case when value !== i-1 (the missing value will be i+1)

optimistiks

export function findCorruptPair(nums) {
  let i = 0;

  // since our nums[i] is >= 1 and <= nums.length
  // we can apply cycle sort and remain O(n)
  // since we know that there is exactly one missing and one duplicated element
  // we sort our nums using cycle sort
  // and then find the first mismatch between an index and a value at the index
  // that first mismatch will give us the missing value (index+1), as well as the duplicated value nums[index]

optimistiks

export function firstKMissingNumbers(arr, k) {
  // first we apply cycle sort to elements in range 0 < value <= arr.length
  // this way we ensure cycle sort is O(n)
  let i = 0;
  while (i < arr.length) {
    const value = arr[i];
    const index = arr[i] - 1;
    if (
      value !== i + 1 &&
      index >= 0 &&

optimistiks

export function findCompilationOrder(dependencies) {
  const adjList = {};
  // store indegree of each vertex (indegree = how many edges are inbound)
  const indegrees = {};

  // initialize our adj list and indegrees map
  for (let i = 0; i < dependencies.length; ++i) {
    const [to, from] = dependencies[i];
    adjList[from] = [];
    adjList[to] = [];

optimistiks

export function alienOrder(words) {
  const adjList = {};
  const indegreeMap = {};

  // initialize adjacency list and indegree map
  for (let i = 0; i < words.length; ++i) {
    const word = words[i];
    for (let j = 0; j < word.length; ++j) {
      const letter = word[j];
      indegreeMap[letter] = 0;

optimistiks

export function verifyAlienDictionary(words, order) {
  // store letter positions in a hashmap
  // so we can get a letter position in constant time
  const foundChars = {};
  for (let i = 0; i < order.length; ++i) {
    foundChars[order[i]] = i;
  }

  // flag if the sorting is invalid
  let exit = false;