Codility Algorithmic skills: FirstUnique

Specifications

• Level: Intermediate

• Problem: Find the first unique number in a given sequence.

• Programming Language: JavaScript

• Codility Problem Link

Problem Statement

A non-empty array A consisting of N integers is given. The unique number is the number that occurs exactly once in array A.

• For example, the following array A:

  • A[0] = 4
  • A[1] = 10
  • A[2] = 5
  • A[3] = 4
  • A[4] = 2
  • A[5] = 10

contains two unique numbers (5 and 2).

You should find the first unique number in A. In other words, find the unique number with the lowest position in A.

For above example, 5 is in second position ( because A[2] = 5 ) and 2 is in fourth position ( because A[4] = 2 ). So, the first unique number is 5.

• Write a function:

  • function solution(A);

that, given a non-empty array A of N integers, returns the first unique number in A. The function should return −1 if there are no unique numbers in A.

• For example, given:

  • A[0] = 1
  • A[1] = 4
  • A[2] = 3
  • A[3] = 3
  • A[4] = 1
  • A[5] = 2

the function should return 4. There are two unique numbers (4 and 2 occur exactly once). The first one is 4 in position 1 and the second one is 2 in position 5. The function should return 4 bacause it is unique number with the lowest position.

• Given array A such that:

  • A[0] = 6
  • A[1] = 4
  • A[2] = 4
  • A[3] = 6

the function should return −1. There is no unique number in A ( 4 and 6 occur more than once ).

• Write an efficient algorithm for the following assumptions:

  • N is an integer within the range [1..100,000]; each element of array A is an integer within the range [0..1,000,000,000].

Function Signature

function solution(A);

Given a non-empty array A of N integers, return the first unique number in A. The function should return -1 if there are no unique numbers in A.

Example 1:

A = [1, 4, 3, 3, 1, 2]

The first unique number is 4 because it is the first number that occurs exactly once.

 Return: 4

Example 2:

A = [6, 4, 4, 6]

There are no unique numbers in A.

Return: -1

Constraints

• N is an integer within the range [1..100,000];

• Each element of array A is an integer within the range [0..1,000,000,000].

JavaScript Solution

function solution(A) {
    let nMap = new Map()

    // Count the occurrence of each number in the array A
    for(let num of A) {
        nMap.set(num, ( nMap.get(num) || 0 ) + 1)
    }

    // Find the first unique number
    for (let num of A) {
        if( nMap.get(num) === 1) {
            return num  // Return the first unique found
        }
    }

    // If no unique number is found, return -1
    return -1
} 

Approach

Count occurrences: We use a Map to store the count of each element in the array A. For each element num in the array, we update the count using nMap.set(num, (nMap.get(num) || 0) + 1).

Find first unique: After counting the occurrences, we iterate through the array A again and return the first element whose count is equal to 1.

Time Complexity

• Time Complexity: O(N), where N is the number of elements in the array A. We iterate over the array twice: once to count the occurrences and once to find the first unique number.

• Space Complexity: O(N) because we store the counts of each element in a Map.

Example Walkthrough

For the array:

A = [1, 4, 3, 3, 1, 2]

• The function first counts the occurrences:

  • 1 appears twice.
  • 4 appears once.
  • 3 appears twice.
  • 2 appears once.

The function then returns 4 as it is the first unique number with the lowest position.

If the array was:

A = [6, 4, 4, 6]

Since all numbers are repeated, the function would return -1, indicating there are no unique numbers.