Finding first duplicate in an array and returning the minimal index

Question

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.

try looking at: stackoverflow.com/questions/14944458/…

stevenlacerda
– stevenlacerda

2017-07-21 19:28:32 +00:00
Commented Jul 21, 2017 at 19:28 — stevenlacerda
– stevenlacerda, Commented Jul 21, 2017 at 19:28

Dij · Accepted Answer · 2017-07-21 19:46:07Z

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]));

edited Jul 21, 2017 at 19:46

answered Jul 21, 2017 at 19:24

Dij

9,8184 gold badges21 silver badges35 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

Mabeh Al-Zuq Yadeek Over a year ago

this one fails when the array is [2, 3, 3, 1, 5, 2]. Expected output 3, get output 1.

Dij Over a year ago

@MabehAl-ZuqYadeek I was returning index, its correct now.

Mabeh Al-Zuq Yadeek Over a year ago

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.

Dij Over a year ago

@MabehAl-ZuqYadeek I have updated my answer with explanations

Dij Over a year ago

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

|

Jassi · Accepted Answer · 2017-11-29 12:19:54Z

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;
}

answered Nov 29, 2017 at 12:19

Jassi

6697 silver badges14 bronze badges

Comments

Kaps · Accepted Answer · 2017-07-21 19:55:15Z

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]));

edited Jul 21, 2017 at 19:55

answered Jul 21, 2017 at 19:34

Kaps

1897 bronze badges

Comments

neilharia7 · Accepted Answer · 2017-07-21 20:06:58Z

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;
}

answered Jul 21, 2017 at 20:06

neilharia7

1492 silver badges9 bronze badges

Comments

Artem · Accepted Answer · 2018-10-21 11:16:08Z

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;
}

edited Oct 21, 2018 at 11:16

Artem

3,4243 gold badges21 silver badges43 bronze badges

answered Oct 21, 2018 at 9:57

Prakash Mandal

94 bronze badges

1 Comment

Artem Over a year ago

Could you make some explanation to the code you posted?

Collectives™ on Stack Overflow

Finding first duplicate in an array and returning the minimal index

5 Answers 5

7 Comments

Comments

Comments

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

7 Comments

Comments

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related