HackerRank Lonely Integer solution with JavaScript
Let's learn how to solve the Lonely Integer challenge from the HackerRank website.
Given an array of integers, where all elements but one occur twice, we must find the lonely element that occurs only once.
Example
a = [1, 2, 3, 4, 3, 2, 1];
In this example, the lonely integer is 4
.
Pseudo code solution
- Define a
unique
array to process the elements in the input array. - Sort the input array in ascending order so that duplicate values are beside each other.
- Loop over the input array.
- If the
unique
array does not contain the current array element, add it. - If the
unique
array does contain the current array element, remove it.
- If the
- Return the first index of the
unique
array, which is the lonely integer.
Code solution
function lonelyinteger(a) {
let unique = [];
a.sort().forEach((item) => {
const hasItem = unique.includes(item);
if (!hasItem) {
unique.push(item);
} else {
unique.pop(item);
}
});
return unique[0];
}
If we want to avoid sorting the input array, we can use a JavaScript Set
instead.
function lonelyinteger(a) {
const set = new Set();
a.forEach((item) => {
if (set.has(item)) {
set.delete(item);
} else {
set.add(item);
}
});
return set.values().next().value; // or [...set][0]
}
Test cases
console.log(lonelyinteger([0, 0, 1, 2, 1]));
The lonely integer for this array should be 2
. The result is indeed what we expected.
console.log(lonelyinteger([1, 2, 3, 4, 3, 2, 1]));
The lonely integer for this array should be 4
. The result is indeed what we expected.
Time and space complexity
The Big O time complexity of the solution is comprised of the following.
O(n log n)
for the sorting with the JavaScriptsort
method.O(n)
for iterating over the input array, wheren
is the length of the input array.
When adding both together, we get a time complexity of O(2n log n)
, which is essentially just O(n log n)
, or logarithmic time complexity.
The Big O space complexity of the solution is constant, or O(m)
, where m
is the number of unique values from the input array. Even if we delete any duplicate value after detecting that it has already been stored, it still had to be stored. In the case of the [0, 0, 1, 2, 1]
input array, [0, 1, 2]
were stored in the unique
array, or the set
.