Find the Most Frequent / Majority Element in an Array - Java

Category: Medium | Concepts used: Frequency map, Boyer-Moore Voting Algorithm

---

Problem Statement

Given an array, find the element that appears most often. A special case, the majority element, is one that appears more than N/2 times.

Input : [1, 3, 2, 3, 3]      Output: 3   (appears 3 times, more than any other, and more than N/2=2.5)

Examples (with edge scenarios)

#	Input	Output	Why
1	[1, 3, 2, 3, 3]	3	Appears 3 times — most frequent, and a majority (3 > 5/2)
2	[1, 2, 3] (all distinct)	Any one of them, or “no majority”	No true majority element exists (each appears once) — clarify expected behavior
3	[7] (single element)	7	Trivially the most frequent (and majority)
4	[1, 1, 2, 2] (tie)	1 or 2	If there’s a tie for most frequent, clarify which should be returned
5	[] (empty)	Undefined	No elements to count — clarify expected behavior

Common Fresher Mistake

Mistake	What happens	Fix
Confusing “most frequent” with “majority element” (>N/2)	These aren’t always the same thing — an element can be most frequent without exceeding N/2	Clarify which definition the interviewer wants
Assuming a majority element always exists	If no element exceeds N/2, code may return a wrong/misleading answer silently	Verify the found candidate’s count actually exceeds N/2 if that’s the requirement

---

Before You Code: Clarify the Contract

Before choosing an algorithm, confirm whether the array may be null or empty, whether duplicates and original order matter, whether the method may modify the input, and whether the answer should contain values or original indices. These choices can change both the code and the best data structure.

Analogy: The Parliamentary Debate

Imagine a room filled with politicians from various parties (the numbers in the array):

• Boyer-Moore Voting Algorithm: A speaker from Party A stands up at the podium.
  • Every time a member of Party A enters the room, they support the speaker (count++).
  • Every time a member of a different party enters, they challenge the speaker, canceling out one vote of support (count--).
  • If the support count drops to zero, the current speaker is booed off the stage. The next politician to enter the room immediately takes the podium as the new speaker.
  • If one party has a strict majority (more than 50% of all people in the room, i.e., $>N/2$), they can never be fully cancelled out by all other parties combined! Even if every other politician teams up to challenge them, the majority party will always have at least one member standing on the podium at the end of the day.

---

Solution 1 — Using a Frequency Map (General “Most Frequent” — Always Works)

Intuition

Build a complete count of every value’s occurrences (same frequency-map pattern used in earlier problems). Once we know every value’s count, simply scan through the map once more to find whichever value has the highest count.

import java.util.HashMap;

public class MostFrequentElement {
    public static int mostFrequent(int[] arr) {
        HashMap<Integer, Integer> freq = new HashMap<>();
        for (int num : arr) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }

int mostFrequentValue = arr[0];
        int highestCount = 0;

for (var entry : freq.entrySet()) {
            if (entry.getValue() > highestCount) {
                highestCount = entry.getValue();
                mostFrequentValue = entry.getKey();
            }
        }
        return mostFrequentValue;
    }

public static void main(String[] args) {
        System.out.println(mostFrequent(new int[]{1, 3, 2, 3, 3})); // 3
        System.out.println(mostFrequent(new int[]{7}));               // 7
    }
}

Output:

3
7

Dry Run (arr = [1, 3, 2, 3, 3])

freq = {1:1, 3:3, 2:1}

Scanning entries:
1 -> count=1 > 0 -> mostFrequentValue=1, highestCount=1
3 -> count=3 > 1 -> mostFrequentValue=3, highestCount=3
2 -> count=1, not > 3 -> no change

Final: mostFrequentValue=3

Interviewer’s take

This is the correct, general-purpose answer — works regardless of whether a “true majority” (>N/2) exists, and correctly finds the simply most-common value. O(n) time, O(n) space. This is the answer to give unless the interviewer specifically emphasizes the “>N/2 majority” definition.

Follow-up questions you might get:

• “What if the interviewer specifically wants the classic ‘majority element’ (>N/2), and wants it done in O(1) space?” → leads to Solution 2 (Boyer-Moore Voting Algorithm).

