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
         Add entry.key to distinctElements
      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) {
				distinctNumbers.add(entry.getKey());
			}
		}
		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.
Your questions and comments are most welcome.

One Response

  1. Magesh Kumar September 13, 2016

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.