Algorithms: Big O Notation

Time Complexity

Specifies the relationship between the number of operations performed across different Input Sizes for a Function. (Which in turn impacts the total amount of time a Function may take to run to completion.)
- It's convenient to think of Time Complexity as successively running a Function with increasing or decreasing Input Sizes.
- In practice, most computers run so quickly that there's no discernible difference in the amount of time to any kind of Function for small Input Sizes.
- Time Complexity (e.g. Asymptotic Analysis) instead is concerned with the abstract mathematical relationships between a Function, its Control Flow, the number of operations it performs, the Input Size, and its Computability.
By convention, Average Big O Time Complexity almost always indicates the worst-case time complexity.
- It's also standard practice to drop multiples e.g. - O(2n) is usually just written as O(n).
Time Complexity is almost always measured using Big O Notation.

Big O Notation

Given an input n, calculate, a priori, abstracting away certain physical implementation specifics, the time it takes to execute an algorithm relative to n. By convention, Big O Notation typically measures only the worst-case time complexity (upper bound).

Formal Definition

The best formal definition I’ve found:

Where f, g are functions from N to the positive reals, R+; and
Where O(g) is a set of functions from N to the positive reals, R+; and
Where ∈ stands for the elemental inclusion operator:
- f ∈ O(g) means: asymptotically and ignoring constant factors, f does not grow more quickly than g over time or input size.
- f ∈ O(g) means: asymptotically and ignoring constant factors, g is the worst-case time complexity for f over time or input size.

Refer to: http://www.uni-forst.gwdg.de/~wkurth/cb/html/cs1_v06.pdf

Constant Time

Invariant, constant or unchanging, Time-Complexity. The number of operations performed remains constant and does not depend on the Input Size:

O(1)

Example:

const f = n => {
    console.log(1)
    return 1
}

f(0)
f(1)
f(5)
f(15)

0 -> 1
1 -> 1
5 -> 1
15 -> 1

Example: only returning a Constant Value.

Linear Time

Time-Complexity is Directly Proportional to (the number of Inputs) n:

O(n)

Example:

const f = n => {
  let v = 0

  for (let i = 0; i < n; i++) {
    v++ 
  }

  return v 
}

console.log(f(0))
console.log(f(1))
console.log(f(5))
console.log(f(10))

0 -> 0
1 -> 1
5 -> 5
10 -> 10

Example: un-nested looping once or more through an Array.

Logarithmic Time

The Time Complexity Logarithmically (gradually and varyingly) decreases (or increases) relative to change in Input Size, Not Constant, Linear, or Exponential.

O(log(n))

Example:

const f = n => { 
  let v = 0
    
  for (let i = 0; i < n; i++) { 
      i *= 2 
      v = i
  }

  console.log(v)
  return 1 
}
  
f(3)
f(4)
f(5)
f(6)

3 -> 2
4 -> 6
5 -> 6
6 -> 6
// Time Complexity:        2 6 6 6
// First Order Derivative:  4 0 0      
// Doesn't increase linearly or exponentially. 
// Total growth in number of operations decreases,
// The First Order Derivative varies.

Example: successively halving or doubling a bounding number.
If graphed, is/depicts a Logarithmic Function and/or Logarithmic relationship.
Paradigmatic examples are typified by both an Inner and Outer Time Complexity that performs more efficiently as either the Function continues to run (e.g. - the remaining number of operations halves successively) or the Input Size grows.
- Note: we can think of a Function as being composed of multiple, Inner, Functions. (Indeed, we often refactor Functions in just that way!)
- As such, we can consider both the overall Function's Time Complexity as the sum of the Inner ones and the Time Complexity of some Scope of a Function as it continues to run.
- Paradigmatic Logarithmic Functions therefore exhibt dual efficiences (they get more efficient as they run and more efficient w.r.t. Input Size) that Linear and Quadratic Time Complexities don't.

Logarithms and Logarithmic Functions

log specifies how much, n, the Base, β is raised to in order to obtain some x (e.g. - finds the Exponent given βⁿ = x):
- logᵦ(x) = n if and only if (βⁿ = x)
- (log baseᵦ x = n) if and only if (βⁿ = x)
- E.g. - (log base₂ 64 = 6) if and only if (2⁶ = 64)
- E.g. - (log₂ 64 = 6) if and only if (2⁶ = 64)
log(x) = y is written as shorthand for an assumed or suppressed Base β:
- E.g. - when using Base 10 log₁₀(x) = y .
- When using Big O Notation, the assumed Base is usually taken to be Base 2 (Binary, base₂, 2, or log₂(x) = y).

https://en.wikipedia.org/wiki/Logarithm and notes on logarithms

Quadratic Time

Time-Complexity increases Exponentially with respect to (the number of inputs) n.

O(nˣ) | x > 1

Example (every index is traversed at every index):

const f = n => {
  let v = 0
  for (let i = 0; i < n; i++) { 
      for (j = 0; j < n; j++) { 
        v++ 
      } 
  } 
  console.log(v)
  return v 
}

f(3)
f(4)
f(5)
f(6)

3 -> 3, 3, 3 = 9
4 -> 4, 4, 4, 4 = 16
5 -> 5, 5, 5, 5, 5 = 25
6 -> 6, 6, 6, 6, 6, 6 = 36
// Time Complexity:        9 16 25 35
// First Order Derivative:   7 9 10
// Exponentially increases as input size grows.

Example (every index from the current one is traversed at every index):

const g = n => {
  let v = 0
  for (let i = 0; i < n; i++) { 
      for (j = i; j < n; j++) { 
        v++ 
      } 
  } 
  console.log(v)
  return v 
}

g(3)
g(4)
g(5)
g(6)

3 -> 3, 2, 1 = 6
4 -> 4, 3, 2, 1 = 10
5 -> 5, 4, 3, 2, 1 = 15
6 -> 6, 5, 4, 3, 2, 1 = 21
// Time Complexity:        6 10 15 21
// First Order Derivative:   4 5 6
// Exponentially increases as input size grows.

Example: nested loops (a loop within a loop).

Calculations

Big O calculations can be combined:

