Solving the Majority Element Problem in Java Arrays

The Majority Element Problem is a classic algorithmic challenge that frequently appears in programming interviews and coding competitions. The objective is simple yet profound: find the element in an array that occurs more than half the time. In this blog post, we will explore various approaches to solving the Majority Element Problem in Java while keeping code clarity and performance in mind.

Understanding the Problem

Before we dive into the solutions, let’s define the problem more clearly. Given an array of size n, an element is said to be a "majority element" if it appears more than n/2 times. For example, in the array [2, 2, 1, 1, 2], the majority element is 2 since it appears 3 times (which is greater than 5/2 = 2.5).

Approach 1: Brute Force Solution

The simplest way to solve this problem is to use a brute-force approach that counts the occurrences of each element.

Code Example

import java.util.HashMap;

public class MajorityElementBruteForce {
    public static Integer findMajorityElement(int[] nums) {
        HashMap<Integer, Integer> counts = new HashMap<>();
        for (int num : nums) {
            counts.put(num, counts.getOrDefault(num, 0) + 1);
        }
        
        for (Integer key : counts.keySet()) {
            if (counts.get(key) > nums.length / 2) {
                return key;
            }
        }
        
        return null; // No majority element found
    }

    public static void main(String[] args) {
        int[] nums = {2, 2, 1, 1, 2};
        Integer majorityElement = findMajorityElement(nums);
        System.out.println("Majority Element: " + majorityElement);
    }
}

Explanation

HashMap Count: We use a HashMap to count the occurrences of each number. This allows us to map each unique number to its frequency.
Check Occurrences: After counting, we iterate through the entries in the HashMap to check if any number appears more than n/2 times.

Complexity Analysis

Time Complexity: O(n) for counting and checking.
Space Complexity: O(n) for storing counts in the HashMap.

This solution is straightforward but can be inefficient in terms of space, especially with large arrays and diverse elements.

Approach 2: Moore's Voting Algorithm

An optimal way to solve this problem is using Moore's Voting Algorithm, which exploits the properties of majority elements. This algorithm runs in O(n) time and O(1) space.

Code Example

public class MajorityElementMooresVoting {
    public static Integer findMajorityElement(int[] nums) {
        int candidate = -1;
        int count = 0;

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

        // Verification step
        count = 0;
        for (int num : nums) {
            if (num == candidate) {
                count++;
            }
        }

        return (count > nums.length / 2) ? candidate : null;
    }

    public static void main(String[] args) {
        int[] nums = {2, 2, 1, 1, 2};
        Integer majorityElement = findMajorityElement(nums);
        System.out.println("Majority Element: " + majorityElement);
    }
}

Explanation

Finding a Candidate: We iterate through the array, maintaining a candidate and a count. The count increases if we see the candidate again and decreases for other elements. When the count reaches zero, we update our candidate.
Verification: After finding a candidate, a second pass through the array confirms whether the candidate is indeed the majority element.

Complexity Analysis

Time Complexity: O(n) for both passes.
Space Complexity: O(1), as we only use a few variables.

Moore’s Voting Algorithm is efficient and elegant, making it a popular solution to this problem.

Approach 3: Sorting the Array

An alternative method involves sorting the array first and then directly accessing the middle element.

Code Example

import java.util.Arrays;

public class MajorityElementSorting {
    public static Integer findMajorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2]; // Middle element will be the majority if it exists
    }

    public static void main(String[] args) {
        int[] nums = {2, 2, 1, 1, 2};
        Integer majorityElement = findMajorityElement(nums);
        System.out.println("Majority Element: " + majorityElement);
    }
}

Explanation

Sorting: By sorting the array, the majority element will inevitably be located at the middle position (if it exists).
Retrieving the Element: After sorting, we directly return the middle element.

Complexity Analysis

Time Complexity: O(n log n), due to sorting.
Space Complexity: O(1) if we ignore the space used by the sorting algorithm.

While this solution is less efficient than the previous ones, it’s useful when you need to sort the array for another reason.

The Last Word

The Majority Element Problem is a great exercise for understanding different algorithmic techniques. We explored three approaches: a brute-force method using a hash map, the highly efficient Moore's Voting Algorithm, and a sorting method. Each has its trade-offs between simplicity, runtime, and space complexity.

For practical applications, Moore's Voting Algorithm is the most preferred due to its linear time complexity and constant space requirements.

Solving the Majority Element Problem in Java Arrays

Understanding the Problem

Approach 1: Brute Force Solution

Code Example

Explanation

Complexity Analysis

Approach 2: Moore's Voting Algorithm

Code Example

Explanation

Complexity Analysis

Approach 3: Sorting the Array

Code Example

Explanation

Complexity Analysis

The Last Word

Further Reading