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

A Linear Solution

Following is another implementation of the hasDuplicateValue function that doesn’t rely on nested loops. It’s a bit clever, so let’s first look at how it works and then we’ll see if it’s any more efficient than our first implementation.

function hasDuplicateValue(array) {
    let existingNumbers = [];
    for(let i = 0; i < array.length; i++) {
        if(existingNumbers[array[i]] === 1) {
            return true;
        } else {
            existingNumbers[array[i]] = 1;
        }
    }
    return false;
}

Here’s what this function does. It creates an array called existingNumbers, which starts out empty.

Then, we use a loop to check each number in the array. As it encounters each number, it places an arbitrary value (we’ve chosen to use a 1) in ...