Consider multiple, nested, loops: O(x) * O(y) = O(x*y)
Consider multiple, un-nested, loops: O(x) + O(x) = O(2x)
Consider a linear loop and a logarithmic, nested, loop: O(x) * O(log(y)) = O(x*log(y))

Ambiguity and Equivocation

There are at least three equivocations that are commonly encountered regarding the above:

Imprecision in computing exact Time Complexity. For example:
- A Function may be bounded by a range of Input Sizes so that the result is actually Constant (for that range of Input Sizes) but will nevertheless be treated as some other kind of Time Complexity (or vice-versa, that a Function may be more properly classified by some other label but will be considered say Constant). Consider if the Logarithmic Function example above were bounded to Input Sizes 4:6).
- For many Functions and Input Sizes, some XN = N^Y. Functions with that property may nevertheless be described by different Big O Time Complexities.
- It's standard convention to omit Big O Notation multiples: O(2n) is usually just written as O(n).
Quasilinear Time, Sublinear Time, and the like are usually ignored (and Big O Notation is essentially "rounded" to one of the four categories described above).
"Inner" and "Outer" Time Complexity are often equivocated:
- "Inner" - an Input is passed as a Parameter or Argument to a Function. Many Functions will alter this Value (in-place, for example). Some such Values are modified within a Function, each loop through a Function has a certain number of operations to be performed, a Function is a set of Functions, etc.
- "Outer" - consideration of a Function's Time Complexity by comparison of different Input Sizes to their total number of operations (per the above).

Resources and Links

Algorithms: Space Complexity

There’s a lot more ambiguity and disagreement about what constitutes what with respect to Space Complexity: https://www.studytonight.com/data-structures/space-complexity-of-algorithms observes that:

“Sometimes Auxiliary Space is confused with Space Complexity. But Auxiliary Space is the extra space or the temporary space used by the algorithm during it's execution.”

Furthermore, small Input Sizes are often just called O(1) (despite being strictly Linear): https://stackoverflow.com/questions/44430974/space-complexity-of-an-array.

Generally, carefully explaining how the memory footprint changes (or doesn’t) based on various input sizes is sufficient (regardless of the label we apply in some ambiguous outlier cases).
Arguably, in such cases one can use either moniker or label (linear or constant) depending on one’s justification. In other words, the labels above might overlap in certain limited scenarios rather than being sharply bounded/mutually exclusive.

Big O Notation

Is similar to Big O Notation for Time Complexity.

O(1)
- Space in memory is not dependent on Input Size.
- Space in memory remains fixed in Input Size.
O(n)
- Space in memory is proportional (linearly-related) to Input Size. For very small sizes this is often considered O(1).
O(log(n))
- Space in memory gradually decreases (or increases) Logarithmically relative to change in Input Size of an instruction set, method, or operation.
O(nˣ)
- Space in memory increases exponentially relative to Input Size.

Algorithms: Famous Algorithms

Minimum Spanning Tree

Kruskal’s Algorithm

Greedy algorithm
Time Complexity: O(V²) | V is the number of vertices
Given an undirected, connected, weighted Graph, construct a minimum spanning Tree of it.
- Traverse an entire Graph using the minimum number of moves and weights.
- Applies to undirected, connected, weighted Graphs.
Iterate through each node of the Graph sequentially starting with the lowest node (or first sorted node):
- Find the minimum weighted path to another node such that no cycle is formed.
- Each starting node is tracked as its own Tree.
- If a cycle is formed, that Tree is discarded.
- The remaining Tree is the minimum spanning Tree.
Review: https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/

Prim’s Algorithm

Greedy algorithm
Time Complexity: O(E*log(V)) | E is the number of edges and V is the number of vertices
Prim’s algorithm uses two sets of vertices to supplement its operation - visited and not yet visited nodes.
Constructs a minimum spanning Tree from a Graph.
- Traverse an entire Graph using the minimum number of moves and weights.
- Applies to undirected, connected, weighted Graphs.
Kruskal’s Algorithm is similar to Prim’s Algorithm which uses a single Tree (whereas Kruskal’s Algorithm uses a metaphorical forest).
Prim’s Algorithm traverses each node more than once whereas Kruskal’s Algorithm allows for each node to be traversed only once (within the last remaining, valid, Tree).
Review: https://www.coursera.org/learn/cs-fundamentals-3/home/week/4

Dijkstra's Algorithm

Find the shortest path between nodes in a graph.
- Find the minimum weighted path from the current or starting node to any node it’s directly connected to or any path not yet visited from a previously visited node.
  - Mark the node that’s the minimum weight from the current or starting node as visited.
  - Set the newly visited node as the new current node.
  - Set any previously unvisited nodes that are directly connected to any previously visited nodes as visited.
- Repeat until the endpoint has been reached.

Heap’s Algorithm

Used to find all permutations of a set.
Recursively moves index and swaps pairs in transfer array.
- https://leetcode.com/problems/permutations/

// Heap's Algorithm
// https://stackoverflow.com/questions/27539223/permutations-via-heaps-algorithm-with-a-mystery-comma#27540053
function permutation(originalArr) {
  let transferArr = originalArr, resultsAsStrings = []

  function swap(end, begin) {
    let original = transferArr[begin]
    transferArr[begin] = transferArr[end]
    transferArr[end] = original
  }

  function heaps_algorithm(n) {
    if (n === 1) resultsAsStrings.push(transferArr.join(""))

    for (let i = 0; i != n; ++i) {
      heaps_algorithm(n - 1)
      swap(n - 1, n % 2 === 0 ? i : 0)
    }
  }

  heaps_algorithm(originalArr.length)
  return resultsAsStrings
}

const a = [1, 2, 3, 4]
console.log(permutation(a))

const b = [0, 1, 2]
console.log(permutation(b))

const c = [2, 3, 4]
console.log(permutation(c))

Kadane's Algorithm

Given:

int[] input = new int[]{2, 3, -8, 7, -1, 2, 3};

int result = input[0];

for (int i = 0; i < input.length; i++) {
  int current = 0;
  
  for (int j = i; j < input.length; j++) {
    current += input[j];
    result = Math.max(result, current);
  }
}

