This is a problem in which we have an integer array which contains some elements and our job is to find out number of distinct elements in a given range. The given range will represent a sub array.

We will solve this problem using three methods:

• Brute force O(N^2) time and O(1) space
• Sorting approach O(N logN) time and O(1) space
• Hashing approach O(N) time and O(N) space

For example:

A[] = {8 ,1, 3, 1, 5, 7, 1}

Now for the range 0 to 7 the number of distinct elements are 5 (1 is counted only once and 8, 3, 5, 7 are distinct).

Now there can be multiple queries to find out the distinct elements which we are going to implement here.

Our program will accept some inputs from the user with queries on the array and we will produce the output for each query in a new line.
First line of the input will be the elements of the array separated by ',' (comma) and second line will contain a number that will indicate the number of queries (Q) and then Q lines will follow and will specify the range of the sub array for query.
Lets see some more examples on it.

Example 1:

Input:

1 2 4 1 2
3
0 2
0 4
2 4

Output:

3
3
3

Explanation:

our array is A = {1, 2, 4, 1, 2} and number of queries are 3 (Q = 3).

• First query is on the sub array A[0] to A[2] which contains the following elements (1, 2, 4) and clearly we can see the output will be 3 as all elements are distinct.
• Second query is on the sub array A[0] to A[4] that represents the original array (1, 2, 4, 1, 2) and in this case there are 3 distinct elements as 1 and 2 are repeating two times.
• Third query is on the sub array A[0] to A[2] which contains the following elements (1, 2, 4) and again this array has all distinct elements hence output is 3.

Example 2:

Input:

1 2 4 4 3 1
2
0 5
2 4

Output:

4
2

Solutions

There can be various solutions for this problem but in this article we will see three simple and easy to understand solutions along with their analysis.

First Method

In this method we are going to find out distinct elements by checking the elements before it i.e. when we are at a particular element of the array then we will compare this element with the previous elements to check if it is unique or not. If it is unique we will increment our count variable with stores the number of distinct elements.

Algorithm:

Method-1-countDistinctElements(A, i, j):
1. count = 0
2. for i to j:
3.     flag = flase
4.     for k = i+1 to 0:
5.         if a[i] == a[k]:
6.             flag = true
7.             break
8.         if flag = flase:
9.             count = count + 1
10. return count

Time complexity: O(n^2)

In this algorithm we are traversing the full array in the first loop which take 'n' (liner) time and for each iteration of loop we are traversing the array backwards which again takes linear time so the final complexity of this algorithm is 'n*n' O(n^2).

Implementation (Java)

// Part of OpenGenus
import java.util.Scanner;

public class Main {

    static int countDistinctElements(int[] a, int i, int j){
        int count=0;

        for(; i <= j; i++){
            boolean flag = false;
            for(int k = i-1; k >= 0; k--){
                if(a[i] == a[k]){
                    flag = true;
                    break;
                }
            }
            if(!flag)
                count += 1;
        }

        return count;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        String[] a =  s.split(" ");
        int[] arr = new int[a.length];
        for(int i = 0; i < arr.length;  i++)
            arr[i] = Integer.valueOf(a[i]);

        int t = scanner.nextInt();
        scanner.nextLine();
        while(t-- != 0){
            String range = scanner.nextLine();
            String[] r = range.split(" ");
            System.out.println(countDistinctElements(arr, Integer.valueOf(r[0]), Integer.valueOf(r[1])));
        }
    }
}

Inputs:

1 2 4 1 2
3
0 4
2 2
1 2

Outputs:

3
1
2

Second Method

In this method we will sort the elements of the sub array in the non decreasing order and then for each element we will check if it has appeared for the first time or not by comparing it with the previous element of the array.

Algorithm:

Method-3-getDistinctElements(A, x, y):
1. Create subArraay = A[x to y]
2. count = 0
3. subArray.sort()
4. if subArray.Length >= 1:
5. count = 1
6. for i=1 to subArray.Length:
7.     if subArray[i] != subArray[i-1]:
8.         count = count +1
9. return count

Time complexity: O(nlogn)

This algorithm creates a new sub array and then sorts it non decreasing order and assume that the sorting algorithm takes O(nlogn) time to sort the elements of the array, then we are traversing though the array only once so time complexity for this operation will be O(n) i.e. linear so finally the time complexity of this algorithm will be O(nlogn).

Implementation (Java):

// Part of OpenGenus
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    static int countDistinctElements(int[] a, int x, int y) {
        int[] subA = Arrays.copyOfRange(a, x, y+1);
        int count = 0;
        Arrays.sort(subA);
        if(subA.length >= 1)
            count=1;

        for(int i = 1; i < subA.length; i++){
            if(subA[i] != subA[i-1])
                count+=1;
        }

        return count;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        String[] a =  s.split(" ");
        int[] arr = new int[a.length];
        for(int i = 0; i < arr.length;  i++)
            arr[i] = Integer.valueOf(a[i]);

        int t = scanner.nextInt();
        scanner.nextLine();
        while(t-- != 0){
            String range = scanner.nextLine();
            String[] r = range.split(" ");
            System.out.println(countDistinctElements(arr, Integer.valueOf(r[0]), Integer.valueOf(r[1])));
        }
    }
}

Inputs:

1 2 4 4 3 1
2
0 5
2 4

Outputs:

4
2

This algorithm is better than the previous algorithm in terms of running time but let's see if we can even have a better algorithm than this.

Third Method

In this method we will traverse through the array and will form a set to find the number of distinct elements, now lets see how that's done.

Algorithm:

Method-3-getDistinctElements(A, i, j):
1. Create an empty Set S
2. for i to j
3.     S.add(A[i])
4. return S.length

Time complexity: O(n)

As the the operation of insertion in the set (HashSet which is implemented as Hashtable) will take constant time (and there are n such operations) and also the length of the set can be calculated in constant time so the final complexity is linear i.e. O(n).

Surely this algorithm is the fastest as compared to other algorithms which we have seen above.

Implementation (Java):

// Part of OpenGenus
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {

    private static int getDistinctElements(int[] arr, int i, int j){
        Set<Integer> set = new HashSet<>();

        for(; i<=j; i++)
            set.add(arr[i]);

        return set.size();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        String[] a =  s.split(" ");
        int[] arr = new int[a.length];
        for(int i = 0; i < arr.length;  i++)
            arr[i] = Integer.valueOf(a[i]);

        int t = scanner.nextInt();
        scanner.nextLine();
        while(t-- != 0){
            String range = scanner.nextLine();
            String[] r = range.split(" ");
            System.out.println(getDistinctElements(arr, Integer.valueOf(r[0]), Integer.valueOf(r[1])));
        }
    }
}

Inputs:

1 2 4 1 2
3
0 4
2 2
1 2

Outputs:

3
1
2

With this article at OpenGenus, you must have the complete idea of finding the number of distinct elements in a set efficiently. Enjoy.