Hashing: Given an array, find the majority element

Coding Interview Questions

1 min read

Problem Statement:

You are given an array of repeated numbers. You need to return all the numbers that repeats [n/3] times

Example:

Input: arr = [1, 2, 1]

Output: 1

Solution 1: Hashmap Approach

In this approach we will use map to sore the frequency of the numbers.

Then we check all the elements inside the map one by one and check with the majority number and return the result.

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

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

vector<int> solution(vector<int>& nums) 
{
    int majorityNumber = nums.size()/3;

    unordered_map<int, int> map;

    vector<int> result;
    
    for(auto num : nums)
    {
        map[num]++;
    }
    
    for(auto num : map)
    {
        if(num.second > majorityNumber)
        {
            result.push_back(num.first);
        }
    }
    return result;
}

int main() 
{
    vector<int> arr = {3,2,3};

    vector<int> result = solution(arr);

    for(auto num: result)
        cout <<num <<" ";

    return 0;
}