How to get the only different value inside an array in Javascript?

Question

I saw many questions showing how to get unique values in an array, but none solved my problem. I get an array like this:

[ 1, 1, 1, 2, 1, 1 ]

I want to determine the unique value within it, which, in this case, is: 2.

I have a code that solves the problem with small values, but, with very large values, it fails.

Follows the code:

function findUniq(arr) {
  var result;
  arr.forEach((value, index, self) => {
    var lengthAll = []; 
    self.map(x => {
      if(x === value) {
        lengthAll.push(x);
      }
    })
    if (lengthAll.length === 1) {
      result = lengthAll[0];
    }
  });
  return result;
}

How to improve performance with big values?

Answer 1

I think you’re complicating a lot by using the Array.prototype.map there. You don’t actually need to map the array to solve this problem. It looks like you’re using the Array.prototype.map as a substitute for Array.prototype.forEach, what is an inaccurate use.

In addition, the solution proposed in the question has quadratic time complexity, which means that for each element of the array, a full scan will be done. For example, for an array of 100 elements, 100² iterations will be performed.

To learn more about this type of measure, see Definition of the "Big O" notation.

---

As far as I understand, there is no way to solve this problem with less than O(n).

This means that for any array, you must necessarily scroll through each element to check for any guaranteed unique member.

Solving with a map and only a scan for each element of the original array, one has something like:

function findUniqueElement(arr) {
  const map = new Map();

  for (const el of arr) {
    // Para cada elemento do array original, criamos um
    // registro no mapa `map` para determinar sua frequência:
    map.set(el, (map.get(el) || 0) + 1);
  }

  // Para cada elemento (sem repetição) do mapa, verificaremos
  // e retornaremos o primeiro único encontrado:
  for (const [entry, count] of map.entries()) {
    if (count === 1) return entry;
  }

  return undefined;
}

console.log(findUniqueElement([1, 1, 2, 2, 3, 3, 4])); //=> 4
console.log(findUniqueElement([1, 1, 2, 2, 3, 4])); //=> 3 (somente o primeiro único é retornado)
console.log(findUniqueElement([1, 1, 2, 2, 3, 3])); //=> undefined

The above algorithm complexity approaches O(2n) (considered linear), which is much better than O(n²) (quadratic).

Remember that this solution returns only the first single element found. If the occurrence of one more unique value is possible, an alternative is to return an array:

function findUniqueElements(arr) {
  const map = new Map();

  for (const el of arr) {
    map.set(el, (map.get(el) || 0) + 1);
  }

  const uniqueElements = [];
  for (const [entry, count] of map.entries()) {
    if (count === 1) uniqueElements.push(entry);
  }
  return uniqueElements;
}

console.log(findUniqueElements([1, 1, 2, 2, 3, 4])); //=> [3, 4]
console.log(findUniqueElements([1, 1, 2, 2, 3, 3])); //=> []

Answer 2

This function returns the first unique value in the array, and returns null if none is unique.

function findUniq(arr) {
  let uniq = {};

  //Para cada elemento do array é criado um index no objeto 'uniq' e incrementado a quantidade de vezes que esse elemento aparece.
  arr.forEach(a => uniq[a] = uniq[a] ? uniq[a] + 1 : 1);
  
  //Com o objeto de contagem pronto, é possivel iterá-lo até encontrar o primeiro elemento que possui apenas uma recorrência
  for (i in uniq)
    if (uniq[i] === 1)
      return i

  //caso nenhum elemento possua apenas uma recorrência, um valor nulo é retornado
  return null;
}

console.log(findUniq([1, 1, 1, 2, 1, 1]))