Group Elements - C++ Solution

1. Introduction

This blog post explores a common problem in array manipulation: grouping duplicate elements while preserving their original order of first occurrence. The challenge lies in rearranging an unsorted array such that all instances of each element are grouped together.

Problem

Given an unsorted integer array containing many duplicate elements, the task is to rearrange it so that the same element appears together, and the relative order of the first occurrence of each element remains unchanged.

2. Solution Steps

1. Create a map to keep track of the count of each element in the array.

2. Iterate over the array and update the count in the map.

3. Iterate over the array again and group elements based on their count while maintaining the order of first occurrence.

4. Modify the array in place or create a new array for the grouped elements.

3. Code Program

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

void groupElements(vector<int>& nums) {
    unordered_map<int, int> countMap;
    for (int num : nums) {
        countMap[num]++;
    }

    int index = 0;
    for (int num : nums) {
        if (countMap[num] > 0) {
            for (int i = 0; i < countMap[num]; i++) {
                nums[index++] = num;
            }
            countMap[num] = 0;
        }
    }
}

int main() {
    vector<int> nums = {5, 4, 5, 5, 3, 1, 2, 2, 4};
    groupElements(nums);

    // Output the grouped array
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

Output:

5 5 5 4 4 3 1 2 2

Explanation:

The function groupElements rearranges the given array to group duplicate elements while preserving the order of their first occurrence. It first counts the occurrences of each element, then iterates through the array, placing the correct number of occurrences of each element in place. For example, given the input array [5, 4, 5, 5, 3, 1, 2, 2, 4], the function rearranges it to [5, 5, 5, 4, 4, 3, 1, 2, 2], grouping all identical elements together.