educative.io

Solution using map, maybe o(n log(n)) but simple solution

Courses
,
#1

Well I know the best solution is using the hash approach, however I implement my solution using Map structure from Javascript, it is pretty simple. :smiley:

// Time complexity O (n log(n))
function findFirstUnique(arr) {
  const newMap = new Map();

  for (value of arr) {
    if (!newMap.has(value)) {
      newMap.set(value, 1);
    } else {
      newMap.delete(value);
    }
  }

  const iterator = newMap.keys();

  return iterator.next().value || null;
}
#2

Hi @Ulises,

Your solution gives an incorrect result of null on the following array: [9,2,3,6,2,6,9,0,3] whereas the expected result should be 0. This is because of the following line in your solution:

return iterator.next().value || null;

Since 0 is interpreted as null by the compiler, if 0 is the first unique value in the array, it gives the result of 0 || null as null.

This could be corrected by adding the following lines:

result = ((iterator.next().value + 1) || null) - 1

if(result == -1){
return null
}
return result;

Your final code would look like this:

function findFirstUnique(arr) {
const newMap = new Map();

for (value of arr) {
if (!newMap.has(value)) {
newMap.set(value, 1);
} else {
newMap.delete(value);
}
}

const iterator = newMap.keys();

result = ((iterator.next().value + 1) || null) - 1

if(result == -1){
return null
}

return result;
}

1 Like