A Common-Sense Guide to Data Structures and Algorithms

A Linear Solution

Below is another implementation of the hasDuplicateValue function that doesn’t rely upon nested loops. Let’s analyze it and see if it’s any more efficient than our first implementation.

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

This implementation uses a single loop, and keeps track of which numbers it has already encountered using an array called existingNumbers. It uses this array in an interesting way: every time the code encounters a new number, it stores the value 1 inside the index of the existingNumbers ...