//return result;

The Brute-Force implementation O(N²) can be optimzed to O(N):

int result = input[0]; 
int maxEnding = input[0]; 

for (int i = 1; i < input.length; i++) {
  int N = input[i];

  maxEnding = Math.max(maxEnding + N, N); 
  result = Math.max(maxEnding, result);
}

Observe:

There are three conditions:
- New highest sum
- Replacing the last highest sum with current index value
- Same highest sum
Highests subarray sums are transitive across indicies (except in the second condition where a positive number follows a negative one).
This necessitates two Variables, one (result) that's derived from the other (maxEnding). (I attempted to reduce this to a single multiple Max expression with a single Variable and was unable to optimize beyond the above.)

Resources and Links

Algorithms: Some Fun Ones

Some fun algorithms I've encountered from here and there.

Implement Lodash Curry

Challenge: implement Lodash .curry() from scratch. Official Code snippet.

function W(func) {
    // Key insight here is to use an aux buffer to store args into.
    let resolvedArgs = []
    return C(func, resolvedArgs)
}

function C(func, resolvedArgs, arity=func.length) {
    // Return an anon function with ...args here
    return function(...args) {
        resolvedArgs = [...resolvedArgs, ...args]
        // This is the trickiest part conceptually: recursively curry here
        if (args.length < arity) return C(func, resolvedArgs, arity-args.length)
        return func(...resolvedArgs)
  }
}

function T(a,b,c) {
    return [a,b,c]
}

const F = W(T)

console.log(T("A","B","C"))
console.log(F("A", "B", "C"))
console.log(F("A")("B", "C"))
console.log(F("A", "B")("C"))
console.log(F("A")("B")("C"))

["A", "B", "C"]
["A", "B", "C"]
["A", "B", "C"]
["A", "B", "C"]
["A", "B", "C"]

Flatten Without Flatten

Flatten an Array by a specified amount without using .flat():

var flatten = function (arr, flatten_by) {
    console.log(`Input: ${JSON.stringify(arr)} flatten_by: ${flatten_by}`)

    if (flatten_by === 0) return arr

    let str_arr = JSON.stringify(arr),
        result = "[",
        f_rem = flatten_by
    
    for (let i = 1; i < str_arr.length - 1; i++) {
        const C = str_arr[i]
        
        if (C === "[") {
            f_rem--
            // Balance checks here aren't symmetrical
            if (f_rem < 0) result += C
            
        } else if (C === "]") {
            f_rem++
            if (f_rem <= 0) result += C
        
        } else {
            result += C
        
        }
    }

    result += "]"
    console.log(`Output: ${result}`)
    return JSON.parse(result)
}
    
console.log(flatten([0, 1, 2, [3, 4]], 0))
console.log(flatten([0, 1, 2, [3, 4]], 1))
console.log(flatten([0, 1, 2, [[3, 4]]], 1))
console.log(flatten([0, 1, 2, [[3, 4]]], 2))
console.log(flatten([0, 1, [[[2, 3, 4]]]], 1))
console.log(flatten([[0, 1], 2, [[3, 4]]], 2))
console.log(flatten([[1], 1, [1], 1, [1], 1], 1))
console.log(flatten([[1], 1, [1], 1, [1], 1], 9))
console.log(flatten([[1], 1, [1], 1, [1], 1], 0))
console.log(flatten([[[[[[[[[[[[[[[[[9]]]]]]]]]]]]]]]]], 8))
console.log(flatten([[[[[[[[[[[[[[[[[9]]]]]]]]]]]]]]]]], 18))

"Input: [0,1,2,[3,4]] flatten_by: 0"
[0, 1, 2, [3, 4]]
"Input: [0,1,2,[3,4]] flatten_by: 1"
"Output: [0,1,2,3,4]"
[0, 1, 2, 3, 4]
"Input: [0,1,2,[[3,4]]] flatten_by: 1"
"Output: [0,1,2,[3,4]]"
[0, 1, 2, [3, 4]]
"Input: [0,1,2,[[3,4]]] flatten_by: 2"
"Output: [0,1,2,3,4]"
[0, 1, 2, 3, 4]
"Input: [0,1,[[[2,3,4]]]] flatten_by: 1"
"Output: [0,1,[[2,3,4]]]"
[0, 1, [[2, 3, 4]]]
"Input: [[0,1],2,[[3,4]]] flatten_by: 2"
"Output: [0,1,2,3,4]"
[0, 1, 2, 3, 4]
"Input: [[1],1,[1],1,[1],1] flatten_by: 1"
"Output: [1,1,1,1,1,1]"
[1, 1, 1, 1, 1, 1]
"Input: [[1],1,[1],1,[1],1] flatten_by: 9"
"Output: [1,1,1,1,1,1]"
[1, 1, 1, 1, 1, 1]
"Input: [[1],1,[1],1,[1],1] flatten_by: 0"
[[1], 1, [1], 1, [1], 1]
"Input: [[[[[[[[[[[[[[[[[9]]]]]]]]]]]]]]]]] flatten_by: 8"
"Output: [[[[[[[[[9]]]]]]]]]"
[[[[[[[[[9]]]]]]]]]
"Input: [[[[[[[[[[[[[[[[[9]]]]]]]]]]]]]]]]] flatten_by: 18"
"Output: [9]"
[9]

Algorithms: Search

A Needle refers to the Value, item, or Object one is searching for within a Haystack (the collection of items one is searching within).

Search Techniques

Breadth First Search (BFS) - graph search, sequential horizontal search (by row or width) of a node.

Typically uses Queue.
Pros: Will find a Needle and the shortest path in unweighted graphs.
Cons: If the Needle is far from the starting point (vertically), it may be better to use DFS.
Example: Traverse BST by level.

Depth First Search (DFS) - graph search, sequential vertical search (by column or full height) of a branch.

Typically uses Stack.
Pros: Will find a Needle (if no infinite cycles exist).
Cons: Not guaranteed to find the shortest path. If the Needle is close to the source (vertically), use BFS. Susceptible to infinite cycles if such exist within the Haystack.
Example: Traverse BST in order.

