169. Majority Element - Detailed Explanation

Complexity Analysis:

• Time Complexity: O(n²) – For each element, we perform a count operation which itself is O(n). This nested behavior results in quadratic time.
• Space Complexity: O(1) – No additional data structures (aside from loop counters) are used.

Java Code:

Approach 2: Sorting-Based Solution

Explanation:

• If we sort the array, the majority element will always be located at index n/2 (using 0-based indexing).
• This works because the majority element appears more than half the time, so it inevitably occupies the middle position of the sorted array.

Python Code:

Approach 3: Using HashMap (Frequency Count)

Explanation:

• Use a HashMap (or Python dictionary) to count occurrences of each number as you iterate through the array.
• Whenever a number’s count becomes more than n/2, you can return it immediately (since the majority element is guaranteed to exist).

Python Code:

Complexity Analysis:

• Time Complexity: O(n) – Counting each element is linear in the array size.
• Space Complexity: O(n) – In the worst case (no element more than once, though that can't happen here since majority exists), the HashMap would store all n elements.

Java Code:

Java Code:

Complexity Analysis:

• Time Complexity: O(n) – We perform a constant amount of work (increment/decrement and comparisons) for each element in the array.
• Space Complexity: O(1) – The algorithm uses only a couple of integer variables regardless of input size.

Edge Cases

• Single element array: If nums has just one element, that element is trivially the majority (because it appears 1 time which is more than n/2 when n=1). All approaches handle this naturally.
• All elements are the same: If the array is like [7, 7, 7, 7], the majority is 7. All approaches will correctly identify 7 (the brute force will count and find 7, sorting puts 7 in the middle, hash map will count 7, and Boyer-Moore will keep 7 as candidate).
• Negative or other range values: The array can contain negative numbers or large integers, but the logic of counting/sorting/comparison remains the same. For example, in [-1, -1, -1, 2, 3], -1 is the majority.
• Even length array with majority: If n is even, say 6, a majority element must appear at least 4 times (more than 6/2 = 3). For instance, in [5, 1, 5, 5, 2, 5], the majority element 5 appears 4 times which is > 3, and all methods will find 5 correctly.

(Note: By problem assumption, there's always a valid majority element. If that were not guaranteed, one would need an extra verification step after Boyer-Moore to confirm the candidate truly appears > n/2 times.)

Common Mistakes

• Using count() in a loop (Python): A common mistake is to use nums.count(x) inside a loop (like the brute force approach), which dramatically slows down the solution for large arrays (O(n²) time). It's fine for understanding, but one should avoid it for large input.

• Misunderstanding "majority": Ensure to check strictly greater than n/2 occurrences, not just greater or equal. If an element appears exactly n/2 times (and n is even), that's not more than half. However, the problem guarantee means this situation won't happen in valid inputs.

• Not considering all approaches: Using a HashMap or sorting is straightforward, but forgetting the Boyer-Moore algorithm means missing out on an optimal solution. Some might jump to hashing and overlook that an O(1) space solution exists.

• Boyer-Moore Implementation Bugs: When coding the Boyer-Moore voting algorithm, a common mistake is not resetting the candidate when count drops to zero, or misordering the increment/decrement logic. Make sure the algorithm follows the exact pattern (reset candidate when count = 0, then update count based on match or mismatch).

Related Problems

• Majority Element II (LeetCode 229): Find all elements that appear more than ⌊ n/3 ⌋ times. This is a similar problem where there can be up to two "majority" elements. An extended Boyer-Moore algorithm (tracking two candidates) can solve it in O(n) time.
• Check if any element appears more than n/2 times (General version): In scenarios where a majority element may or may not exist, you can still use the Boyer-Moore voting algorithm to find a candidate, then verify its count in a second pass.
• Top K Frequent Elements: While not exactly a majority problem, it also deals with counting frequencies of elements in an array. Hash maps and sorting or heap techniques are used there to find the most frequent elements.
• Find the Dominant Element in a stream: A streaming variant of the majority vote problem, where you use the Boyer-Moore algorithm to maintain a majority candidate as new elements flow in (useful in online algorithms or data stream processing).