3

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 complexity and O(1) additional space complexity.

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

yoozer8
  • 7,361
  • 7
  • 58
  • 93
Mabeh Al-Zuq Yadeek
  • 46
  • 4
  • 16
  • 28

5 Answers5

10

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 complexity and O(n) space complexity.

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 complexity and O(n) time complexity 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]));
Dij
  • 9,761
  • 4
  • 18
  • 35
  • this one fails when the array is `[2, 3, 3, 1, 5, 2]`. Expected output `3`, get output `1`. – Mabeh Al-Zuq Yadeek Jul 21 '17 at 19:27
  • @MabehAl-ZuqYadeek I was returning index, its correct now. – Dij Jul 21 '17 at 19:29
  • Other answers were good as well. Thanks for your help. Can you explain your thought process or good resources to think the way you have? I completely went off the deep and wrote unnecessary code. – Mabeh Al-Zuq Yadeek Jul 21 '17 at 19:36
  • @MabehAl-ZuqYadeek I have updated my answer with explanations – Dij Jul 21 '17 at 19:48
  • 1
    @MabehAl-ZuqYadeek you were almost the right track with using dictionary, with dictionary you can always find a key value pair and if you find a key in the dictionary means you have already seen that number before which means it is being repeated. – Dij Jul 21 '17 at 19:55
  • @Jassi "array a that contains only numbers in the range from 1 to a.length" as it says in the question, that means [2,2] is invalid input according to the question. – Dij Nov 30 '17 at 08:41
  • @Dij that is true. Actually this question was part of Code Fight and there it was numbers <=a.length. I posted the answer below which will work if a.length is max – Jassi Nov 30 '17 at 16:34
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]));
Kaps
  • 189
  • 7
1
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;
}
neilharia7
  • 149
  • 2
  • 9
1

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;
}
Jassi
  • 619
  • 7
  • 12
0

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;
}
Artem
  • 3,304
  • 3
  • 18
  • 41
Prakash Mandal
  • 9
  • 4