Group Multiple Occurrence of Array Elements Ordered by First Occurrence in Java
You are provided with a non-sorted array with repeated elements. The problem statement is to group various occurrences of individual elements. The order of firstly occurred elements must be maintained while grouping the elements.
Example 1:
Input: Arr = { 2, 3, 3, 5, 5, 1}
Output: Arr = { 3, 3, 5, 5, 2, 1}
Explanation:
In the above-mentioned example, the first repeating element is 3, so the occurrences of 3 will be placed at starting indexes. After 3, 5 is the repeating element so the occurrences of 5 will be placed after 3. Later, the non-repeating elements 2 and 1 are placed according to their order of insertion.
Example 2:
Input: Arr = { 5, 5, 3, 4, 4, 3, 2, 5, 1}
Output: Arr = { 5, 5, 5, 3, 3, 4, 4, 2, 1}
Explanation:
In the above-mentioned example, element 5 is the first repeating element so it will be placed first in the array with its occurrences. After 5, 4 is the next repeating element so the occurrences of 4 will be placed after 5. Finally, the non-repeating elements 2 and 1 will be placed at the end of the array according to their order of insertion.
Example 3:
Input: Arr = { 1, 2, 3, 4, 5, 6, 7, 8, 8, 9}
Output: Arr = { 8, 8, 1, 2, 3, 4, 5, 6, 7, 9}
Explanation:
In the above-mentioned example, the array only has a single element which repeats once. So, the only repeating element 8 will be placed at the beginning of the array and since no other element is repeated all other elements will be placed after 8 in their order of insertion.
Simple Approach: Using Nested Loops
The simple solution or approach for solving the above-mentioned problem statement would be using nested loops. Two loops will be utilized for generating the result in this approach. The outer-most loop is utilized for traversing all the elements of the one-dimensional array one-by-one. inner loop will be used for checking whether it is the first occurrence or not. If it is the first occurrence, then the inner-most loop will be utilized for printing the element and its occurrences in order.
Filename: GroupElements.java
//Java program to group multiple occurrence of array elements ordered by first occurrence.
//This approach uses the concepts of nested-loops for checking and printing the elements of the array according to the problem statement.
//This is the simplest approach.
class GroupElements
{
static void group_Array_Elements(int array[], int len)
{
// This is used to initialize all the elements of the array as not-check_visited.
boolean check_visited[] = new boolean[len];
for (int i = 0; i < len; i++)
{
check_visited[i] = false;
}
// This loop is used to traverse all the elements of the array.
for (int i = 0; i < len; i++)
{
// This statement is used to check whether this is the first occurence or not.
if (!check_visited[i])
{
// If this is the first occurrence, the inner loop will print all the occurences of the element including it.
System.out.print(array[i] + " ");
for (int j = i + 1; j < len; j++)
{
if (array[i] == array[j])
{
System.out.print(array[i] + " ");
check_visited[j] = true;
}
}
}
}
}
// This is the main method.
public static void main(String[] args)
{
int array[] = { 5, 5, 3, 4, 4, 3, 2, 5, 1};
int len = array.length;
groupElements(array, len);
}
}
// This Java program was written by R K Eshwar.
Output:
5, 5, 5, 3, 3, 4, 4, 2, 1
Complexity Analysis:
In the above-mentioned approach or java program, two loops are used. So, the time complexity of this approach is O(n^2). Also, an additional array was created for storing the elements of the visited array. So, the space complexity of the above-mentioned java program is O(n). In the time complexity and space complexity, n stands for the number of elements in the one-dimensional input array.
Approach: Hashing based Algorithm
In this approach, we will be using the concepts and functionalities of hashing to solve the above-mentioned problem statement in java.
//This is a Java program to group Multiple Occurrence of Array Elements Ordered by First Occurrence in Java.
//This approach uses Hashing concepts to generate result for the above-mentioned problem statement.
import java.util.*;
class GroupElements
{
//This is a hashing based approach used for grouping all the repeated occurrences of elements in an array.
static void ordered_group(int array[])
{
// The below-mentioned statement creates a hashmap object.
HashMap hashmap_variable = new HashMap();
// The below-mentioned statement travereses the array and checks for multiple occurrences in the hashmap.
for (int i=0; i
{
// Checks if the array element is already present in the hashmap or not.
Integer count_prev = hashmap_variable.get(array[i]);
if (count_prev == null)
count_prev = 0;
// This statement will increment the count of element.
hashmap_variable.put(array[i], count_prev + 1);
}
// This statement is used to traverse the elements of array again.
for (int i=0; i
{
//Checks whether this is the first occurrence of the element or not.
Integer count = hashmap_variable.get(array[i]);
if (count != null)
{
// If this is the first occurrence of the element, it will print the element "count" times.
for (int j=0; j
System.out.print(array[i] + " ");
// The element then will be removed from the Hashmap.
hashmap_variable.remove(array[i]);
}
}
}
// This is the main method.
public static void main (String[] args)
{
int array[] = {5, 5, 3, 4, 4, 3, 2, 5, 1};
ordered_group(array);
}
}
Output:
5, 5, 5, 3, 3, 4, 4, 2, 1
Complexity Analysis:
The above-mentioned approach or java program takes O(1) time complexity as the concepts and functionalities of HashMap are being used in the program. The operations of HashMap such as insertion, deletion, searching take O(1) time complexity.
Whereas, the HashMap is created to store all the elements of the array in it. So the space complexity of the above-mentioned program will be O(n) where n denotes the size of the array.
Approach : Binary Tree Based Algorithm
Step-1: Create an empty integer array of the size n and input the values of array elements or take them as input from the user.
Step-2: The next step of the above-mentioned binary tree related algorithm is creating a new Binary Search Tree (BST). The node of the binary search tree will have two parameters. One parameter will contain the array element and the other parameter will store its count.
Step-3: The next step of this algorithm or approach will be traversing the entire input array and perform the following instructions:
- If the element of the array is not present in the binary search tree, then store the array element in the binary search tree. The value of the element will be stored in the array element part of the node and the count of the array element will be stored as 0.
- If the element of the array is already stored in the binary search tree, then increment the count of the array element by one.
Step-4: The final step of this algorithm is traversing the input array again and performing the following instructions:
- If the element of the array is present in the binary search tree, then perform the following:
- Obtain the count of the array element from its node.
- Print the array element ‘count’ times.
- Then remove the array element from the binary search tree.
Step-5: End of the algorithm.
Complexity Analysis:
The above-mentioned binary search tree approach takes O(nlog(n)) time complexity where n denotes the number of elements in the input array.
Points to Remember:
The above-mentioned binary search tree approach can be optimized or improved by utilizing self-balancing binary search trees such as AVL tree and Red-Black Tree.