Find the Majority Element

📌 Definition:

📖 Detailed Explanation:

Boyer-Moore voting: keep a candidate and a counter; increment when the current element matches the candidate, decrement otherwise, and pick a new candidate when the counter hits zero. The majority element survives. O(n) time, O(1) space — far better than a frequency map.

💻 Solutions:

• Java
• JavaScript
• Python

public static int majority(int[] a) {
    int candidate = a[0], count = 0;
    for (int x : a) {
        if (count == 0) candidate = x;
        count += (x == candidate) ? 1 : -1;
    }
    return candidate;
}

function majority(a) {
  let candidate = a[0], count = 0;
  for (const x of a) {
    if (count === 0) candidate = x;
    count += (x === candidate) ? 1 : -1;
  }
  return candidate;
}

def majority(a):
    candidate, count = None, 0
    for x in a:
        if count == 0:
            candidate = x
        count += 1 if x == candidate else -1
    return candidate

🔑 Key Points:

• Boyer-Moore voting: candidate + counter
• Counter to 0 -> adopt the current element
• O(n) time, O(1) space
• Verify with a second pass if existence is not guaranteed

🌍 Real-World Example: