A Common-Sense Guide to Data Structures and Algorithms in JavaScript, Volume 1

Trade-Offs Between Time and Space

Here’s a function that accepts an array and returns whether it contains any duplicate values (you may recognize this function from Chapter 4, ​Speeding Up Your Code with Big O​:

function hasDuplicateValue(array) {
  for (let i = 0; i < array.length; i += 1) {
    for (let j = 0; j < array.length; j += 1) {
      if (i !== j && array[i] === array[j]) {
        return true;
      }
    }
  }

  return false;
}

This algorithm uses nested loops and has a time complexity of O(N²). We’ll call this implementation Version #1.

Here’s a second implementation, Version #2, which employs a hash table and just a single loop:

function hasDuplicateValue(array) {
  const existingValues = {};

  for (const value ...