Java Program to Find an Index of an Array Such That Its Value Occurs at More Than Half of Indices in The Array

Problem Statement

Finding an index in an array such that the value at that index appears at more than half of the array's indices is the task at hand. This number is frequently referred to as the array's majority element.

An element that occurs more than n/2 times, where n is the array's length, is considered the majority element in the array. Return the index of one such occurrence if such an element is present; else, return -1 if there is no majority element.

Example

Input:

Output:

 0 

Explanation

An array element 2 appears 4 times out of 6 indices. Since 4 > 6/2 (which is 3), 2 is the majority element. The function should return any index of 2. In this case, the index 0 is one valid answer. Other valid answers could be 2, 3, or 5.

Solution to the Approach

The Boyer-Moore Voting Algorithm is an optimal solution with a time complexity of O(n) and a space complexity of O(1). The algorithm is based on the following observations:

1. Candidate Selection: It is possible to find the majority element if we cancel each occurrence of a distinct element pair. The element that survives these cancellations is the majority element.
2. Verification: After identifying the candidate, we need to verify that it is actually the majority element by counting its occurrences.

Output:

 Index of majority element: 0 

Explanation

The Java code provided efficiently finds an index of an array where the value at that index is the majority element, meaning it appears more than half the time in the array. The findMajorityElementIndex method serves as the primary function and calls two helper methods: findCandidate and isMajority.

The findCandidate method uses the Boyer-Moore Voting Algorithm to select a potential majority element by iterating through the array and adjusting a candidate and its count. If the current count is zero, it sets a new candidate; otherwise, it increases or decreases the count based on whether the current element matches the candidate.

Once a candidate is identified, the isMajority method verifies whether this candidate truly is a majority element by counting its occurrences in the array. If the candidate's count exceeds half the length of the array, it is confirmed as the majority element, and the findMajorityElementIndex method returns the first index of this candidate.

If no majority element exists, it returns -1. This method works best, assuring efficient performance for massive arrays with an O(n) time complexity and an O(1) space complexity.

Conclusion

The code above offers an effective method of utilizing the Boyer-Moore Voting Algorithm to discover the index of an array element that appears more than half of the time in the array; this solution runs in O(n) time with O(1) space complexity, making it ideal for this application.