HackerRank Lonely Integer solution with JavaScript

Learn how to solve the lonely integer problem from the HackerRank challenges by using JavaScript.
April 27, 2023JavaScript
3 min read

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

  1. Define a unique array to process the elements in the input array.
  2. Sort the input array in ascending order so that duplicate values are beside each other.
  3. 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.
  4. 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 JavaScript sort method.
  • O(n) for iterating over the input array, where n 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.

New
Be React Ready

Learn modern React with TypeScript.

Learn modern React development with TypeScript from my books React Ready and React Router Ready.