O'Reilly logo

A Common-Sense Guide to Data Structures and Algorithms by Jay Wengrow

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required