Distinct at app.codility.com/programmers in JavaScript Explained: Compute number of distinct values in an array.
Task score : 100% - Correctness : 100% ; Performance : 100%
Detected time complexity : O(N*log(N)) or O(N)
Lesson 6 at app.codility.com/programmers
The solution and its explanation are given below.
Category of Article : Technology | Computers and Software | Algorithm
By: Chrysanthus Date Published: 2 Jul 2025
Problem
Write a functionfunction solution(A);
that, given an array A consisting of N integers, returns the number of distinct values in array A.
For example, given array A consisting of six elements such that:
A[0] = 2 A[1] = 1 A[2] = 1
A[3] = 2 A[4] = 3 A[5] = 1
the function should return 3, because there are 3 distinct values appearing in array A, namely 1, 2 and 3.
Write an efficient algorithm for the following assumptions:
• N is an integer within the range [0..100,000];
• each element of array A is an integer within the range [−1,000,000..1,000,000].
Note
It can be cumbersome to solve this problem the brute force way, so only the smart approach is given.The array, A is:
const A = [2, 1, 1, 2, 3, 1];
Smart Approach
This tutorial (lesson) is on sorting, so it should occur to the reader that sorting should be required in the solution. The list is sorted first in ascending order.The given list,
const A = [2, 1, 1, 2, 3, 1];
sorted, becomes:
1, 1, 1, 2, 2, 3
After the list has been sorted, elements appear in groups of the same value. The sorted list is then scanned to count each repeated and non-repeated element once.
If the JavaScript array predefined sorting method is used, then that sorting function should take a maximum of O(n.log2n) time. The scanning takes an extra n time. So, expected time complexity is O(n.log2n + n) .
In order to count the number of distinct values, in the sorted list (array), two consecutive numbers are compared, beginning from the element at index 0 (zero based indexing). This means that i in the for-loop is incremented (by 1) for each pair until index N-2. The last element is at index N-1 for zero based indexing. This element is compared with the previous element, and i does not reach the last element in the following code.
Since the sorted elements have to be compared in consecutive pairs, what happens if the list has just one element? In this case, 1 is returned because there is only one distinct element. A list of length 1 has only one distinct element by default. If the length of the list is zero, then the number of distinct elements is zero, and zero is returned, as the list has no element. The program is (read the code and comments):
<script type='text/javascript'>
"use strict";
function solution(A) {
let N = A.length;
if (N == 0)
return 0;
let counter = 1; //in case given list has only one element
A.sort((a, b) => a - b);
for (let i=0;i<N-1; ++i) { //will not iterate if list has only one element
if (A[i] != A[i+1])
++counter;
}
return counter;
}
const A = [2, 1, 1, 2, 3, 1];
let ret = solution(A);
document.write(ret + '<br>');
</script>
The output is 3. The statement to sort the vector isA.sort();
Note that after deciding that the list is not of zero length in the solution() function, the counter is given the value 1, for the case when the length of the list is one. The while-condition in the for-loop is such that, if the length of the array is 1, the for-loop will not execute. In this case, 1 already assigned to the counter, will be returned.
At app.codility.com/programmers the scoring and detected time complexity for this smart solution() function is:
Task score : 100% - Correctness : 100% ; Performance : 100%
Detected time complexity : O(N*log(N)) or O(N)
Thanks for reading.