Finding the Majority Element

Given an array of elements, find the element that appears more than n / 2 times, where n is the size of the array. This is a common problem in computer science and has applications in data analysis, voting systems, and finding dominant patterns in datasets.

Problem Description

You are tasked with creating a function that accepts a non-empty array of elements (which can be numbers, characters, or any comparable type). Your function should identify and return the "majority element". The majority element is defined as the element that appears strictly more than n / 2 times, where n is the total number of elements in the input array.

It is guaranteed that a majority element always exists in the given array.

Key Requirements:

• The function must correctly identify and return the majority element.
• The function should handle arrays of varying sizes.

Expected Behavior:

• For a given input array, return the single element that satisfies the majority condition.

Edge Cases to Consider:

• An array with only one element.
• An array where the majority element's count is just above n / 2.

Examples

Example 1:

Input: [3, 2, 3]
Output: 3
Explanation: The array has 3 elements. 3 appears 2 times, which is more than 3 / 2 = 1.5.

Example 2:

Input: [2, 2, 1, 1, 1, 2, 2]
Output: 2
Explanation: The array has 7 elements. 2 appears 4 times, which is more than 7 / 2 = 3.5.

Example 3:

Input: [1]
Output: 1
Explanation: The array has 1 element. 1 appears 1 time, which is more than 1 / 2 = 0.5.

Constraints

• The input array will contain at least one element.
• The elements in the array will be of a type that supports equality comparison (e.g., integers, strings).
• A majority element is guaranteed to exist.
• The size of the array n can range from 1 to 10^5.
• The time complexity of your solution should ideally be O(n).
• The space complexity of your solution should ideally be O(1).

Notes

Consider how you can efficiently count the occurrences of elements. Think about data structures or algorithms that might help you process the array in a single pass or with minimal additional memory. The guarantee that a majority element always exists is a crucial piece of information.