CODEWITHSUNDEEP
javascriptalgorithm
Mabeh Al-Zuq Yadeek
Mabeh Al-Zuq Yadeek

Reputation: 84

Finding first duplicate in an array and returning the minimal index

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.

Upvotes: 3

Views: 5484

Answers (5)

Prakash Mandal
Prakash Mandal

Reputation: 9

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

Upvotes: 0

Jassi
Jassi

Reputation: 669

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

Upvotes: 2

neilharia7
neilharia7

Reputation: 149

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

Upvotes: 1

Kaps
Kaps

Reputation: 189

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

Upvotes: 1

Dij
Dij

Reputation: 9808

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

Upvotes: 10

Related Questions