[Solution] Find First Duplicate

by Sanjay Yadav

HTML

<ul id="theList">
    <li>6</li>
    <li>3</li>
    <li>1</li>
    <li>4</li>
    <li>7</li>
    <li>4</li>
    <li>2</li>
    <li>8</li>
    <li>9</li>
    <li>2</li>
</ul>

<h1 id="output">

</h1>

CSS

h1 {
  color: red;
}

JavaScript

/*
Write an algorithm that will find the first duplicate in a list on the page.
For example we would return 4, for the list above.
*/
 
var numbers = document.getElementById("theList").getElementsByTagName("li")
document.getElementById("output").innerHTML = numbers.length
 
/* solution #1 - loop inside loop. Runtime = less than O(n2) */
for (i=0; i < numbers.length; i++) {
                var duplicateFound = false
                for (j=i+1; j < numbers.length; j++) {
if (numbers[i].innerHTML == numbers[j].innerHTML) {
                duplicateFound = true
                document.getElementById("output").innerHTML = "Duplicate found: " + numbers[i].innerHTML
      break
    }
  }
  if (duplicateFound) {
                break
   }
}
 
/* solution #2 - use of hashmap and while loop. Runtime: still O(n2) for worst possible scenario since key lookup in hash could be O(n) */
var seen = {};
var i = 0;
var duplicateFound = false
while (!duplicateFound) {
                if (numbers[i].innerHTML in seen) {
                document.getElementById("output").innerHTML = "Duplicate found: " + numbers[i].innerHTML
                duplicateFound = true
  }
  else {
                seen[numbers[i].innerHTML] = 1
                i++;
  }
}