Find duplicate integer in time O(n logn) and space O(n)

June 2, 2018

Here’s how you can find a duplicate integer in a list of integers (read array) in space O(n) and time O(nlogn). This will only return the first duplicate integer in the array.

Note: This only applies for a list of integers 1..n. This won’t work otherwise.

function findDuplicate(arr) {
  var floor = 1;
  var ceiling = arr.length - 1;

  while (floor < ceiling) {
    var midpoint = Math.floor(floor + (ceiling - floor) / 2);
    var lowerRangeFloor = floor;
    var lowerRangeCeiling = midpoint;
    var upperRangeFloor = midpoint + 1;
    var upperRangeCeiling = ceiling;

    var distinctPossibleIntegersInLowerRange =
      lowerRangeCeiling - lowerRangeFloor + 1;
    var itemsInLowerRange = 0;
    arr.forEach(function (item) {
      if (item >= lowerRangeFloor && item <= lowerRangeCeiling) {
        itemsInLowerRange += 1;
      }
    });
    if (itemsInLowerRange > distinctPossibleIntegersInLowerRange) {
      floor = lowerRangeFloor;
      ceiling = lowerRangeCeiling;
    } else {
      floor = upperRangeFloor;
      ceiling = upperRangeCeiling;
    }
  }
  return floor;
}

// Example use case
let arr = [1, 2, 3, 4, 5, 4, 6, 3, 4, 6];
console.log(findDuplicate(arr)); // 3