Find Majority Element in an Array in Java
Problem
A majority element is one that appears more than n/2 times in an array of length n — strictly more than every other value combined.
Given an array of integers that is guaranteed to contain a majority element, find it.
Java Program
public class MajorityElement {
public static void main(String[] args) {
int[] arr = {4, 4, 2, 4, 6, 4, 4};
int candidate = arr[0];
int count = 1;
for (int i = 1; i < arr.length; i++) {
if (count == 0) { // vote canceled out, switch to a new candidate
candidate = arr[i];
count = 1;
} else if (arr[i] == candidate) {
count++; // vote for the current candidate
} else {
count--; // vote against the current candidate
}
}
System.out.println("Majority element: " + candidate);
}
}Output
Core Logic
Treating matching values as votes for a candidate and mismatches as votes against it, a single running candidate survives every non-majority value canceling itself out.
- 1
candidatestarts as the first element, withcountat1. - 2If
countever drops to0, the current element becomes the newcandidate, andcountresets to1. - 3An element equal to
candidateincrementscount; any other element decrements it. - 4Because the true majority element outnumbers every other value combined, it's mathematically guaranteed to survive as the final
candidate.
[4, 4, 2, 4, 6, 4, 4], count dips down to 1 after the 2 and 6 are seen, but candidate stays 4 throughout and finishes with count = 3.Key Point: This algorithm assumes a majority element actually exists — given an array with no true majority, it would still confidently report some candidate, just an incorrect one, since nothing here double-checks the final count against n/2.
Why: A single pass tracks just a candidate value and a running vote count, with no extra data structure needed.
Key Concepts
Approach 2: Frequency Map
import java.util.HashMap;
import java.util.Map;
public class MajorityElementFrequency {
public static void main(String[] args) {
int[] arr = {4, 4, 2, 4, 6, 4, 4};
Map<Integer, Integer> freq = new HashMap<>();
int majority = arr[0];
for (int num : arr) {
int count = freq.getOrDefault(num, 0) + 1;
freq.put(num, count);
if (count > arr.length / 2) { // crossed the majority threshold
majority = num;
}
}
System.out.println("Majority element: " + majority);
}
}
Output
Core Logic
Counting every value's occurrences directly, and checking each running count against n/2 as it grows, finds the majority element without relying on the voting trick's cancellation insight.
- 1A
HashMap<Integer, Integer>namedfreqtracks each value's running count as the array is scanned. - 2
freq.getOrDefault(num, 0) + 1computes the updated count for the current value. - 3As soon as a value's count exceeds
arr.length / 2, it's recorded as themajorityelement. - 4Unlike the voting algorithm, this doesn't need the guarantee that a majority exists — a count simply never crosses the threshold if there isn't one.
[4, 4, 2, 4, 6, 4, 4], the count for 4 keeps climbing and crosses 7 / 2 = 3 once its fourth occurrence is seen.Key Point: This trades the voting algorithm's O(1) space for O(n), in exchange for not needing to assume a majority element exists ahead of time — the count crossing the threshold is verified directly.
Why: The map holds one entry per distinct value in the array, up to n in the worst case, alongside the single pass used to build it.
Key Concepts
Approach 3: Java 8
import java.util.Arrays;
import java.util.Map;
import java.util.stream.Collectors;
public class MajorityElementStream {
public static void main(String[] args) {
int[] arr = {4, 4, 2, 4, 6, 4, 4};
// Groups by value, counts occurrences, then picks the entry with the highest count
int majority = Arrays.stream(arr)
.boxed()
.collect(Collectors.groupingBy(n -> n, Collectors.counting()))
.entrySet()
.stream()
.max(Map.Entry.comparingByValue())
.get()
.getKey();
System.out.println("Majority element: " + majority);
}
}
Output
Core Logic
Grouping every value by identity and counting occurrences, then picking the entry with the highest count, finds the majority element declaratively — without the voting trick's cancellation insight or a hand-written frequency map.
- 1
Arrays.stream(arr).boxed()turns the primitive array into aStream<Integer>. - 2
Collectors.groupingBy(n -> n, Collectors.counting())builds aMap<Integer, Long>of each value's occurrence count. - 3
entrySet().stream().max(Map.Entry.comparingByValue())finds the entry with the highest count. - 4
.get().getKey()extracts that entry's key — the value that occurred most often.
[4, 4, 2, 4, 6, 4, 4] by identity gives counts 4: 4, 2: 1, 6: 2; the entry with the highest count, 4, is reported.Key Point: Like the voting algorithm, this trusts the problem's guarantee that a true majority exists — it reports whichever value has the highest count even if that count doesn't actually exceed n/2, since nothing here checks the count against that threshold.
Why: groupingBy() visits every element once to build a map holding one entry per distinct value, and finding the max entry afterward only scans those distinct entries.