77. Find the Majority Element

Given an array of n integers, find the element that occurs strictly more than n/2 times. If no such element exists, print -1.

Input: The first line contains an integer n. The second line contains n space-separated integers. Output: Print the element occurring strictly more than n/2 times, or -1 if no such element exists.

1 <= n <= 10^5

Boyer-Moore voting only works when you're looking for an element appearing MORE than n/2 times specifically - a weaker threshold (like n/3) requires tracking two candidates simultaneously, a natural but trickier extension worth knowing about.

Find the value that appears more than half the time in an array - if no value clears that bar, report that none exists. Brute force: For every distinct value, scan the whole array counting its occurrences directly - this costs O(n²) in the worst case if there are many distinct values. Optimised: The Boyer-Moore voting algorithm exploits a clever cancellation idea: if a TRUE majority element exists, it can never be fully 'cancelled out' by all the other elements combined, since by definition it outnumbers everything else put together - tracking a running candidate-and-counter pair finds it in a single linear pass, with a quick second pass only needed to confirm it's genuinely a majority (not just the survivor of an input with no true majority at all).

For every element in the array, scan the entire array again to count how many times it occurs, and if any element's count exceeds n/2, report it. This directly checks the definition of a majority element, but comparing every element against every other element means a huge amount of repeated counting work. Time: O(n^2) Space: O(1)

Make a single pass through the array, incrementing each element's count in a hash map as you go, then scan the map once to see if any value's count exceeds n/2. This gets the exact count of every distinct element in linear time instead of the quadratic repeated scanning of brute force, at the cost of extra memory to store the counts. Time: O(n) Space: O(n)

Walk through the array maintaining a current candidate and a counter starting at 0: whenever the counter hits 0, adopt the current element as the new candidate; then increment the counter if the current element matches the candidate, or decrement it otherwise. Because a true majority element (occurring more than n/2 times) can never be fully 'cancelled out' by all the other elements combined, whatever candidate survives this process is the only possible majority element; a second pass then confirms it actually occurs more than n/2 times (since no majority element is guaranteed to exist). This uses only a couple of variables instead of any hash map or nested scan. Time: O(n) Space: O(1)

1. Keep a 'current candidate' and a counter, both starting empty/zero. 2. Walk through the array: if the counter is 0, adopt the current element as the new candidate. 3. If the current element matches the candidate, increment the counter; otherwise, decrement it. 4. After the pass, do a SECOND scan to verify the surviving candidate actually appears more than n/2 times (a candidate can survive the first pass without truly being a majority, if no majority exists at all).

Time: O(n) - one pass to find a candidate, one more pass to verify it - both linear. Space: O(1) - just a candidate variable and a counter.

n = 1 (the single element trivially qualifies); an array with no element exceeding n/2 occurrences (print -1); and n = 10^5 (largest, confirming the Boyer-Moore approach with a verification pass is O(n)).

Be ready to explain explicitly WHY the verification pass is necessary - without it, an input with NO true majority element could still leave some candidate standing after the voting pass, and reporting it as-is would be wrong.