/ javascript

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

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
Find duplicate integer in time O(n logn) and space O(n)
Share this

Subscribe to Elliot Sachs