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

```
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!

Why not using Linq:

ReplyDeletevar arr = new int[] {14, 11, 7, 45, 3, 11, 11, 45};

Console.WriteLine(string.Join(" ", arr.GroupBy(i => i).OrderBy(g => g.Key).Select(g => g.Key)));

Regards Bernd