Group Multiple Occurrence of Array Elements Ordered by first Occurrence

Difficulty Level Easy
Frequently asked in Accolite Adobe Amazon Delhivery Fourkites
Array HashViews 2923

You are given a question in which you have given an unsorted array with multiple occurrences of numbers. The task is to group all the multiple occurrences of array elements ordered by first occurrence. Meanwhile, the order should be the same as the number comes.

Example

Input:

[ 2, 3,4,3,1,3,2,4]

Output:

[2 2 3 3 3 4 4 1]

Input:

[ 5,4,1,5,4,1,5,6]

Output:

[5 5 5 4 4 1 1 6]

Algorithm

  1. Declare HashMap.
  2. Traverse the array and put all the elements and its frequency into the HashMap.
  3. While traversing the array and get the frequency of each element.
    1. Print that key up to that frequency times.
    2. Remove that arr[i] (key).

Explanation for Group Multiple Occurrence of Array Elements

We are going to use Hashing for it. Hashing provides a feature of storing the elements as a key-value pair. In this question, we are going to use a key as an array element and a value as a frequency of each element. We simply insert the element if it’s not present in the hash table. else increase the count(key-value) of the element.

First, we will declare a HashMap say “myMap”. We then traverse the whole array and counting and storing the frequency of each element.

Let us consider an example and understand it.

Example

arr=[5, 4, 1, 5, 4, 1, 5, 6]

i=0, arr[i]=5

myMap={5:1}

i=1, arr[i]=4

myMap={4:1,5:1}

i=2, arr[i]=1

myMap={1:1,4:1,5:1}

i=3, arr[i]=5

myMap={1:1,4:1,5:2}

i=4, arr[i]=4

myMap={1:1,4:2,5:2}

i=5, arr[i]=1

myMap={1:2,4:2,5:2}

i=6, arr[i]=5

myMap={1:2,4:2,5:3}

i=6, arr[i]=6

myMap={1:2,4:2,5:3,6:1}

Now we will have a myMap and values in it.

We will get the frequency after traversing an array again with the ordered element in an array. Taking each array element with its frequency and make a loop until that frequency time and after printing all the array elements until frequency times remove that array key so that it will not print again in the further traversal.

Arr[i]=5 frequency = 3

5 will be printed, 3 times, then we will remove that key in myMap, so whenever we read 5 in an array it will not be present in hashmap and doesn’t print.

Arr[i]=4 frequency = 2

4 will be printed, 2 times, the key will be removed in myMap, so whenever we read 4 in an array it will not be present in HashMap and doesn’t print.

Arr[i]=1 frequency = 2

1 will be printed, 2 times, then we will remove that key in myMap, so whenever we read 5 in an array and it will not be present in HashMap and doesn’t print.

Now 5 comes in array but it will not be present in HashMap and same happens and do nothing until the element is found which is present in HashMap.

Arr[i]=6 frequency =1

6 will be printed, 1 time, the key will be removed in myMap, so whenever we read 4 in the array it will not be present in hashmap and doesn’t print.

We will have the output now as 5 5 5 4 4 1 1 6.

Implementation

C++ program for Group Multiple Occurrence of Array Elements Ordered by first Occurrence

#include<iostream>
#include<unordered_map>

using namespace std;
void arrangeInOrder(int arr[], int n)
{
    unordered_map<int, int> myMap;

    for (int i=0; i<n; i++)
    {
        myMap[arr[i]]++;
    }
    for (int i=0; i<n; i++)
    {
        int count = myMap[arr[i]];
        for (int j=0; j<count; j++)
            cout<<arr[i]<< " ";

        myMap.erase(arr[i]);
    }
}
int main()
{
    int arr[] = {10, 5, 3, 10, 10, 4, 1, 3};
    int n=sizeof(arr)/sizeof(arr[0]);
    arrangeInOrder(arr,n);
    return 0;
}

10 10 10 5 3 3 4 1

Java program

import java.util.HashMap;

class multipleOccurences
{
    public static void arrangeInOrder(int arr[])
    {
        HashMap<Integer, Integer> myMap= new HashMap<Integer, Integer>();

        for (int i=0; i<arr.length; i++)
        {
            Integer current = myMap.get(arr[i]);
            if (current == null)
                current = 0;

            myMap.put(arr[i], current + 1);
        }
        for (int i=0; i<arr.length; i++)
        {
            Integer count = myMap.get(arr[i]);
            if (count != null)
            {
                for (int j=0; j<count; j++)
                {
                    System.out.print(arr[i] + " ");
                }
                myMap.remove(arr[i]);
            }
        }
    }
    public static void main (String[] args)
    {
        int arr[] = {10, 5, 3, 10, 10, 4, 1, 3};
        arrangeInOrder(arr);
    }
}

10 10 10 5 3 3 4 1

Complexity Analysis for Group Multiple Occurrence of Array Elements

Time Complexity

O(n) where “n” is the number of elements in the array.

Space Complexity

O(n) where “n” is the number of elements in the array.

Reference

Translate »