Home » Technical Interview Questions » Hashing Interview Questions » Group Multiple Occurrence of Array Elements Ordered by first Occurrence

Group Multiple Occurrence of Array Elements Ordered by first Occurrence


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}

READ  Check if a given array contains duplicate elements within k distance from each other

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.

READ  Find subarray with given sum (Handles Negative Numbers)

Space Complexity

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

Reference

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!!

You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Abhishek

Abhishek was able to crack Microsoft after practicing questions from TutorialCup