Matrix: Given a matrix, count the majority element

Problem Statement:

You are given a 2D (m * n) matrix.

You need to find the majority element.

A majority element is a number whose count is greater than or equal to (n*m)/2

Example:

Input:

1 2 3
3 3 1
3 3 1

Output: 1

The number 3 and frequency is 4

Solution Explanation:

To solve this problem we will use map to store the frequency of elements with the element.

Then traverse the map and count the variable count majority element whose frequency is equal to or greater than (n*m)/2.

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

Code Solution

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


#define N 3 // row
#define M 3 // column

int solution(int arr[N][M])
{
    int result = 0;

    unordered_map<int, int> mp;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            mp[arr[i][j]]++;
        }
    }

    for (auto itr = mp.begin(); itr != mp.end(); itr++) {

        if (itr->second >= ((N * M) / 2)) {
            result++;
        }
    }

    return result;
}

int main()
{

    int mat[N][M] = { { 1, 2, 3 },
                      { 3, 3, 1 },
                      { 3, 3, 1 } };

    cout << solution(mat) << endl;

    return 0;
}

Output

1