DSA-007 · Boyer–Moore cancellation plus verification
Majority Element
Intermediate · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 9845 deterministic checks. Learner drafts are not executed.
Understand the problem
Return the value occurring strictly more than half the time, if such a value exists. The input does not promise that a majority exists.
- nums is non-null with 0–100,000 signed int values. Empty input has no majority.
- Return OptionalInt.of(value) for a count greater than floor(n/2), or OptionalInt.empty() otherwise. There can be at most one strict majority.
- Preserve input. Any int, including -1 and Integer.MIN_VALUE, can be a valid majority, so no int sentinel denotes absence.
Examples
Input:
[3,2,3]
Output:OptionalInt[3]3 occurs twice among three positions.
Input:
[1,2,3]
Output:OptionalInt.emptyThe first pass may leave a candidate, but no value is a majority.
Input:
[1,1,2,2]
Output:OptionalInt.emptyExactly half does not satisfy a strict majority.
Before you start
- Strict majority threshold
- Candidate selection versus proof of existence
Recognize the structure
Canceling pairs of different values preserves any existing strict majority. This can identify a candidate with constant state, but it does not establish that the original input contained one. The verification pass belongs to this contract.
Try before revealing
Hint 1
What happens to a strict majority when two different values are removed?
Hint 2
Represent only the unmatched residue.
Hint 3
Select by cancellation, then verify the candidate’s full count.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Count frequencies in a map
Scan values, increment each map count, and return when a count exceeds n/2. For [2,1,2], counts become {2:1}, {2:1,1:1}, then {2:2,1:1}, establishing majority 2. Expected time is O(n) and space O(u). The optimized method improves retained state rather than the asymptotic scan time.
Improve the baseline
Cancel different pairs
If one value has more than half the positions, removing one occurrence of it together with one different occurrence cannot eliminate its strict advantage among survivors.
Keep only a candidate and unmatched balance
When balance is zero, start a new candidate. Matching values increment balance; different values decrement it. The state represents unmatched copies after pair cancellation, not the candidate’s total frequency.
Verify against the original array
Count the selected candidate in a second pass and test occurrences>n/2. If no majority existed, cancellation can still leave a nonempty residue, so returning the candidate alone is unsound.
Why it is correct
Cancellation invariant
After each prefix, that prefix can be partitioned into pairs of different values plus balance unmatched copies of the current candidate. Resetting at zero and canceling a mismatch preserve this partition.
Majority survival
A strict majority cannot be completely removed by different-value pair cancellation because there are fewer other occurrences available to cancel it. Thus if an original majority exists, the final unmatched candidate must be that value.
Verification and absence
The second scan establishes the candidate’s actual original count. Passing the strict threshold proves it is a majority. Failing it proves no other majority was missed, by the survival argument. Empty input correctly fails the count test.
Complete Java reference and baseline
Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.
import java.util.HashMap;
import java.util.Map;
import java.util.OptionalInt;
public final class Solution {
public static OptionalInt majorityElement(int[] nums) {
int candidate = 0, balance = 0;
for (int value : nums) {
if (balance == 0) candidate = value;
balance += value == candidate ? 1 : -1;
}
int occurrences = 0;
for (int value : nums) if (value == candidate) occurrences++;
return occurrences > nums.length / 2 ? OptionalInt.of(candidate) : OptionalInt.empty();
}
public static OptionalInt baseline(int[] nums) {
Map<Integer, Integer> counts = new HashMap<>();
for (int value : nums) {
int count = counts.merge(value, 1, Integer::sum);
if (count > nums.length / 2) return OptionalInt.of(value);
}
return OptionalInt.empty();
}
}
Read the meaningful blocks
Reset only at zero balance
A zero balance means all preceding residue has been canceled, allowing a new candidate.
Interpret balance correctly
It is unmatched cancellation residue, not a frequency or an answer by itself.
Use OptionalInt for absence
Every int is a legitimate data value. Verification determines whether the optional is present.
Complexity
O(n) deterministic time for two scans and O(1) auxiliary space. Output is one optional value; input is unchanged.
The counting baseline is expected O(n) time and O(u) map entries. A sorting approach would add ordering work and require a copy to preserve the array.
Exact-state walkthroughs
Reveal normal and boundary traces
Candidate must be verified
Input: [1,2,3] · Result: OptionalInt.empty
Step 1 of 8: Begin without unmatched occurrences.
Balance is cancellation residue, not original frequency.
- 0: 1
- 1: 2
- 2: 3
| Variable | Value |
|---|---|
| candidate | 0 |
| balance | 0 |
| optionalRepresentation | "null means OptionalInt.empty; a number means a present value" |
See the affected Java block
1 import java.util.HashMap; 2 import java.util.Map; 3 import java.util.OptionalInt; 4 public final class Solution { 5 public static OptionalInt majorityElement(int[] nums) { 6 int candidate = 0, balance = 0; 7 for (int value : nums) { 8 if (balance == 0) candidate = value; 9 balance += value == candidate ? 1 : -1; 10 } 11 int occurrences = 0; 12 for (int value : nums) if (value == candidate) occurrences++; 13 return occurrences > nums.length / 2 ? OptionalInt.of(candidate) : OptionalInt.empty(); 14 } 15 public static OptionalInt baseline(int[] nums) { 16 Map<Integer, Integer> counts = new HashMap<>(); 17 for (int value : nums) { 18 int count = counts.merge(value, 1, Integer::sum); 19 if (count > nums.length / 2) return OptionalInt.of(value); 20 } 21 return OptionalInt.empty(); 22 } 23 } 24
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Begin without unmatched occurrences.
Balance is cancellation residue, not original frequency.
- candidate
0- balance
0- optionalRepresentation
"null means OptionalInt.empty; a number means a present value"
- Match the candidate or cancel a different pair.
The processed prefix consists of different-value pairs plus balance copies of candidate.
- index
0- value
1- candidate
1- balance
1
- Match the candidate or cancel a different pair.
The processed prefix consists of different-value pairs plus balance copies of candidate.
- index
1- value
2- candidate
1- balance
0
- Match the candidate or cancel a different pair.
The processed prefix consists of different-value pairs plus balance copies of candidate.
- index
2- value
3- candidate
3- balance
1
- Count this candidate in the original input.
This separate count, not the residual balance, will establish majority existence.
- index
0- candidate
3- occurrences
0
- Count this candidate in the original input.
This separate count, not the residual balance, will establish majority existence.
- index
1- candidate
3- occurrences
0
- Count this candidate in the original input.
This separate count, not the residual balance, will establish majority existence.
- index
2- candidate
3- occurrences
1
- Return the contract result.
The completed state satisfies the declared output and mutation contract.
- result
null
A negative majority
Input: [-1,-1,2] · Result: OptionalInt[-1]
Step 1 of 8: Begin without unmatched occurrences.
Balance is cancellation residue, not original frequency.
- 0: -1
- 1: -1
- 2: 2
| Variable | Value |
|---|---|
| candidate | 0 |
| balance | 0 |
| optionalRepresentation | "null means OptionalInt.empty; a number means a present value" |
See the affected Java block
1 import java.util.HashMap; 2 import java.util.Map; 3 import java.util.OptionalInt; 4 public final class Solution { 5 public static OptionalInt majorityElement(int[] nums) { 6 int candidate = 0, balance = 0; 7 for (int value : nums) { 8 if (balance == 0) candidate = value; 9 balance += value == candidate ? 1 : -1; 10 } 11 int occurrences = 0; 12 for (int value : nums) if (value == candidate) occurrences++; 13 return occurrences > nums.length / 2 ? OptionalInt.of(candidate) : OptionalInt.empty(); 14 } 15 public static OptionalInt baseline(int[] nums) { 16 Map<Integer, Integer> counts = new HashMap<>(); 17 for (int value : nums) { 18 int count = counts.merge(value, 1, Integer::sum); 19 if (count > nums.length / 2) return OptionalInt.of(value); 20 } 21 return OptionalInt.empty(); 22 } 23 } 24
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Begin without unmatched occurrences.
Balance is cancellation residue, not original frequency.
- candidate
0- balance
0- optionalRepresentation
"null means OptionalInt.empty; a number means a present value"
- Match the candidate or cancel a different pair.
The processed prefix consists of different-value pairs plus balance copies of candidate.
- index
0- value
-1- candidate
-1- balance
1
- Match the candidate or cancel a different pair.
The processed prefix consists of different-value pairs plus balance copies of candidate.
- index
1- value
-1- candidate
-1- balance
2
- Match the candidate or cancel a different pair.
The processed prefix consists of different-value pairs plus balance copies of candidate.
- index
2- value
2- candidate
-1- balance
1
- Count this candidate in the original input.
This separate count, not the residual balance, will establish majority existence.
- index
0- candidate
-1- occurrences
1
- Count this candidate in the original input.
This separate count, not the residual balance, will establish majority existence.
- index
1- candidate
-1- occurrences
2
- Count this candidate in the original input.
This separate count, not the residual balance, will establish majority existence.
- index
2- candidate
-1- occurrences
2
- Return the contract result.
The completed state satisfies the declared output and mutation contract.
- result
-1
Test the contract
Input:
[]
Output:OptionalInt.emptyNo occurrences.
Input:
[9]
Output:OptionalInt[9]One position is a strict majority.
Input:
[2,2,1,1,1,2,2]
Output:OptionalInt[2]Cancellation and verification.
Input:
[-1,-1,2]
Output:OptionalInt[-1]No numeric absence sentinel.
Common mistakes and counterexamples
Skip verification when existence is not guaranteed
Counterexample: [1,2,3] can leave candidate 3 without a majority.
Count the candidate in the original data.
Accept half the positions
Counterexample: [1,1,2,2] has no strict majority.
Use >n/2, not ≥n/2.
Return -1 to signal absence
Counterexample: [-1,-1,2] has valid majority -1.
Use OptionalInt or another explicit presence representation.
Follow-ups
The contract guarantees a majority exists.
The second pass may be omitted only under that explicit promise. Keep the proof that pair cancellation preserves the promised value.
Find every value occurring more than n/3 times.
At most two values qualify. Maintain two candidate balances, cancel triples appropriately, then verify both counts; do not simply reuse one candidate.
Use a non-replayable stream without an existence promise.
One candidate and balance cannot always certify the exact original frequency at the end. Explain replay/storage requirements or change the guarantees; do not invent a verified answer from the first-pass residue.
Your Java attempt
Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.
Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.
No unsaved text changes · 112/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.