Loop Array Hash Map Counting Prefix Sum
Learner Level

Implement the majorityElementValue method that returns the value that appears more than half of the time.

The input contains an integer array nums and its length size. Your task is to return the majority element.

The majority element is the value that appears more than size / 2 times in the array. For example, in [2,2,1,1,1,2,2], the value 2 appears more than half of the time, so the answer is 2.

Example 1
Input:
nums (int[]) = [2,2,1,1,1,2,2]
size (int) = 7
Return:
(int) 2
Example 2
Input:
nums (int[]) = [3,2,3]
size (int) = 3
Return:
(int) 3
Example 3
Input:
nums (int[]) = [1,1,1,2,3]
size (int) = 5
Return:
(int) 1

This can be solved efficiently using the Boyer-Moore voting algorithm.

Keep one candidate value and a counter. When the counter becomes zero, choose the current value as the new candidate. If the current value matches the candidate, increase the counter; otherwise, decrease it.

Because the majority element appears more than half of the time, all other values cannot fully cancel it out, so the remaining candidate is the answer.

Pseudocode:

function majorityElementValue(nums, size):
    candidate = 0
    count = 0
    for each num in nums:
        if count == 0:
            candidate = num
        if num == candidate:
            count++
        else:
            count--
    return candidate
Run your code to see the result.