Majority Element

Write a function findMajorityElement that takes an array of size n and returns the element that appears more than n/2 times. This element is called the majority element. You may assume that the majority element always exists in the array.

Constraints

The array will have at least one element and at most 10,000 elements.
Each element in the array is an integer.
The majority element appears more than n/2 times in the array, where n is the size of the array.

Examples

Input: [3, 2, 3]
Output: 3
Explanation: The number 3 appears twice, which is more than 3/2 times.

Input: [2, 2, 1, 1, 1, 2, 2]
Output: 2
Explanation: The number 2 appears four times, which is more than 7/2 times.

Tips

Consider using Boyer-Moore Voting Algorithm for an efficient solution.
This algorithm allows finding a majority element in linear time and constant space.

Solution

What’s the Exact Problem?

The problem is to identify the majority element in an array, which is an element that appears more than n/2 times, where n is the size of the array.

Steps to Understand the Problem

Understand that you need to find an element that occurs more than half the time in the array.
Recognize that there will always be one majority element in the array as per the given constraint.
The challenge is to find this element efficiently.

Examples

Input: [3, 2, 3]
Output: 3

Input: [2, 2, 1, 1, 1, 2, 2]
Output: 2

What Your Function Should Do?

The function findMajorityElement should take an array of integers and return the majority element, which is the element that appears more than n/2 times in the array.

How to Solve the Problem?

Use the Boyer-Moore Voting Algorithm, which is an efficient method to find the majority element.
This algorithm works by maintaining a count of a potential candidate for majority element and reducing the count when a different element is encountered.

Example Code Solution

def findMajorityElement(nums):
    count = 0
    candidate = None

    for num in nums:
        if count == 0:
            candidate = num
        count += (1 if num == candidate else -1)

    return candidate

Example Usage

print(findMajorityElement([3, 2, 3]))  # Output: 3
print(findMajorityElement([2, 2, 1, 1, 1, 2, 2]))  # Output: 2

How this Code Works?

The function initializes count as 0 and candidate as None.
It then iterates through each number in the array.
When the count is 0, it sets the current number as the new candidate for majority element.
The count is incremented for every occurrence of the candidate and decremented for every different number.
Since the majority element appears more than half the time, the final candidate is guaranteed to be the majority element.

Time Complexity:

The time complexity of this solution is O(n), where n is the number of elements in the array. This is because the solution involves a single pass through the array, with constant time operations within the loop. The space complexity is O(1) as it only uses two additional variables, count and candidate.