Count Distinct Elements in an Array

Problem Statement

Given an array of integers, find the number of distinct elements in the array.

Examples:

Example 1:

Input: arr[] = {10, 20, 20, 10, 30, 10}
Output: 3
Explanation: The distinct elements are 10, 20, and 30.

Example 2:

Input: arr[] = {10, 10, 10}
Output: 1
Explanation: The only distinct element is 10.

Method 1: Simple Approach (Nested Loops)

The simple approach is to use two nested loops. For every element in the array, we check if it has appeared before. If it has not appeared before, we increment the count of distinct elements.

Implementation

function countDistinct(arr) {
    let res = 1;
    
    // Pick all elements one by one
    for (let i = 1; i < arr.length; i++) {
        let j = 0;
        
        // Check if the picked element is already printed
        for (j = 0; j < i; j++) {
            if (arr[i] === arr[j]) {
                break;
            }
        }
        
        // If not printed earlier, then increment result
        if (i === j) {
            res++;
        }
    }
    return res;
}
 
// Example usage
let arr1 = [10, 20, 20, 10, 30, 10];
console.log(countDistinct(arr1)); // Output: 3

• Time Complexity: O(N²) - Due to the two nested loops.
• Auxiliary Space: O(1) - No extra space is required.

Method 2: Using Sorting

A better approach is to sort the array first. Once the array is sorted, all duplicate elements will be adjacent to each other. We can then easily count the distinct elements by traversing the array and comparing adjacent elements.

Implementation

function countDistinctSort(arr) {
    // Sort the array
    arr.sort((a, b) => a - b);
    
    let res = 0;
    
    for (let i = 0; i < arr.length; i++) {
        // Move the index to the last occurrence of the current element
        while (i < arr.length - 1 && arr[i] === arr[i + 1]) {
            i++;
        }
        res++;
    }
    
    return res;
}
 
// Example usage
let arr2 = [10, 20, 20, 10, 30, 10];
console.log(countDistinctSort(arr2)); // Output: 3

• Time Complexity: O(N log N) - Dominant time is taken by the sorting algorithm.
• Auxiliary Space: O(1) or O(log N) - Depending on the internal sorting algorithm used by JavaScript.

Method 3: Using Hashing (Hash Object)

The optimal idea is to use an algorithm that takes O(N) average time using hashing. We can use a hash map (or a plain JavaScript object) to keep track of the elements we have already encountered.

(Note: In some poorly documented resources, you might see the O(N²) nested loop code mistakenly pasted under the "Hashing" section. The correct hashing approach uses an actual hash map/object as shown below).

Implementation

function countDistinctHash(arr) {
    let hash = {};
    let res = 0;
    
    for (let i = 0; i < arr.length; i++) {
        // If the element is not in the hash object, it's distinct
        if (!hash[arr[i]]) {
            hash[arr[i]] = true; // Mark as seen
            res++;
        }
    }
    
    return res;
}
 
// Example usage
let arr3 = [10, 20, 20, 10, 30, 10];
console.log(countDistinctHash(arr3)); // Output: 3

• Time Complexity: O(N) - We traverse the array exactly once, and object insertions/lookups take O(1) on average.
• Auxiliary Space: O(N) - We need extra space to store the hash object.

Method 4: Using JavaScript Set (Optimal / Industry Standard)

The most modern and elegant way to solve this problem in JavaScript is by using the built-in Set object. A Set automatically removes duplicate values. We simply insert all array elements into a Set and return its size.

Implementation

function countDistinctSet(arr) {
    // Create a Set from the array
    let s = new Set(arr);
    
    // The size of the set is the number of distinct elements
    return s.size;
}
 
// Example usage
let arr4 = [10, 20, 20, 10, 30, 10];
console.log(countDistinctSet(arr4)); // Output: 3

• Time Complexity: O(N) - Inserting N elements into a Set takes O(N) time.
• Auxiliary Space: O(N) - Space is required to store the unique elements inside the Set.