So the question reads:

Given an array a that contains only numbers in the range from 1 to a.length, find the first duplicate number for which the second occurrence has the minimal index. In other words, if there are more than 1 duplicated numbers, return the number for which the second occurrence has a smaller index than the second occurrence of the other number does. If there are no such elements, return -1. Write a solution with O(n) time plexity and O(1) additional space plexity.

I have a solution, but apparently it's not fast enough and stalls when there are over a thousand items in the array.

This is what I have:

function firstDuplicate(arr) {
  let dictionary = {};

  for(let i = 0, ii = arr.length; i < ii; i++) {
    for(let z = i+1, zz = arr.length; z < zz; z++) {
      if(arr[i] === arr[z]) {
        if(dictionary.hasOwnProperty(arr[i])) {
          if(dictionary[arr[i]] !== 0 && dictionary[arr[i]] > z) {
            dictionary[i] = z;
          }
        } else {
          dictionary[arr[i]] = z;
        }
      }
    }
  }

  let answer = [];

  for(key in dictionary) {
    // [array number, position];
    answer.push([key, dictionary[key]]);
  };

if(answer.length > 0) {
  return Number(answer.sort((a, b) => {
    return a[1]-b[1];
  })[0][0]);
}

return -1;
}

I think converting the object into an array and then sorting the array after the answers are plete slows down the whole function. Using built in JS methods like forEach, map and sort (like I did above), slows the code/function down even more. There is obviously a better and more accurate way to do this, so I'm asking for some JS masterminds to help me out on this.

So the question reads:

Given an array a that contains only numbers in the range from 1 to a.length, find the first duplicate number for which the second occurrence has the minimal index. In other words, if there are more than 1 duplicated numbers, return the number for which the second occurrence has a smaller index than the second occurrence of the other number does. If there are no such elements, return -1. Write a solution with O(n) time plexity and O(1) additional space plexity.

I have a solution, but apparently it's not fast enough and stalls when there are over a thousand items in the array.

This is what I have:

function firstDuplicate(arr) {
  let dictionary = {};

  for(let i = 0, ii = arr.length; i < ii; i++) {
    for(let z = i+1, zz = arr.length; z < zz; z++) {
      if(arr[i] === arr[z]) {
        if(dictionary.hasOwnProperty(arr[i])) {
          if(dictionary[arr[i]] !== 0 && dictionary[arr[i]] > z) {
            dictionary[i] = z;
          }
        } else {
          dictionary[arr[i]] = z;
        }
      }
    }
  }

  let answer = [];

  for(key in dictionary) {
    // [array number, position];
    answer.push([key, dictionary[key]]);
  };

if(answer.length > 0) {
  return Number(answer.sort((a, b) => {
    return a[1]-b[1];
  })[0][0]);
}

return -1;
}

I think converting the object into an array and then sorting the array after the answers are plete slows down the whole function. Using built in JS methods like forEach, map and sort (like I did above), slows the code/function down even more. There is obviously a better and more accurate way to do this, so I'm asking for some JS masterminds to help me out on this.

• javascript
• algorithm

• try looking at: stackoverflow./questions/14944458/… – stevenlacerda Commented Jul 21, 2017 at 19:28

5 Answers 5

you can keep adding numbers to a dictionary as keys with values as their index, and as soon as you find a repeating key in the dictionary return its value. This will be O(n) time plexity and O(n) space plexity.

function firstDuplicate(arr) {
  var dictionary = {};

  for(var i = 0; i < arr.length; i++) {
if(dictionary[arr[i]] !== undefined)
     return arr[i];
else
   dictionary[arr[i]] = i;
  }

  return -1;
}

console.log(firstDuplicate([2, 3, 3, 1, 5, 2]));

Since the numbers are between 1 to arr.length you can iterate on the array. For each arr[i] use arr[i] as index and make the element present and arr[arr[i]] negative, then the first arr[arr[i]] negative return arr[i]. This give O(1) space plexity and O(n) time plexity you can do this:

function firstDuplicate(arr) {

  for(var i = 0; i < arr.length; i++) {
if(arr[Math.abs(arr[i])] < 0)
     return Math.abs(arr[i]);
else
   arr[Math.abs(arr[i])] = 0 - arr[Math.abs(arr[i])];
  }

  return -1;
}

console.log(firstDuplicate([2, 3, 3, 1, 5, 2]));

Answer mentioned by @dij is great, but will fail for [2,2] or [2,3,3], a little change for input [2,2], i=0 we get a[ Math.abs[a[0] ] = a[2] = undefined so we remove 1 from a[ Math.abs[a[0] -1 ] this will work now

function firstDuplicate(arr) {

  for(var i = 0; i < arr.length; i++) {
    if(arr[Math.abs(arr[i])-1] < 0)
      return Math.abs(arr[i]);
    else
      arr[Math.abs(arr[i])-1] = 0 - arr[Math.abs(arr[i])-1];
   }

   return -1;
}

function firstDuplicate(arr) {
   for(var i = 0; i < arr.length; i++) {
        var num = Math.abs(arr[i]);
        if(arr[num] < 0)
            return num;
        arr[num] = - arr[num];
    }
    return -1;
} 
console.log(firstDuplicate([2,2,3,1,2]));

function firstDuplicate(arr) {
    var numMap = {};
    for (var i = 0; i < arr.length; i++) {
        if (numMap[arr[i]]) {
            return arr[i];
        }
        numMap[arr[i]] = true;
    }
    return -1;
}

Please try the code below:

function getCountOccurence(A) {

    let result = [];
    A.forEach(elem => {
        if (result.length > 0) {
            let isOccure = false;
            result.some((element) => {
                if (element.element == elem) {
                    element.count++;
                    isOccure = true;
                }
            });
            if (!isOccure) {
                result.push({element: elem, count: 1});
            }
        } else {
            result.push({element: elem, count: 1});
        }
    });
    return result;
}

function getFirstRepeatingElement(A) {

    let array = getCountOccurence(A);
    array.some((element)=> {
        if (element.count > 1) {
            result = element.element;
            return true;
        }
    });
    return result;
}