Tutorial: Majority Element Interview Question and Solution in Java

Introduction

In this tutorial, we will delve into the “Majority Element” interview question, a classic problem frequently encountered in coding interviews. We will discuss what the problem entails, its significance, and step through a Java solution to tackle it. By the end of this tutorial, you will have a clear understanding of the problem, its solutions, and how to implement them effectively.

Problem Statement

Majority Element: Given an array of integers, the majority element is defined as the element that appears more than ⌊n/2⌋ times, where n is the length of the array. In simpler terms, it is the element that occurs more frequently than any other element in the array.

The problem expects us to write an algorithm to find the majority element in the array or determine if there is no majority element present.

Example

Let’s consider an array: [3, 1, 3, 3, 2]. Here, the majority element is 3, as it appears 3 times in the array, which is more than half of the array’s length (which is 5). If no majority element exists, the algorithm should return an appropriate response, such as -1.

Importance of the Problem

The Majority Element problem is not only a common coding interview question but also has real-world applications. In voting systems, surveys, and data analysis, identifying the majority element can provide crucial insights. This problem tests a candidate’s ability to design efficient algorithms and make optimal use of data structures.

Approach 1: Brute Force

Let’s start with a simple, brute force approach. We can iterate through the entire array and, for each element, count its occurrences. If the count exceeds ⌊n/2⌋, we have found the majority element. Otherwise, we continue with the next element. This approach guarantees finding the majority element (if it exists), but it has a time complexity of O(n^2), making it highly inefficient for larger arrays.

public class MajorityElementBruteForce {

    public static int findMajorityElement(int[] nums) {
        int n = nums.length;

        for (int num : nums) {
            int count = 0;
            for (int i = 0; i < n; i++) {
                if (nums[i] == num) {
                    count++;
                }
            }
            if (count > n / 2) {
                return num;
            }
        }

        return -1; // No majority element
    }

    public static void main(String[] args) {
        int[] nums = {3, 1, 3, 3, 2};
        int result = findMajorityElement(nums);
        if (result != -1) {
            System.out.println("Majority Element: " + result);
        } else {
            System.out.println("No Majority Element");
        }
    }
}

Approach 2: Boyer-Moore Voting Algorithm

The Boyer-Moore Voting Algorithm is a highly efficient approach to solve the Majority Element problem in O(n) time complexity and O(1) space complexity. This algorithm leverages the observation that the majority element occurs more times than all other elements combined.

How Boyer-Moore Algorithm Works

1. Initialize two variables: candidate and count. The candidate variable represents the potential majority element, and count keeps track of its occurrences.
2. Iterate through the array:

• If count is 0, assign the current element as the candidate and set count to 1.
• If the current element equals the candidate, increment count.
• If the current element is different from the candidate, decrement count.

1. After iterating through the array, the candidate will hold the potential majority element. However, it’s essential to verify whether it actually is the majority element by counting its occurrences again.
2. If the count of the potential majority element is greater than ⌊n/2⌋, then it’s the majority element; otherwise, there is no majority element.

Let’s implement the Boyer-Moore Voting Algorithm in Java:

public class MajorityElementBoyerMoore {

    public static int findMajorityElement(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--;
            }
        }

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

        return count > nums.length / 2 ? candidate : -1;
    }

    public static void main(String[] args) {
        int[] nums = {3, 1, 3, 3, 2};
        int result = findMajorityElement(nums);
        if (result != -1) {
            System.out.println("Majority Element: " + result);
        } else {
            System.out.println("No Majority Element");
        }
    }
}

Conclusion

The Majority Element problem is a classic coding interview question that tests a candidate’s algorithmic and problem-solving skills. In this tutorial, we explored two different approaches to solve the problem: the brute force method and the highly efficient Boyer-Moore Voting Algorithm. The Boyer-Moore algorithm is preferred due to its linear time complexity and minimal space usage.

By understanding the problem’s significance and practicing the implementation of these approaches in Java, you will be better prepared to tackle similar algorithmic problems in coding interviews and real-world scenarios.