How to Find All Distinct Elements of a Given Integer Array

In this post, we will learn how to find and print all distinct elements in an array. The given array may contain duplicates and it is not sorted, the C# solution should find and print every distinct element only once.

Here are few examples:

Input: arr[] = {14, 11, 7, 45, 3, 11, 11, 45}
Output: 14, 11, 7, 45, 3

Input: arr[] = {1, 2, 3, 4, 5}
Output: 1, 2, 3, 4, 5

Input: arr[] = {4, 4, 4, 4, 4}
Output: 4

Solution #1: Find all distinct elements of an integer array

The first solution that may come to our mind is to use two nested loops. The outer loop picks an element one by one starting from the leftmost element. Then the inner loop checks if the element is present on left side of it. If present, then ignores the element, else prints the element. Following is the implementation of this solution:

using System.Collections;

class Program
{
	public static void Main()
	{
		int[] arr = { 3, 11, 5, 4, 7, 89, 4, 3, 11 };

		FindDistinct(arr);
	}

	/// <summary>
	/// C# program to print all distinct elements in a given array
	/// </summary>
	/// <param name="arr">It is the integer array</param>
	static void FindDistinct(int[] arr)
	{
		int n = arr.Length;
		// Pick all elements one by one
		for (int i = 0; i < n; i++)
		{
			// Check if the picked element is already printed
			int j;
			for (j = 0; j < i; j++)
				if (arr[i] == arr[j])
					break;

			// If not printed earlier, then print it
			if (i == j)
				Console.Write(arr[i] + " ");
		}
	}
}

Here is the output:

3 11 5 4 7 89

Solution #2: Sort the array before finding the distinct elements

Time Complexity of the first solution is O(n2). We can sort the array then try solving the problem in O(nLogn) time. The idea is simple, first sort the array so that all occurrences of every element become consecutive. Once the occurrences become consecutive, we can traverse the sorted array and print distinct elements in O(n) time. Following is the implementation of the second solution:

using System.Collections;

class Program
{
     public static void Main()
     {
	int[] arr = { 3, 11, 5, 4, 7, 89, 4, 3, 11 };

	FindDistinct(arr);
     }

     /// <summary>
     /// C# program to print all distinct elements in a given array
     /// </summary>
     /// <param name="arr">It is the integer array</param>
     static void FindDistinct(int[] arr)
     {
        //get the length of the array
	int n = arr.Length;

        // First sort the array so that all occurrences become consecutive
        Array.Sort(arr);

        // Traverse the sorted array
        for (int i = 0; i < n; i++)
        {

            // Move the index ahead while there are duplicates
            while (i < n - 1 && arr[i] == arr[i + 1])
                i++;

            // print last occurrence of the current element
            Console.Write(arr[i] + " ");
        }
    }
}

Here is the output:

3 4 5 7 11 89

Solution #3: Find distinct elements in an array using Hashing

We can also use Hashing to solve this in O(n) time on average. The idea is to traverse the given array from left to right and keep track of visited elements in a hash table. Following is the implementation of this solution:

using System.Collections;

class Program
{
    public static void Main()
    {
	int[] arr = { 3, 11, 5, 4, 7, 89, 4, 3, 11 };

	FindDistinct(arr);
    }

    /// <summary>
    /// C# program to print all distinct elements in a given array
    /// </summary>
    /// <param name="arr">It is the integer array</param>
    static void FindDistinct(int[] arr)
    {
        // Creates an empty hashset
        HashSet<int> set = new HashSet<int>();

        // Traverse the input array
        for (int i = 0; i < arr.Length; i++)
        {
            // If not present, then put it in hashtable and print it
            if (!set.Contains(arr[i]))
            {
                set.Add(arr[i]);
                Console.Write(arr[i] + " ");
            }
        }
    }
}

Here is the output of this solution:

3 11 5 4 7 89

Solution #4: Find distinct elements in an integer array using Linq

The simplest and probably the fast solution is to use Linq. Here is the code:

using System;

class Program
{
    public static void Main()
    {		
	int[] arr = { 3, 11, 5, 4, 7, 89, 4, 3, 11 };

	Console.WriteLine(string.Join(" ", arr.Distinct()));
    }
}

Here is the output of this solution:

3 11 5 4 7 89

Do you have better solution? Please share it with us in the comments!