---

Solution 2 — Boyer-Moore Voting Algorithm (O(1) Space, Only for True Majority >N/2)

Intuition

Imagine a “tug of war” between candidates. Walk through the array keeping one current “candidate” and a “vote count.” If the next element matches the candidate, increase the vote count; if it doesn’t match, decrease it. If the vote count ever drops to zero, that candidate has lost all its support — discard it and adopt the current element as the new candidate.

This clever trick works specifically because a true majority element (appearing more than N/2 times) can never be fully “cancelled out” by all the other elements combined — it’s guaranteed to survive as the final candidate.

public class MajorityElementBoyerMoore {
    public static int findMajority(int[] arr) {
        int candidate = arr[0];
        int count = 0;

for (int num : arr) {
            if (count == 0) {
                candidate = num; // adopt a new candidate
            }
            count += (num == candidate) ? 1 : -1;
        }

// Optional verification step: confirm candidate truly appears > n/2 times
        int actualCount = 0;
        for (int num : arr) {
            if (num == candidate) actualCount++;
        }
        if (actualCount > arr.length / 2) {
            return candidate;
        }
        throw new IllegalStateException("No majority element exists");
    }

public static void main(String[] args) {
        System.out.println(findMajority(new int[]{1, 3, 2, 3, 3})); // 3
    }
}

Output:

3

Dry Run (arr = [1, 3, 2, 3, 3])

candidate=1(initial), count=0

num=1: count==0 -> candidate=1; 1==1 -> count=1
num=3: 3==1? no -> count=1-1=0
num=2: count==0 -> candidate=2; 2==2 -> count=1
num=3: 3==2? no -> count=1-1=0
num=3: count==0 -> candidate=3; 3==3 -> count=1

Final candidate=3
Verification: actual count of 3 in array = 3, and 3 > 5/2=2.5 -> confirmed

Interviewer’s take

This is an advanced, impressive answer if the problem is specifically the “>N/2 majority element” version — O(n) time, and crucially O(1) extra space (no HashMap needed), compared to Solution 1’s O(n) space. The verification step is important to include — without it, if no true majority exists, the algorithm can return a wrong “candidate” with total confidence.

Follow-up questions you might get:

• “Why does this algorithm work?” → Because a true majority element appears more than all other elements combined; every time a non-majority element “cancels out” a vote, the majority element still has enough excess votes elsewhere to survive as the final candidate.
• “What happens if no majority element exists and you skip the verification step?” → The algorithm will still output some candidate confidently, but it may be wrong — this is exactly why the verification pass matters.

---

📊 Visual Flowchart

graph TD
    Start["Input: Array arr"] --> Init["candidate = arr[0], count = 0<br>i = 0"]
    Init --> Loop{"i < arr.length?"}
    Loop -->|Yes| CheckCount{"count == 0?"}
    CheckCount -->|Yes| UpdateCand["candidate = arr[i]"]
    CheckCount -->|No| CheckMatch{"arr[i] == candidate?"}
    UpdateCand --> CheckMatch
    CheckMatch -->|Yes| IncCount["count++"]
    CheckMatch -->|No| DecCount["count--"]
    IncCount --> Next["i++"]
    DecCount --> Next
    Next --> Loop
    Loop -->|No| Verify["Run verification pass to count candidate frequency"]
    Verify --> Confirm{"actualCount > arr.length / 2?"}
    Confirm -->|Yes| End["Return candidate"]
    Confirm -->|No| Err["Throw Exception / Return null"]

---

Final Verdict — Which Solution Should You Give?

• Clarify the exact definition wanted first — that alone is often the biggest signal to the interviewer.
• Solution 1 is the safe, general default. Solution 2 is a great bonus for the specific “>N/2” case when O(1) space is desired.

---

Quick Recap

Approach	Time	Space	Works for general “most frequent”?	Works for true majority (>N/2)?
Frequency map	O(n)	O(n)	Yes	Yes
Boyer-Moore Voting	O(n)	O(1)	No (needs true majority to exist)	Yes (with verification)