1. Introduction

The "Majority Element" problem focuses on finding an element in an array that appears more than half the time (i.e., more than ⌊n / 2⌋ times). It's a common problem to test understanding of array manipulation and voting algorithms.

2. Problem

Given an array nums of size n, return the majority element. The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

3. Solution in C++

``````int majorityElement(vector<int>& nums) {
int count = 0;
int candidate = 0;

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

return candidate;
}

``````

Explanation:

1. Use Boyer-Moore Voting Algorithm.

2. Initialize count and candidate.

3. Traverse the array: if count is 0, set the current element as candidate.

4. Increase count if the current element equals candidate, otherwise decrease count.

5. The remaining candidate after the loop is the majority element.

4. Solution in Java

``````public int majorityElement(int[] nums) {
int count = 0;
Integer candidate = null;

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

return candidate;
}

``````

Explanation:

1. Implement the Boyer-Moore Voting Algorithm.

3. Iterate over the array, changing candidate when count drops to 0.

4. Increment count for every match with candidate, otherwise decrement.

5. The candidate at the end is the majority element.

5. Solution in Python

``````def majorityElement(nums):
count = 0
candidate = None

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

return candidate

``````

Explanation:

1. Apply the Boyer-Moore Voting Algorithm.