Majority Element - Java Solution

1. Introduction

In this post, we'll delve into a solution for the "Majority Element" problem, a common challenge in array processing and voting algorithms. The task is to identify an element in an array that appears more than half the time (i.e., more than ⌊n / 2⌋ times), assuming such an element always exists in the array.

Problem

Given an array nums of size n, the objective is to find and return the majority element, which is defined as the element that appears more than ⌊n / 2⌋ times.

2. Solution Steps

1. Utilize the Boyer-Moore Voting Algorithm, which is an efficient method to find the majority element.

2. Initialize two variables: count to keep track of the frequency, and candidate to store the potential majority element.

3. Iterate through the array:

- If count is 0, assign the current element as the candidate.

- Increment count if the current element is the same as candidate, otherwise decrement it.

4. Return candidate as it is the majority element.

3. Code Program

public class MajorityElement {
    public static void main(String[] args) {
        int[] nums = {2,2,1,1,1,2,2};
        System.out.println(findMajorityElement(nums)); // Test the function
    }

    // Function to find the majority element in the array
    public static int findMajorityElement(int[] nums) {
        int count = 0;
        Integer candidate = null;

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

        return candidate;
    }
}

Output:

2

Explanation:

1. findMajorityElement: This function implements the Boyer-Moore Voting Algorithm to find the majority element in nums.

2. It initializes candidate as null and count as 0.

3. As the function iterates over nums, it tracks the potential majority element by increasing or decreasing the count based on whether the current element matches the candidate.

4. When count drops to 0, it selects a new candidate.

5. The algorithm guarantees that the final candidate is the majority element as it appears more than ⌊n / 2⌋ times.

6. This approach is highly efficient, requiring only a single pass over the array, resulting in O(n) time complexity and O(1) space complexity.