Sorted by Average Big O Time Complexity.

Hash Table - define a hashing method, each value is assigned a hash key that is unique to that value, then lookup a value using the hash key.

Best: O(1)
Average: O(1)
Worst: O(n)

const hash = (needle, haystack) => {
  console.log((`Find: ${needle} in [${haystack}]`, "hashstart")

  let table = []
  for (let i = 0; i < haystack.length; i++) {
    table[i] = -1
  }

  let keyHash = 0

  const simpleHash = val => val % table.length

  for (let i = 0; i < haystack.length; i++) {
    let flag = haystack[i] == needle
    const currentHash = simpleHash(haystack[i])

    if (table[currentHash] === -1) {
      table[currentHash] = haystack[i]
      if (flag) keyHash = currentHash

    } else {
      const NEXT = table.indexOf(-1)
      table[NEXT] = haystack[i]
      if (flag) keyHash = NEXT

    }
  }

  console.log((`Hash Table: [${table}] - Length: ${table.length}`)

  const BEGIN = new Date()
  const result = table[keyHash]
  const indexOf = haystack.indexOf(needle)
  const END = new Date()

  console.log((`Hash: ${keyHash} - Value: ${result} - IndexOf ${indexOf} in unsorted haystack`)
  console.log(`Time taken: ${END - BEGIN}`)
}

Linear - iterate through n until k is found.

Best: O(1)
Average: O(n)
Worst: O(n)

const linear = (needle, haystack) => {
  const BEGIN = new Date()
  let result = -1

  console.log(`Find: ${needle} in [${haystack}]`)

  for (let i = 0; i < haystack.length; i++) {
    if (needle === haystack[i]) {
      result = i;
      break;
    }
  }

  const indexOf = haystack.indexOf(needle);
  const END = new Date()
  console.log(`Index: ${result} - IndexOf: ${indexOf}`)
  console.log(`Time taken: ${END - BEGIN}`)
}

Binary- take a sorted Array and recursively divide in two comparing the Needle against values in each divided Array.

Best: O(1)
Average: O(log(n))
Worst: O(log(n))

const binary = (needle, haystack) => {
  haystack.sort((a, b) => a - b)
  console.log(`Sorted haystack: ${haystack}`)

  let l = 0, r = haystack.length - 1

  while (l <= r) {
    const M = Math.floor((l + r) / 2)

    if (haystack[M] === needle) {
      console.log(`${haystack[M]} at sorted index ${M}`)
      break
    } 
    
    if (haystack[M] < needle) l = M + 1
    
    // haystack[M] > needle
    else r = M - 1
  }
}

Consult a clean implementation here: https://www.instagram.com/reel/CYjmjbFF_8g/?utm_source=ig_web_copy_link

Resources and Links

https://www.instagram.com/reel/CYjmjbFF_8g/?utm_source=ig_web_copy_link

Algorithms: Sort

Sorted by Average Big O Time Complexity.

Non-Comparison Sorts

Insertion Sort - use a second array to rebuild the first array in sorted order, loop through inserting the next lowest value into the second array.

Best: O(n)
Average: O(n²)
Worst: O(n²)

https://github.com/Thoughtscript/sort_algos_2025/blob/main/noncomparison/insertion.js

Counting Sort - sort by statistical frequency using a buffer. (Frequency Sort)

Best: O(n + k)
Average: O(n + k)
Worst: O(n + k)

https://github.com/Thoughtscript/sort_algos_2025/blob/main/noncomparison/frequency.js

Bucket Sort- sort an array using buckets (that divide across the range of the input array), can be a Counting Sort and/or Insertion Sort depending on setup.

Best: O(n + k)
Average: O(n²)
Worst: O(n²)

https://github.com/Thoughtscript/sort_algos_2025/blob/main/noncomparison/bucket.js

Comparison Sorts

Heap Sort - properly sorts an array into a Binary Heap.

Best: O(n * log(n))
Average: O(n * log(n))
Worst: O(n * log(n))

https://github.com/Thoughtscript/cplusplus-coursera/blob/master/course/12%20-%20Heap/main.cpp

Merge Sort - divide an array into halves until two elements exist in each array then recombine comparing elements along the way.

Best: O(n * log(n))
Average: O(n * log(n))
Worst: O(n * log(n))

https://github.com/Thoughtscript/sort_algos_2025/blob/main/comparison/merge.js

Review: https://medium.com/analytics-vidhya/implement-merge-sort-algorithm-in-javascript-7402b7271887

Quick Sort - (recursively) specify a pivot point and swap values that are above and below the pivot point.

Best: O(n * log(n))
Average: O(n * log(n))
Worst: O(n²)

Helpful: https://www.geeksforgeeks.org/quick-sort-algorithm/

https://github.com/Thoughtscript/sort_algos_2025/blob/main/comparison/quick.js

Bubble Sort - loop through replacing sequential pairs (Swap) as necessary.

Best: O(n)
Average: O(n²)
Worst: O(n²)

https://github.com/Thoughtscript/sort_algos_2025/blob/main/comparison/bubble.js

Selection Sort - loop through swapping the lowest number with the current index.

Best: O(n²)
Average: O(n²)
Worst: O(n²)

https://github.com/Thoughtscript/sort_algos_2025/blob/main/comparison/selection.js

Language Implementations

Java uses a modified Merge Sort (by default).
JavaScript uses a modified Quick Sort with Insertion Sort fallback (by default).

Resources and Links

Code samples:

Algorithms: Recursion

Where a function repeatedly calls itself until some condition is met.

Solved Examples

Algorithms: Loop Recursion

A kind of Recursion problem where Recursion is called within a For-loop.

Useful for iterating through all permissible contiguous String subsequence "chunks".

Resources and Links

https://www.youtube.com/watch?v=DI6pH9Cx654 <- great example

Algorithms: Dynamic Programming

Breaking a problem down into multiple sub-problems where each step is stored (typically on the fly not Ahead-of-Time).

Often used with Memoization to reduce recursion footprint.

Solved Examples

https://leetcode.com/problems/count-sorted-vowel-strings/ <- Using variables that are saved off each cycle
https://leetcode.com/problems/product-of-array-except-self/ <- Bottom 50% time-complexity. Top .07% space-complexity.
https://leetcode.com/problems/max-increase-to-keep-city-skyline/
https://leetcode.com/problems/arithmetic-subarrays/
https://leetcode.com/problems/pascals-triangle/

Algorithms: Memoization

Saving the state of an instruction set into an Array, Map, Stack, Dequeue, or Queue.

Often eliminates the need to recursively compute some value.

Solved Examples

https://leetcode.com/problems/triangle/
https://leetcode.com/problems/climbing-stairs/ <- Used a precomputed O(1) data set I generated.
https://leetcode.com/problems/count-and-say/ <- Used a precomputed O(1) data set I generated.
https://leetcode.com/problems/longest-nice-substring/

Algorithms: Sets

Power Set

Dynamic Solution:

/**
 * Review: https://stackoverflow.com/questions/24365954/how-to-generate-a-power-set-of-a-given-set
 *
 * Strategy is clean and elegant so I made a few tweaks and implemented it in JS from the above.
 * 
 * Add elements one at a time to a result array, also iterate over the result array adding elements to the existing ones.
 *
 * This accomplished what was done here: https://medium.com/leetcode-patterns/leetcode-pattern-3-backtracking-5d9e5a03dc26 
 * and here: https://jimmy-shen.medium.com/78-subsets-fa4f0b047664 without backtracking (those are excellent articles 
 * and implementations given the requirements!).
 */

const powerSet = arrSet => {
  let arrSets = []
  for (let i = 0; i < arrSet.length; i++) {
    let item = arrSet[i], origSets = [...arrSets]
    
    for (let j = 0; j < origSets.length; j++) {
      let nSet = origSets[j].concat(item)
      arrSets.push(nSet)
    }
    arrSets.push([item])
  }
  arrSets.push([])
  return arrSets.sort()
}

window.onload = () => {
  console.log(powerSet([4, 2, 3]))
  console.log(powerSet([5, 1, 4, 2, 3]))
}

[
  [],          [ 2 ],
  [ 2, 3 ],    [ 3 ],
  [ 4 ],       [ 4, 2 ],
  [ 4, 2, 3 ], [ 4, 3 ]
]

[
  [],             [ 1 ],
  [ 1, 2 ],       [ 1, 2, 3 ],
  [ 1, 3 ],       [ 1, 4 ],
  [ 1, 4, 2 ],    [ 1, 4, 2, 3 ],
  [ 1, 4, 3 ],    [ 2 ],
  [ 2, 3 ],       [ 3 ],
  [ 4 ],          [ 4, 2 ],
  [ 4, 2, 3 ],    [ 4, 3 ],
  [ 5 ],          [ 5, 1 ],
  [ 5, 1, 2 ],    [ 5, 1, 2, 3 ],
  [ 5, 1, 3 ],    [ 5, 1, 4 ],
  [ 5, 1, 4, 2 ], [ 5, 1, 4, 2, 3 ],
  [ 5, 1, 4, 3 ], [ 5, 2 ],
  [ 5, 2, 3 ],    [ 5, 3 ],
  [ 5, 4 ],       [ 5, 4, 2 ],
  [ 5, 4, 2, 3 ], [ 5, 4, 3 ]
]

Greedy Solution:

/**
 * One can approach this from a few different angles:
 * 1. Brute force.
 * 2. Binary counter.
 * 3. Use native abstractions.
 * ---
 * I'd prefer to use what I understand to be a novel approach by generating 
 * constraints AOT (ahead-of_time) so that power-set 
 * generation is linear for every subsequent run.
 * ---
 * We can then use these values to populate others by index (e.g. - 1 means in the subset, 0 not).
 * The upside is that this is superfast (most powerset implementations 
 * involve deep recursion and 2-3 nested loops).
 * ----
 * The downside of this approach is that only works if you know the desired 
 * set size beforehand. It's Greedy.
 */

const generateConstraints = () => {
  let result = [], current = []

  // Flattened nested loop...
  for (let i = 0, j = 0, k = 0, l = 0; i < 2 && j < 2 && k < 2 && l < 2; i) {
    current.push(i)
    current.push(j)
    current.push(k)
    current.push(l)
    result.push(current)
    current = []

    l++;
    if (l == 2) {
      k++
      l = 0
    }
    if (k == 2) {
      j++
      k = 0
    }
    if (j == 2) {
      i++
      j = 0
    }
  }

  return result
}

window.onload = () => {
  const aot = generateConstraints()
  console.log(aot)
}

[
  [],          [ 2 ],
  [ 2, 3 ],    [ 3 ],
  [ 4 ],       [ 4, 2 ],
  [ 4, 2, 3 ], [ 4, 3 ]
]

[
  [],             [ 1 ],
  [ 1, 2 ],       [ 1, 2, 3 ],
  [ 1, 3 ],       [ 1, 4 ],
  [ 1, 4, 2 ],    [ 1, 4, 2, 3 ],
  [ 1, 4, 3 ],    [ 2 ],
  [ 2, 3 ],       [ 3 ],
  [ 4 ],          [ 4, 2 ],
  [ 4, 2, 3 ],    [ 4, 3 ],
  [ 5 ],          [ 5, 1 ],
  [ 5, 1, 2 ],    [ 5, 1, 2, 3 ],
  [ 5, 1, 3 ],    [ 5, 1, 4 ],
  [ 5, 1, 4, 2 ], [ 5, 1, 4, 2, 3 ],
  [ 5, 1, 4, 3 ], [ 5, 2 ],
  [ 5, 2, 3 ],    [ 5, 3 ],
  [ 5, 4 ],       [ 5, 4, 2 ],
  [ 5, 4, 2, 3 ], [ 5, 4, 3 ]
]

Cartesian Multiplication

Original Generalized Dynamic Solution using the above Dynamic Power Set Solution as an inspiration:

const solve = (args) => {
    let last = []
    const L = args.length - 1
    
    for (let i = 0; i < args[L].length; i++) {
        last.push([args[L][i]])
    }

    for (let i = L - 1; i >= 0; i--) {
        let curr = args[i], temp = []
        
        for (let j = 0; j < curr.length; j++) {
            for (let k = 0; k < last.length; k++) {
                const v = [...last[k]]
                if (v.indexOf(curr[j]) === -1) v.push(curr[j])
                temp.push(v)
            }
        }
        
        last = temp
    }
  
    console.log(last)
} 

window.onload = () => {
  const argsA = [[1,2],[3,4],[5,6]]
  solve(argsA)

  const argsB = [[1,2,3],[3,4],[5,6,15]]
  solve(argsB)

  const argsC = [[1],[1],[1]]
  solve(argsC)
}

Note: the above implementation isn't order preserving (Sets don't preserve order anyway) and assumes no empty Array is passed (the Empty Set is assumed to be present in every Set so we'll just omit all empty Arrays/Empty Set or we would have to add it everywhere).

[
  [5, 3, 1], 
  [6, 3, 1], 
  [5, 4, 1], 
  [6, 4, 1], 
  [5, 3, 2], 
  [6, 3, 2], 
  [5, 4, 2], 
  [6, 4, 2]
]

[
  [5, 3, 1], 
  [6, 3, 1],
  [15, 3, 1], 
  [5, 4, 1], 
  [6, 4, 1], 
  [15, 4, 1], 
  [5, 3, 2], 
  [6, 3, 2], 
  [15, 3, 2], 
  [5, 4, 2], 
  [6, 4, 2], 
  [15, 4, 2],
  [5, 3], 
  [6, 3],
  [15, 3], 
  [5, 4, 3], 
  [6, 4, 3], 
  [15, 4, 3]
]

[
  [1]
]

Algorithms: Hash Maps and Counts

Typically used when a solution requires a unique answer or a deduplicated Set.

Also often used to track the frequency of some value (number of occurrences).

Technique: Hash Map

let M = {}; 

// ...

if (M[x] != undefined) M[x]++; 
else M[x] = 1;

Solved Examples

Algorithms: Graph Relationship

Where a series of relationships are expressed using Arrays, Sets, or Maps.

Often a kind of Hash Counting Algorithm that requires Reverse Maps, Dual Mapping, Symmetric Maps and the like. Strong possibility that a solution can be achieved using a Maps of Maps.

Reverse Map

const A = {
    "AA": "BB",
    "CC":"DD"
}

const B = {
    "BB": "AA",
    "DD":"CC"
}

N-Tuple

Demonstrating a specific kind of this problem and how to index the relationships in multiple ways in O(N) time:

const Example = [
    [1, 2, 3], 
    [0, 3, 1], 
    [0, 4, 3], 
    [0, 5, 3], 
]

/*
 Where for each X in Example:
    1. X[1] is related to X[2] through relationship X[0].
    2. Where the relationship of X[1] to X[2] is symmetric (or not depending).
*/

const A = {
    "1": {
        "3": 0
    },
    "2": {
        "3": 1
    },
    "3": {
        "2": 1,
        "1": 0,
        "4": 0,
        "5": 0
    },
    "4": {
        "3": 0
    },
    "5": {
        "3": 0
    }
}
// Map of X[1] to X[2] and X[2] to X[1]

const B = {
    "1": {
        "3": {
            "2": true
        }
        "2": {
            "3": true
        }
    },
    "0": {
        "1": {
            "3": true
        },
        "3": {
            "1": true,
            "4": true,
            "5": true
        },
        "4": {
            "3": true
        },
        "5": {
            "3": true
        }
    }
}

// Map of X[0] to the relationship of X[2] to X[1] (and vice-versa)

Algorithms: Phone Dialer

Questions that use a 0-9 phone pad or phone numbers.

Solved Examples

Algorithms: Text Representation

Technique: Unicode Char Codes

// JavaScript
const c = str.charCodeAt(i);

// Unicode numbers codes 48-57 inclusive
if (c >= 48 && c <= 57) console.log("I'm a number character")
// Unicode uppercased letters codes 65-90 inclusive 
if (c >= 65 && c <= 90) console.log("I'm an uppercased character")
// Unicode lowercased letters codes 97-122 inclusive 
if (c >= 97 && c <= 122) console.log("I'm an lowercased character")

// JavaScript
const c = str.charCodeAt(i);

if ((c >= 65 && c <= 90) || (c >= 97 && c <= 122)) {
    const isUpperVowel = [65, 69, 73, 79, 85].indexOf(c) === -1 
    const isLowerVowel = [97, 101, 105, 111, 117].indexOf(c) === -1
    if (isUpperVowel && isLowerVowel) console.log("I'm a consonant")
    else console.log("I'm a vowel")
} else console.log("I'm not a letter")

Review: https://tutorial.eyehunts.com/js/get-the-unicode-value-of-character-javascript-example-code/

Technique: Character Maps

Alphabet maps:

// JavaScript
const a = {"a":0,"e":0,"i":0,"o":0,"u":0,"b":0,"c":0,"d":0,"f":0,"g":0,"h":0,"j":0,"k":0,"l":0,"m":0,"n":0,"p":0,"q":0,"r":0,"s":0,"t":0,"v":0,"w":0,"x":0,"y":0,"z":0}
const A = {"A":0,"E":0,"I":0,"O":0,"U":0,"B":0,"C":0,"D":0,"F":0,"G":0,"H":0,"J":0,"K":0,"L":0,"M":0,"N":0,"P":0,"Q":0,"R":0,"S":0,"T":0,"V":0,"W":0,"X":0,"Y":0,"Z":0}

// As array mapped by index
const arr_a = Object.keys(a)
const arr_A = Object.keys(A)

Consonant maps:

// JavaScript
const c = {"b":0,"c":0,"d":0,"f":0,"g":0,"h":0,"j":0,"k":0,"l":0,"m":0,"n":0,"p":0,"q":0,"r":0,"s":0,"t":0,"v":0,"w":0,"x":0,"y":0,"z":0}
const C = {"B":0,"C":0,"D":0,"F":0,"G":0,"H":0,"J":0,"K":0,"L":0,"M":0,"N":0,"P":0,"Q":0,"R":0,"S":0,"T":0,"V":0,"W":0,"X":0,"Y":0,"Z":0}

// As array mapped by index
const arr_c = Object.keys(c)
const arr_C = Object.keys(C)

Vowel maps:

// JavaScript
const v = {"a":0,"e":0,"i":0,"o":0,"u":0}
const V = {"A":0,"E":0,"I":0,"O":0,"U":0}

// As array mapped by index
const arr_v = Object.keys(v)
const arr_V = Object.keys(V)

Number maps:

// JavaScript
const N = {"0":0,"1":0,"2":0,"3":0,"4":0,"5":0,"6":0,"7":0,"8":0,"9":0}

// As array mapped by index
const arr_N = Object.keys(N)

Technique: Check Character is Number

// Java
Character.isDigit(inputStr.charAt(i)); // true/false

Algorithms: Letter Chars and Word Dictionaries

Specific to the dictionary, String, and Character checking with a fixed, finite, alphabet.

Can often be simplified to iterating through the letters of the English alphabet (0-25) rather than iterating over a string or multiple nested loops.
Otherwise, Hashing is often a good approach since the number of map keys will often be somewhere between 0-52 (inclusive).

Solved Examples

https://leetcode.com/problems/expressive-words/
https://leetcode.com/problems/string-without-aaa-or-bbb/ <- Bottom 50% time-complexity.
https://leetcode.com/problems/maximum-number-of-words-you-can-type/
https://leetcode.com/problems/check-if-all-characters-have-equal-number-of-occurrences/ <- Bottom 50% time-complexity.
https://leetcode.com/problems/check-if-word-equals-summation-of-two-words/
https://leetcode.com/problems/long-pressed-name/
https://leetcode.com/problems/shortest-word-distance/
https://leetcode.com/problems/keyboard-row/
https://leetcode.com/problems/verifying-an-alien-dictionary/ <- Bottom 50% time-complexity.
https://leetcode.com/problems/single-row-keyboard/
https://leetcode.com/problems/remove-vowels-from-a-string/ <- Bottom 50% time-complexity.

Algorithms: Word Patterns, Anagrams, and Palindromes

Word pattern, anagram, and palindrome scenarios.

Solved Examples

https://leetcode.com/problems/word-pattern/
https://leetcode.com/problems/palindrome-number/
https://leetcode.com/problems/valid-palindrome/ <- Below 50% time-complexity. Top 2.62% space-complexity.
https://leetcode.com/problems/palindrome-linked-list/
https://leetcode.com/problems/valid-palindrome-ii/
https://leetcode.com/problems/palindromic-substrings/ <- Below 50% time-complexity. Brute-force.
https://leetcode.com/problems/partition-labels/ <- Below 50% time-complexity.
https://leetcode.com/problems/find-anagram-mappings/
https://leetcode.com/problems/group-anagrams/ <- Below 50% time-complexity. Top .26% space-complexity.
https://leetcode.com/problems/minimum-number-of-steps-to-make-two-strings-anagram/

Algorithms: Parentheses

Calculate the validity of various Strings or substrings containing parentheticals.

Similar to facing but typically with a narrower focus (balance).

Somewhat similar to left, right two-pointer problems

Solved Examples

Algorithms: Two Pointer

Typically used when working with Arrays or Strings.

Use two pointers left and right.

Check or compare the values of each cycle.

Technique: Left and Right Pointers

while (left < right) { 
    //... 
    left++; 
    right--;
}

Solved Examples

Algorithms: Sliding Window

Often used to find unique subarrays, longest substrings, longest Strings with some property, etc.

This method is often used to reduce the time complexity of a solution from Quadratic to Linear time (when it can be applied).

Generally:

Initialize two pointers (left and right) at the beginning.
Expand the window (by incrementing the right pointer) until some desired condition is met.
Then, contract the window by incrementing the left pointer

Solved Examples

Algorithms: Direction and Facing

Used to represent cardinal direction facing.
Use a common local variable to track the current index allowing the index to move from end to start or start to end.
- Involves mod or Modulus concepts.
- Once the index reaches a certain point, it wraps around like a ring or circle.
Use an Array (usually for three or more values) or pointers to represent possible moves
- e.g. [n, e, s, w] or [up, right, down, left]

Solved Examples

Algorithms: Number Representation

Non-number type number-representation scenarios.

Technique: Fast Number Reversal

Old way:

const rev = num => {
    const numStr = `${num}`
    let str = ''

    for (let i = numStr.length - 1; i >= 0; i--) {
        str += numStr[i]
    }

    return parseInt(str)
}

Much faster than int to String and back conversion:

// Java
int reverse(int num) {
    int rev = 0;
    
    while(num > 0){
        int d = num % 10;
        rev = rev * 10 + d;
        num = num / 10;
    }
    
    return rev;
}

// Java
const reverse = num => {
    let rev = 0

    while(Math.floor(num) > 0) {
        const d = num % 10
        result = Math.floor(result * 10 + d)
        num = num / 10
    }

    return rev
}

JavaScript doesn't automatically round Numbers < 1 to 0 like Java does. So, use Math.floor().

Solved Examples

https://projecteuler.net/problem=89
https://www.codewars.com/kata/51b66044bce5799a7f000003
https://www.codewars.com/kata/5324945e2ece5e1f32000370
https://www.codewars.com/kata/525f4206b73515bffb000b21
https://www.codewars.com/kata/5265326f5fda8eb1160004c8
https://www.codewars.com/kata/54d7660d2daf68c619000d95
https://leetcode.com/problems/thousand-separator/
https://leetcode.com/problems/roman-to-integer/ <- Below 50% time-complexity. Top .01% space-complexity.
https://leetcode.com/problems/integer-to-roman/
https://leetcode.com/problems/integer-to-english-words/
https://leetcode.com/problems/string-to-integer-atoi/
https://leetcode.com/problems/add-strings/
https://leetcode.com/problems/add-two-numbers/
https://leetcode.com/problems/add-two-numbers-ii/ <- Below 50% time-complexity. Top 2.73% space-complexity.
https://leetcode.com/problems/sum-of-two-integers/
https://leetcode.com/problems/excel-sheet-column-number/ <- Not original, bijective base 26.

Algorithms: Number Theory

Implementations of arithmetic or number-theoretic scenarios.

These may or may not have some trick to them (like Big Int addition).
Factorials.

Solved Examples

Algorithms: Prime Numbers

Algorithms involving Prime Numbers.

Solved Examples

Algorithms: Path Compression and Merging

Used to combine multiple subarrays until they are all non-overlapping.

Used to merge Sets until they are Disjoint Sets.

Solved Examples

https://leetcode.com/problems/sum-of-digits-of-string-after-convert/ <- top 98.6% answer, loosely a compression/merging problem since it involves repeatedly summing a number until it’s below 10 or k.
https://leetcode.com/problems/merge-intervals/
https://www.codewars.com/kata/5286d92ec6b5a9045c000087
https://leetcode.com/problems/partition-labels/
https://leetcode.com/problems/meeting-rooms/
https://leetcode.com/problems/meeting-rooms-ii/ <- Very slow.
https://www.codewars.com/kata/52b7ed099cdc285c300001cd
https://leetcode.com/problems/summary-ranges/

Algorithms: Directory or Name Traversal

Directory name, IP Address, versioning, or URL context path operations.

Solved Examples

Algorithms: Level Recursion

Recursion specific to iterating down a pyramidal data structure.

Where each following level has a number of elements greater than or equal to the prior one.
Or, just when there are levels, period.

Technique: Queue

Use a Queue (nxt), use two alternating containers: level and nxt.

    level = [node]
    nxt = []
    
    while len(level) > 0:
        temp = []
        count = 0
        l = len(level)
        
        while count < l:
            if (len(level) > 0):
                c = level.pop(0)
                if c is None:
                    continue
                temp.append(c.value)
                nxt.append(c.left)
                nxt.append(c.right)
            count += 1
        
        if len(temp) > 0:
            for x in range(0, len(temp)):
                result.append(temp[x])

        level = nxt

Solved Examples

Algorithms: Geometry

Implementations of geometry scenarios and problems.

Solved Examples

Algorithms: Islands

Problems representing connected sub-matrices.

Technique: Check and Recurse

const countIslands = mapStr => {
  const ARR = mapStr.split("\n"), cleanedArr = []
  
  for (let i = 0; i < ARR.length; i++) {
    cleanedArr.push(ARR[i].split(""))
  }
  
  let deepCopy = [...cleanedArr], cnt = 0, hasNext = findNext(deepCopy)
  
  while (hasNext !== false) {
    cnt++
    recurse(deepCopy, hasNext[0], hasNext[1])
    hasNext = findNext(deepCopy)
  }

  return cnt
}

const findNext = arr => {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr[i].length; j++) {
      const I = arr[i][j]
      if (I === '0') {
        return [i, j]
      }
    }
  }  
  return false
}

const recurse = (arr, i, j) => {
  if (i >= arr.length || j >= arr[i].length || i <= -1 || j <= -1) {}
  else {
    arr[i][j] = '.'
    if (arr[i-1] !== undefined && arr[i-1][j] === '0') recurse(arr, i-1, j)    
    if (arr[i+1] !== undefined && arr[i+1][j] === '0') recurse(arr, i+1, j)
    if (arr[i][j-1] !== undefined && arr[i][j-1] === '0') recurse(arr, i, j-1)    
    if (arr[i][j+1] !== undefined && arr[i][j+1] === '0') recurse(arr, i, j+1)
  }
}

Interesting Technique

// Helpful comments from Sakashi to get in under the absolute time limit
// https://www.geeksforgeeks.org/problems/word-search/1

//...
boolean[][] seen = new boolean[mat.length][mat[0].length];
seen[r][c] = true; // Key insight here - allows reusing same deepcopy repeatedly!!!

//... Code here

seen[r][c] = false; // doesn't require deep copying each traversal!

https://github.com/Thoughtscript/java_algos/blob/main/src/main/java/io/thoughtscript/algos/gfg/arrays/WordSearch.java

Solved Examples

Code samples:

https://github.com/Thoughtscript/java_algos/blob/main/src/main/java/io/thoughtscript/algos/gfg/arrays/WordSearch.java

Algorithms: Pathing

To find a path from some origin to some end point.

Solved Examples

Algorithms: Rotations, Spirals, Diagonals

Includes spirals or diagonally traversing an N x M Array or matrix, transposing matrices, rotations, etc.

Also often involves mod or Modulus concepts.

Used for ciphers or rotating an Array.

Solved Examples

Algorithms: Coins and Make Bricks

Optimization scenarios involving fixed units of some value that need to be combined in some optimal way.

Solved Examples

https://projecteuler.net/problem=31
https://www.codewars.com/kata/564d0490e96393fc5c000029
http://www.javaproblems.com/2013/11/java-logic-2-makebricks-codingbat.html
https://leetcode.com/problems/coin-change-ii/ <- Not original.
https://leetcode.com/problems/coin-change/ <- Not original. Slow.
https://leetcode.com/problems/how-many-apples-can-you-put-into-the-basket/
https://leetcode.com/problems/water-bottles/
https://leetcode.com/problems/maximum-units-on-a-truck/ <- Below 50% time-complexity.

Algorithms: N-Sum

Triplet, 4-Sum, 3-Sum, and 2-Sum type problems.

Solved using a mix of l,r pointer and hashmap techniques.

Solved Examples

https://leetcode.com/problems/two-sum/ <- Original solution was very slow but top 100% space-complexity.
https://leetcode.com/problems/two-sum-less-than-k/
https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

Algorithms: Mountains, Peaks, and Stock Markets

Find a highest point in a sequence and the next highest or lowest point depending.

Solved Examples

Algorithms: Controlled Subsequences

Track things like substrings of a certain length, row or text justification/formatting, or repeated sub-patterns.

Use multiple pointers to track some value that gets reset every n-many loops.

Also includes "reverse loop in loop" (loop "backfilling") problems.