Tutorial: Majority Element Interview Question and Solution in C++

Introduction

In this tutorial, we’ll explore the “Majority Element” interview question and provide a comprehensive solution using C++. The Majority Element is a common coding interview problem that tests your ability to find an element that appears more than n/2 times in an array of size n. We’ll walk through the problem statement, discuss different approaches to solving it, and implement the solution in C++.

Problem Statement

You are given an array of integers, and you need to find the majority element. A majority element is an element that appears more than n/2 times in the array, where n is the size of the array. It is guaranteed that a majority element always exists in the array.

For example, consider the array:

[3, 1, 3, 3, 2]

In this case, the majority element is 3, as it appears three times, which is more than half of the total elements (5/2 = 2.5).

Brute Force Approach

A straightforward approach to solving this problem is by using nested loops to count the occurrences of each element and finding the one that appears more than n/2 times. Here’s a step-by-step breakdown of this approach:

1. Initialize a variable maxCount to keep track of the maximum count of an element.
2. Initialize a variable majorityElement to store the element that appears more than n/2 times.
3. Loop through each element num in the array.

• Initialize a variable count to 0.
• Loop through the array again to count the occurrences of num.
• If count is greater than maxCount, update maxCount and majorityElement.

1. After both loops, majorityElement will contain the majority element.

Implementation

Here’s the implementation of the brute force approach in C++:

#include <iostream>
#include <vector>

int findMajorityElement(const std::vector<int>& nums) {
    int n = nums.size();
    int maxCount = 0;
    int majorityElement = 0;

    for (int num : nums) {
        int count = 0;
        for (int otherNum : nums) {
            if (otherNum == num) {
                count++;
            }
        }

        if (count > maxCount) {
            maxCount = count;
            majorityElement = num;
        }
    }

    return majorityElement;
}

int main() {
    std::vector<int> nums = {3, 1, 3, 3, 2};
    int majority = findMajorityElement(nums);
    std::cout << "Majority Element: " << majority << std::endl;

    return 0;
}

Optimal Approach: Boyer-Moore Voting Algorithm

The brute force approach works, but it has a time complexity of O(n^2) due to the nested loops. We can achieve a more efficient solution using the Boyer-Moore Voting Algorithm, which has a time complexity of O(n) and a space complexity of O(1).

The key idea behind this algorithm is that if we cancel out each occurrence of an element x with all the other elements that are different from x, then x will be the majority element if it indeed is a majority element.

Here’s a step-by-step breakdown of the Boyer-Moore Voting Algorithm:

1. Initialize two variables candidate and count to keep track of the current candidate for the majority element and its count, respectively.
2. Loop through each element num in the array.

• If count is 0, assign num to candidate and set count to 1.
• If num is the same as candidate, increment count; otherwise, decrement count.

1. After the loop, the candidate will contain the majority element.
2. To confirm that the candidate is the majority element, loop through the array again and count its occurrences.

• If the count of candidate is greater than n/2, return candidate; otherwise, return -1 to indicate no majority element.

Implementation

Here’s the implementation of the Boyer-Moore Voting Algorithm in C++:

#include <iostream>
#include <vector>

int findMajorityElement(const std::vector<int>& nums) {
    int candidate = 0;
    int count = 0;

    for (int num : nums) {
        if (count == 0) {
            candidate = num;
            count = 1;
        } else if (num == candidate) {
            count++;
        } else {
            count--;
        }
    }

    // Confirm the candidate is the majority element
    count = 0;
    for (int num : nums) {
        if (num == candidate) {
            count++;
        }
    }

    if (count > nums.size() / 2) {
        return candidate;
    } else {
        return -1; // No majority element
    }
}

int main() {
    std::vector<int> nums = {3, 1, 3, 3, 2};
    int majority = findMajorityElement(nums);

    if (majority != -1) {
        std::cout << "Majority Element: " << majority << std::endl;
    } else {
        std::cout << "No Majority Element" << std::endl;
    }

    return 0;
}

Testing and Analysis

Let’s test our solution with various inputs to ensure its correctness and efficiency.

Test Case 1

Input:

[3, 1, 3, 3, 2]

Output:

Majority Element: 3

Test Case 2

Input:

[1, 2, 2, 3, 2]

Output:

Majority Element: 2

Test Case 3

Input:

[1, 2, 3, 4, 5]

Output:

No Majority Element

Conclusion

In this tutorial, we’ve covered the Majority Element interview question and provided a detailed solution in C++. We discussed both the brute force approach and the more efficient Boyer-Moore Voting Algorithm. By using the Boyer-Moore algorithm, we can solve the problem in O(n) time complexity and O(1) space complexity, making it a much more efficient solution. Remember to thoroughly test your code with different test cases to ensure its correctness and efficiency in various scenarios. Happy coding!