# Distinct elements in an array

Problem: Write a Java program to find distinct elements in an array.
For example, if input array is { 2, 4, 3, 2, 6, 9, 4, 6 } then, the distinct elements in the array are  3 and 9.

## Algorithm to find distinct elements in an array

```Say the input array is A with n elements.

1. Create frequency map for the elements A
Frequency map holds elements of array with their respective frequencies in the array.
Ex: If the input array is {2, 3, 2, 4, 6} then, frequency map would look like
{2->2, 3->1, 4->1, 6->1}

1. Let M be the frequency map.
2. Iterate over the elements of A
for i = 0 to n
If M contains A[i]
Add A[i] to M and increase value of A[i] by 1
Else
Add A[i] to M with value 1
End if
End for

2. Let distinctElements be a list which will hold distinct elements
Iterate over entries of M
while M has entries
entry = M.entry
If entry.value = 1
End if
End while

3. Return distinctElements```

Analysis:

Let us analyze above algorithm.
1. In step 1 we create a frequency map. We iterate over the elements of the array. So the run-time of this step id Ο(n).
2. In step 2, we iterate over map n times. So the run-time of this step id Ο(n).
So the total run-time is Ο(n) + Ο(n) = 2Ο(n), 2 is a constant so the run-time of this algorithm is Ο(n).
Space complexity of this algorithm is also Ο(n) since we use map to store frequencies of the elements in the array.

Java code:

We will implement above algorithm in Java.

```package com.javafries.array;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

public class DistinctElementsProblem {

private static List<Integer> findDistinctNumbers(int[] arr) {

Map<Integer, Integer> frequencyMap = createElementFrequencyMap(arr);

return findNumbersWithFrequencyOne(frequencyMap);
}

private static List<Integer> findNumbersWithFrequencyOne(
Map<Integer, Integer> frequencyMap) {
List<Integer> distinctNumbers = new ArrayList<Integer>();

Iterator<Entry<Integer, Integer>> iterator = frequencyMap.entrySet()
.iterator();
while (iterator.hasNext()) {
Map.Entry<Integer, Integer> entry = iterator.next();

if (entry.getValue() == 1) {
}
}
return distinctNumbers;
}

private static Map<Integer, Integer> createElementFrequencyMap(int[] arr) {

Map<Integer, Integer> frequencyMap = new HashMap<Integer, Integer>();

for (int key : arr) {
if (frequencyMap.containsKey(key)) {
frequencyMap.put(key, frequencyMap.get(key) + 1);
} else {
frequencyMap.put(key, 1);
}
}

return frequencyMap;
}

private static void print(List<Integer> numberList) {
for (int number : numberList) {
System.out.println(number);
}
}

public static void main(String[] args) {
int[] arr = { 2, 4, 3, 2, 6, 9, 4, 6 };
List<Integer> distinctNumbers = findDistinctNumbers(arr);
System.out.println("Distinct elements are : ");
print(distinctNumbers);
}
}
```

Output:

```Distinct elements are :
3
9```

I hope you understood the solution.