A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition

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++) {
        for(let j = 0; j < array.length; j++) {
            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, that employs a hash table and just a single loop:

function hasDuplicateValue(array) {
    let existingValues = {};
    for(let i = 0; i < array.length; ...