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, 1002 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(n2) (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])); //=> []
What if you have two unique values? For example, in:
[1, 1, 2, 3]
?– Luiz Felipe
In my problem, there’s always one different value.
– Eduardo Nogueira
"but, with very large values, it fails" - which is the fault?
– vinibrsl
I don’t know exactly. It’s a Codewars Kata. In random tests, which are with large values sometimes, it exceeds the limit of 12 seconds of processing and breaking
– Eduardo Nogueira
@Vinibrasil, the fault is the excessively long time, which occurs quadratic algorithms that perform on a large number of elements. If it has 1e5 elements, 1e10 iterations will be made, which is absurd and would take a lot longer than needed for this type of problem.
– Luiz Felipe
The evening I publish an answer, but for now the load tests are here: https:/jsbench.me/awkpdlrj0d
– Augusto Vasques