Java Program To Print All Distinct Elements of a given integer array

Program to find Unique Array Element

We will learn, how to find and print all distinct elements of a given integer array. 

Objective:

Given a set of integers in array, we have to print all unique values from the array. This array may contain duplicate values and the output of our program should be printing only distinct numbers.

Examples:

Example 1: array1[] = {1, 2, 3, 4, 5, 6, 7, 8}
Output 1: 1 2 3 4 5 6 7 8

Example 2: array2[] = {20, 10, 30, 20, 67, 100, 90, 20, 90}
Output 2: 10, 20, 30, 67, 90, 100

Example 3: array3[] = {23, 46, 54, 33, 14, 19, 23, 33, 99, 14}
Output 3: 23, 46, 54, 33, 14, 19, 99

This is a common telephonic interview question to understand the thinking of the candidate. You should ask some questions to the interviewer whether the you understand the question correctly. This reveals understanding the problem and how you are trying to solve the problem.

Questions to interviewer

We should ask primarily

1) Does array contains negative numbers?
2) Is array sorted?
3) Output elements or values order should be as same as in input array?

If you ask valid questions, interviewer will get good impression on you.

First, We will see the easier solutions then slowly learn how to write optimized code for the problem.

Solution 1: Burte-Force procedure:

This is very simple solution using two for loops. A for loop inside a another for loop is called as Nested for loop.


The outer loop picks an element one by one starting from the leftmost element and 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 the simple algorithm.

This program looks very simple but not.

package examples.java.w3schools.array.programs;

public class UniqueNumbersForLoop {

 /**
  * Prints all unique numbers in the array arr using for loops
  * 
  * @param arr
  */
 static void printUnique(int arr[]) {

  int length = arr.length;
  // For loop picks all elements one by one
  System.out.print("Printing unique number from array are: ");
  for (int i = 0; i < length; 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)
    System.out.print(arr[i] + " ");

  }
 }

 // Main Driver Program
 public static void main(String[] args) {
  int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 2, 4, 6, 8 };
  printUnique(arr);

 }

}

Output:

The above program produces the below output.

Printing unique number from array are: 1 2 3 4 5 6 7 8 

Time Complexity of for loop: O(n2). See for the method 2 below for optimizing it.

Solution 2: Use Sorting technique

We can further optimize the above solution using sorting technique. The idea is simple. First, We need to sort the given array that makes all same numbers appears in the consecutive. Once the occurrences become consecutive, we can traverse the sorted array and print distinct elements in O(n) time.

See the below implementation code. We can use any sorting techniques or can use Arrays.sort(arr) method.

Implementation using sorting technique:

import java.util.Arrays;

public class UniqueNumbersForLoop {

 /**
  * Prints all unique numbers for the array arr using sorting technique
  * 
  * @param arr
  */
 static void printUnique(int arr[]) {

  // Getting the length of the array.
  int length = arr.length;

  // First sort the array so that all occurrences become consecutive
  Arrays.sort(arr);
  System.out.print("Sorting technique: Printing unique number from array are: ");
  // Traversing the sorted array
  for (int i = 0; i < length; i++) {
   // Move the index ahead while there are duplicates
   while (i < length - 1 && arr[i] == arr[i + 1])
    i++;

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

 // Main Driver Program
 public static void main(String[] args) {
  int arr[] = { 20, 10, 30, 20, 67, 100, 90, 20, 90 };
  printUnique(arr);

 }

}

Output:

The above program produces the below output.

Sorting technique: Printing unique number from array are: 10 20 30 67 90 100 

In this case, Time Complexity of for loop: O(nlogn). Still we can optimize using the method 3.

Solution 3: Using Hashset

In this method, First we traverse the input array from left to right and check each element is present in the hashset, if not present then add the element to the hashset and print it. If the element is already present in the hashset then ignore that element.

Below is the implementation using Hashset.

package examples.java.w3schools.array.programs;

import java.util.HashSet;
import java.util.Set;

public class UniqueNumbersForLoop {

 /**
  * Prints all unique numbers for the array arr using HashSet
  * 
  * @param arr
  */
 static void printUnique(int arr[]) {
  // Creating a empty Hashset instances which is used to store the values of
  // array.
  Set values = new HashSet();

  // Getting array length.
  int length = arr.length;

  System.out.print("Priting unique values using Hashmap for the given array: ");
  // Iterating array using for loop.
  for (int i = 0; i < length; i++) {
   if (!values.contains(arr[i])) {
    values.add(arr[i]);
    System.out.print(arr[i] + " ");
   }

  }

 }

 // Main Driver Program
 public static void main(String[] args) {
  int arr[] = { 23, 46, 54, 33, 14, 19, 23, 33, 99, 14 };
  printUnique(arr);

 }
}

Output:

The above program produces the below output.

Priting unique values using Hashmap for the given array: 23 46 54 33 14 19 99 

In this case, Time Complexity of for loop: O(n). This is the best solution(Solution 3). Here, the output order is preserved as in input.