A Common-Sense Guide to Data Structures and Algorithms

A Quadratic Problem

Let’s say you’re writing a JavaScript application that requires you to check whether an array contains any duplicate values.

One of the first approaches that may come to mind is the use of nested for loops, as follows:

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

In this function, we iterate through each element of the array using var i. As we focus on each element in i, we then run a second for loop that checks through all of the elements in the array—using var j—and checks if the elements at positions i and j are the same. If they are, that ...