Run your code 2 more times to open the solutions. The idea sticks better after an attempt. Majority Element in Python
3 reference approaches in Python, from brute force to the one to reach for. Compare them with yours.
Counter tallies every value in one pass, and most_common(1) returns the value with the highest count. Because the majority appears more than half the time, the most common value is the answer. The dictionary holds one entry per distinct value, so the extra space grows with the input.
from collections import Counter
def majority_element(nums: list[int]) -> int:
counts = Counter(nums)
value, _ = counts.most_common(1)[0]
return value
After sorting, every copy of the majority value forms one run, and a run longer than half the array must cover the middle position whichever end it starts from. So sorted(nums)[len(nums) // 2] is the answer. sorted builds a new list; nums.sort() would sort in place but change the caller's list.
def majority_element(nums: list[int]) -> int:
return sorted(nums)[len(nums) // 2]
Boyer–Moore voting keeps one candidate and a count. A matching value adds a vote, any other value removes one, and when the count reaches zero the next value becomes the new candidate. Every lost vote pairs one value with a different one and cancels both; the majority has more copies than everything else combined, so it cannot be cancelled out and is the candidate left at the end. Two variables, one pass.
def majority_element(nums: list[int]) -> int:
candidate, count = 0, 0
for n in nums:
if count == 0:
candidate = n
count += 1 if n == candidate else -1
return candidate
Majority Element in JavaScript
3 reference approaches in JavaScript, from brute force to the one to reach for. Compare them with yours.
A Map counts each value as the loop meets it. (counts.get(n) ?? 0) + 1 reads the old count or starts from zero, and the function returns as soon as one count passes nums.length / 2: that value can only be the majority, so the rest of the array is never read.
function majorityElement(nums) {
const counts = new Map();
for (const n of nums) {
const c = (counts.get(n) ?? 0) + 1;
if (c > nums.length / 2) return n;
counts.set(n, c);
}
}
Sorted, the majority value forms one run longer than half the array, so it always covers the middle index. toSorted leaves the input alone, and the comparator (a, b) => a - b matters: without it JavaScript compares the numbers as strings, so 10 sorts before 9. nums.length >> 1 is the floor of half the length.
function majorityElement(nums) {
const sorted = nums.toSorted((a, b) => a - b);
return sorted[nums.length >> 1];
}
Boyer–Moore voting keeps a candidate and a count. When the count is zero the current value takes over as the candidate; then a match adds a vote and anything else removes one. Every lost vote cancels one value against a different one, and the majority has more copies than all other values together, so it is the candidate still standing at the end. Two variables, one pass.
function majorityElement(nums) {
let candidate = 0;
let count = 0;
for (const n of nums) {
if (count === 0) candidate = n;
count += n === candidate ? 1 : -1;
}
return candidate;
}
Majority Element in TypeScript
3 reference approaches in TypeScript, from brute force to the one to reach for. Compare them with yours.
A Map<number, number> counts each value. The function returns the first value whose count passes nums.length / 2, which can only be the majority. The trailing throw is never reached on valid input, but it keeps the declared number return type honest for the compiler.
function majorityElement(nums: number[]): number {
const counts = new Map<number, number>();
for (const n of nums) {
const c = (counts.get(n) ?? 0) + 1;
if (c > nums.length / 2) return n;
counts.set(n, c);
}
throw new Error('no majority element');
}
Sorted, the majority value is one run longer than half the array, so it covers the middle index whatever its position. [...nums].sort((a, b) => a - b) sorts a copy numerically; the default sort would compare the numbers as strings. Math.floor(nums.length / 2) is the middle index for odd and even lengths alike.
function majorityElement(nums: number[]): number {
const sorted = [...nums].sort((a, b) => a - b);
return sorted[Math.floor(nums.length / 2)];
}
Boyer–Moore voting: one candidate, one count. A zero count hands the candidacy to the current value, a match adds a vote and a mismatch removes one. Each lost vote cancels a pair of different values, and the majority outnumbers all the others combined, so it survives to the end. O(n) time, O(1) extra space.
function majorityElement(nums: number[]): number {
let candidate = 0;
let count = 0;
for (const n of nums) {
if (count === 0) candidate = n;
count += n === candidate ? 1 : -1;
}
return candidate;
}
Majority Element in Java
3 reference approaches in Java, from brute force to the one to reach for. Compare them with yours.
counts.merge(n, 1, Integer::sum) inserts 1 for a new value or adds 1 to the stored count, and returns the new count in the same call. The first value whose count passes nums.length / 2 is the majority, so the method returns right there. The final throw only satisfies the compiler: the statement guarantees a majority.
import java.util.*;
public class Main {
static int majorityElement(int[] nums) {
HashMap<Integer, Integer> counts = new HashMap<>();
for (int n : nums) {
if (counts.merge(n, 1, Integer::sum) > nums.length / 2) {
return n;
}
}
throw new IllegalArgumentException("no majority element");
}
}
Once sorted, the majority value is a single run longer than half the array, so it always covers index nums.length / 2. Arrays.sort on an int[] is a dual-pivot quicksort that sorts in place; nums.clone() sorts a copy so the caller's array keeps its order.
import java.util.*;
public class Main {
static int majorityElement(int[] nums) {
int[] sorted = nums.clone();
Arrays.sort(sorted);
return sorted[sorted.length / 2];
}
}
Boyer–Moore voting keeps one candidate and an int counter. A zero counter hands the candidacy to the current value; a match adds a vote and anything else removes one. Every lost vote cancels two different values, and the majority has more copies than the rest combined, so it is the candidate at the end. No collections, no boxing, O(1) extra space.
import java.util.*;
public class Main {
static int majorityElement(int[] nums) {
int candidate = 0;
int count = 0;
for (int n : nums) {
if (count == 0) {
candidate = n;
}
count += (n == candidate) ? 1 : -1;
}
return candidate;
}
}
Majority Element in Go
3 reference approaches in Go, from brute force to the one to reach for. Compare them with yours.
A map[int]int counts each value. Reading a missing key gives the zero value, so counts[n]++ works without checking for the key first. The function returns as soon as a count passes len(nums)/2; the last return is only there because Go requires one after the loop.
package main
func majorityElement(nums []int) int {
counts := make(map[int]int)
for _, n := range nums {
counts[n]++
if counts[n] > len(nums)/2 {
return n
}
}
return 0 // unreachable: a majority always exists
}
Sorted, the majority value forms one run longer than half the slice, so it covers index len(nums)/2. slices.Sort sorts in place, and a slice shares its backing array with the caller, so the code sorts a copy made with slices.Clone instead.
package main
import "slices"
func majorityElement(nums []int) int {
sorted := slices.Clone(nums)
slices.Sort(sorted)
return sorted[len(sorted)/2]
}
Boyer–Moore voting with two int variables. When count is zero the current value becomes the candidate; a match adds a vote and anything else removes one. Every lost vote cancels two different values, and the majority outnumbers the rest combined, so it is the candidate left at the end. One pass, no allocation.
package main
func majorityElement(nums []int) int {
candidate, count := 0, 0
for _, n := range nums {
if count == 0 {
candidate = n
}
if n == candidate {
count++
} else {
count--
}
}
return candidate
}
Majority Element in C#
3 reference approaches in C#, from brute force to the one to reach for. Compare them with yours.
A Dictionary<int, int> counts each value. GetValueOrDefault reads the old count or 0, and the method returns as soon as a count passes nums.Length / 2. The closing throw never runs on valid input; C# needs it because the compiler cannot prove the loop always returns.
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution
{
public static int MajorityElement(int[] nums)
{
var counts = new Dictionary<int, int>();
foreach (int n in nums)
{
int c = counts.GetValueOrDefault(n) + 1;
if (c > nums.Length / 2) return n;
counts[n] = c;
}
throw new ArgumentException("no majority element");
}
}
Sorted, the majority value is one run longer than half the array, so it covers index nums.Length / 2. Array.Sort sorts in place, so the method sorts a Clone and leaves the caller's array untouched.
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution
{
public static int MajorityElement(int[] nums)
{
var sorted = (int[])nums.Clone();
Array.Sort(sorted);
return sorted[sorted.Length / 2];
}
}
Boyer–Moore voting keeps a candidate and a count. A zero count hands the candidacy to the current value; a match adds a vote and anything else takes one away. Each lost vote cancels two different values, and the majority has more copies than all the others together, so it is the candidate at the end. One pass, O(1) extra space.
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution
{
public static int MajorityElement(int[] nums)
{
int candidate = 0, count = 0;
foreach (int n in nums)
{
if (count == 0) candidate = n;
count += n == candidate ? 1 : -1;
}
return candidate;
}
}
Majority Element in C++
3 reference approaches in C++, from brute force to the one to reach for. Compare them with yours.
An unordered_map<int, int> counts each value. Here the [] operator is exactly right: a missing key is inserted with a count of 0, and ++counts[n] returns the new count. The first value whose count passes nums.size() / 2 is the majority. The final return is never reached on valid input.
#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
class Solution {
public:
int majorityElement(vector<int>& nums) {
unordered_map<int, int> counts;
const int half = (int)nums.size() / 2;
for (int n : nums) {
if (++counts[n] > half) return n;
}
return nums[0]; // unreachable: a majority always exists
}
};
Sorted, the majority value is one run longer than half the vector, so it covers index v.size() / 2. sort works in place, and nums arrives by reference, so the method sorts a copy and the caller's vector keeps its order.
#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
class Solution {
public:
int majorityElement(vector<int>& nums) {
vector<int> v(nums);
sort(v.begin(), v.end());
return v[v.size() / 2];
}
};
Boyer–Moore voting keeps a candidate and a count. A zero count hands the candidacy to the current value; a match adds a vote and anything else removes one. Each lost vote cancels two different values, and the majority outnumbers the rest combined, so it is the candidate at the end. Two ints, one pass, no allocation.
#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
class Solution {
public:
int majorityElement(vector<int>& nums) {
int candidate = 0, count = 0;
for (int n : nums) {
if (count == 0) candidate = n;
count += (n == candidate) ? 1 : -1;
}
return candidate;
}
};
Majority Element in C
3 reference approaches in C, from brute force to the one to reach for. Compare them with yours.
C has no built-in map, so count in a small open-addressing table twice the input's size: keys, counts and a used flag per slot, probed linearly from the value's hash. The first count that passes numsSize / 2 is the majority, so the loop stops there and frees the three arrays. The return after the loop only keeps every path returning an int.
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
int majorityElement(int* nums, int numsSize) {
int capacity = 1;
while (capacity < 2 * numsSize) capacity <<= 1;
unsigned mask = (unsigned)(capacity - 1);
int* keys = malloc(capacity * sizeof *keys);
int* counts = malloc(capacity * sizeof *counts);
bool* used = calloc(capacity, sizeof *used);
int answer = nums[0]; /* unreachable fallback: a majority always exists */
for (int i = 0; i < numsSize; i++) {
unsigned slot = (unsigned)nums[i] * 2654435761u & mask;
while (used[slot] && keys[slot] != nums[i]) slot = (slot + 1) & mask;
if (!used[slot]) {
used[slot] = true;
keys[slot] = nums[i];
counts[slot] = 0;
}
if (++counts[slot] > numsSize / 2) {
answer = nums[i];
break;
}
}
free(keys);
free(counts);
free(used);
return answer;
}
Once sorted, the majority value is one run longer than half the array, so it always covers index numsSize / 2. qsort sorts in place, so the function copies nums into a malloc'ed buffer first, reads the middle and frees the copy. The comparator returns (x > y) - (x < y) rather than x - y, which could overflow.
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
static int compareInts(const void* a, const void* b) {
int x = *(const int*)a;
int y = *(const int*)b;
return (x > y) - (x < y);
}
int majorityElement(int* nums, int numsSize) {
int* sorted = malloc(numsSize * sizeof *sorted);
memcpy(sorted, nums, numsSize * sizeof *sorted);
qsort(sorted, numsSize, sizeof *sorted, compareInts);
int answer = sorted[numsSize / 2];
free(sorted);
return answer;
}
Boyer–Moore voting keeps one candidate and an int counter. A zero counter hands the candidacy to the current value; a match adds a vote and anything else removes one. Every lost vote cancels two different values, and the majority has more copies than all the others combined, so it is the candidate left at the end. No allocation at all.
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
int majorityElement(int* nums, int numsSize) {
int candidate = 0;
int count = 0;
for (int i = 0; i < numsSize; i++) {
if (count == 0) candidate = nums[i];
count += nums[i] == candidate ? 1 : -1;
}
return candidate;
}
Majority Element in Kotlin
3 reference approaches in Kotlin, from brute force to the one to reach for. Compare them with yours.
One pass with a HashMap<Int, Int> from value to count. counts[n] ?: 0 reads a missing key as zero; the first value whose count passes nums.size / 2 is the majority, so the method returns right there. The final error(...) only satisfies the compiler, which needs every path to return an Int.
class Solution {
fun majorityElement(nums: IntArray): Int {
val counts = HashMap<Int, Int>()
for (n in nums) {
val count = (counts[n] ?: 0) + 1
if (count > nums.size / 2) return n
counts[n] = count
}
error("no majority element")
}
}
Once sorted, the majority value is one run longer than half the array, so it always covers index nums.size / 2. sortedArray() returns a sorted copy as a new IntArray, so the caller's array keeps its order and nothing is boxed.
class Solution {
fun majorityElement(nums: IntArray): Int {
val sorted = nums.sortedArray()
return sorted[sorted.size / 2]
}
}
Boyer–Moore voting keeps one candidate and an Int counter. A zero counter hands the candidacy to the current value; a match adds a vote and anything else removes one. Every lost vote cancels two different values, and the majority has more copies than the rest combined, so it is the candidate at the end, in O(1) extra space.
class Solution {
fun majorityElement(nums: IntArray): Int {
var candidate = 0
var count = 0
for (n in nums) {
if (count == 0) candidate = n
count += if (n == candidate) 1 else -1
}
return candidate
}
}
Majority Element in Rust
3 reference approaches in Rust, from brute force to the one to reach for. Compare them with yours.
One pass with a HashMap<i32, usize> from value to count. entry(n).or_insert(0) hands back a mutable reference to the count, new or existing, so one lookup both inserts and increments. The first count that passes nums.len() / 2 is the majority. The closing unreachable! only gives the function a value on every path.
use std::collections::HashMap;
impl Solution {
pub fn majority_element(nums: Vec<i32>) -> i32 {
let half = nums.len() / 2;
let mut counts: HashMap<i32, usize> = HashMap::with_capacity(nums.len());
for &n in &nums {
let count = counts.entry(n).or_insert(0);
*count += 1;
if *count > half {
return n;
}
}
unreachable!("the input always has a majority element")
}
}
Once sorted, the majority value is one run longer than half the array, so it always covers index len / 2. The function owns its Vec, so mut nums sorts that copy in place without touching anything the caller still holds. sort_unstable is the in-place pattern-defeating quicksort; stability means nothing for plain integers.
impl Solution {
pub fn majority_element(mut nums: Vec<i32>) -> i32 {
nums.sort_unstable();
nums[nums.len() / 2]
}
}
Boyer–Moore voting keeps one candidate and an i32 counter. A zero counter hands the candidacy to the current value; a match adds a vote and anything else removes one. Every lost vote cancels two different values, and the majority outnumbers all the others combined, so it is the candidate at the end. The counter never leaves the range 0 to n, so the debug build's overflow checks never fire.
impl Solution {
pub fn majority_element(nums: Vec<i32>) -> i32 {
let mut candidate = 0;
let mut count = 0;
for &n in &nums {
if count == 0 {
candidate = n;
}
count += if n == candidate { 1 } else { -1 };
}
candidate
}
}
Majority Element in Swift
3 reference approaches in Swift, from brute force to the one to reach for. Compare them with yours.
One pass with an [Int: Int] dictionary from value to count. counts[n, default: 0] reads a missing key as zero, and the first count that passes nums.count / 2 is the majority. The closing fatalError returns Never, which satisfies the compiler's every-path-returns check.
class Solution {
func majorityElement(_ nums: [Int]) -> Int {
var counts: [Int: Int] = [:]
counts.reserveCapacity(nums.count)
for n in nums {
let count = counts[n, default: 0] + 1
if count > nums.count / 2 {
return n
}
counts[n] = count
}
fatalError("no majority element")
}
}
Once sorted, the majority value is one run longer than half the array, so it always covers index count / 2. sorted() returns a new array; the parameter is a value type and immutable anyway, so the caller's array keeps its order.
class Solution {
func majorityElement(_ nums: [Int]) -> Int {
let sorted = nums.sorted()
return sorted[sorted.count / 2]
}
}
Boyer–Moore voting keeps one candidate and an Int counter. A zero counter hands the candidacy to the current value; a match adds a vote and anything else removes one. Every lost vote cancels two different values, and the majority has more copies than the rest combined, so it is the candidate at the end, in O(1) extra space.
class Solution {
func majorityElement(_ nums: [Int]) -> Int {
var candidate = 0
var count = 0
for n in nums {
if count == 0 {
candidate = n
}
count += n == candidate ? 1 : -1
}
return candidate
}
}
Majority Element in PHP
3 reference approaches in PHP, from brute force to the one to reach for. Compare them with yours.
One pass with an associative array from value to count. $counts[$n] ?? 0 reads a missing key as zero without a notice, and the first count that passes intdiv(count($nums), 2) is the majority, so the method returns right there. The final throw only states the precondition.
<?php
class Solution {
/**
* @param int[] $nums
* @return int
*/
function majorityElement(array $nums): int {
$half = intdiv(count($nums), 2);
$counts = [];
foreach ($nums as $n) {
$counts[$n] = ($counts[$n] ?? 0) + 1;
if ($counts[$n] > $half) {
return $n;
}
}
throw new InvalidArgumentException('no majority element');
}
}
Once sorted, the majority value is one run longer than half the array, so it always covers index intdiv(count($nums), 2). Arrays are passed by value in PHP, so sort($nums) reorders the method's own copy and the caller's array keeps its order. sort also renumbers the keys from 0, so the middle index is valid.
<?php
class Solution {
/**
* @param int[] $nums
* @return int
*/
function majorityElement(array $nums): int {
sort($nums);
return $nums[intdiv(count($nums), 2)];
}
}
Boyer–Moore voting keeps one $candidate and a counter. A zero counter hands the candidacy to the current value; a match adds a vote and anything else removes one. Every lost vote cancels two different values, and the majority has more copies than the rest combined, so it is the candidate at the end. No array is built, so the extra memory is O(1).
<?php
class Solution {
/**
* @param int[] $nums
* @return int
*/
function majorityElement(array $nums): int {
$candidate = 0;
$count = 0;
foreach ($nums as $n) {
if ($count === 0) {
$candidate = $n;
}
$count += $n === $candidate ? 1 : -1;
}
return $candidate;
}
}
Majority Element in Ruby
3 reference approaches in Ruby, from brute force to the one to reach for. Compare them with yours.
One pass with Hash.new(0), a hash whose missing keys read as 0, so counts[n] += 1 needs no check. The first count that passes nums.length / 2 is the majority, and return inside the block leaves the method right there. The raise after the loop only states the precondition.
# @param {Integer[]} nums
# @return {Integer}
def majority_element(nums)
half = nums.length / 2
counts = Hash.new(0)
nums.each do |n|
counts[n] += 1
return n if counts[n] > half
end
raise ArgumentError, 'no majority element'
end
Once sorted, the majority value is one run longer than half the array, so it always covers index nums.length / 2. sort without a bang returns a new array, so the caller's array keeps its order.
# @param {Integer[]} nums
# @return {Integer}
def majority_element(nums)
nums.sort[nums.length / 2]
end
Boyer–Moore voting keeps one candidate and a counter. A zero counter hands the candidacy to the current value; a match adds a vote and anything else removes one. Every lost vote cancels two different values, and the majority has more copies than the rest combined, so it is the candidate at the end, with no hash or copy at all.
# @param {Integer[]} nums
# @return {Integer}
def majority_element(nums)
candidate = nil
count = 0
nums.each do |n|
candidate = n if count.zero?
count += n == candidate ? 1 : -1
end
candidate
end
Majority Element in Dart
3 reference approaches in Dart, from brute force to the one to reach for. Compare them with yours.
One pass with a Map<int, int> from value to count. counts.update(n, (c) => c + 1, ifAbsent: () => 1) inserts or increments and returns the new count in one call. The first count that passes nums.length ~/ 2 is the majority. The final throw only satisfies the analyzer, which needs every path of an int method to end.
class Solution {
int majorityElement(List<int> nums) {
final half = nums.length ~/ 2;
final counts = <int, int>{};
for (final n in nums) {
if (counts.update(n, (c) => c + 1, ifAbsent: () => 1) > half) return n;
}
throw ArgumentError('no majority element');
}
}
Once sorted, the majority value is one run longer than half the list, so it always covers index length ~/ 2. List.sort works in place, so [...nums]..sort() spreads a copy and sorts that with the cascade operator, leaving the caller's list alone.
class Solution {
int majorityElement(List<int> nums) {
final sorted = [...nums]..sort();
return sorted[sorted.length ~/ 2];
}
}
Boyer–Moore voting keeps one candidate and an int counter. A zero counter hands the candidacy to the current value; a match adds a vote and anything else removes one. Every lost vote cancels two different values, and the majority has more copies than the rest combined, so it is the candidate at the end, in O(1) extra space.
class Solution {
int majorityElement(List<int> nums) {
var candidate = 0;
var count = 0;
for (final n in nums) {
if (count == 0) candidate = n;
count += n == candidate ? 1 : -1;
}
return candidate;
}
}
Majority Element in Scala
3 reference approaches in Scala, from brute force to the one to reach for. Compare them with yours.
One pass with a mutable.HashMap[Int, Int] from value to count. getOrElse(n, 0) reads a missing key as zero, and the first count that passes nums.length / 2 is the majority. A return inside the for would be a non-local return, so boundary and break(n) leave the loop with the answer instead. The throw after it only states the precondition.
import scala.collection.mutable
import scala.util.boundary, boundary.break
object Solution {
def majorityElement(nums: Array[Int]): Int = boundary {
val half = nums.length / 2
val counts = mutable.HashMap.empty[Int, Int]
for (n <- nums) {
val count = counts.getOrElse(n, 0) + 1
if (count > half) break(n)
counts(n) = count
}
throw IllegalArgumentException("no majority element")
}
}
Once sorted, the majority value is one run longer than half the array, so it always covers index length / 2. nums.sorted returns a new Array[Int] and leaves the caller's array alone; for primitive arrays with the default ordering it sorts the unboxed ints directly.
object Solution {
def majorityElement(nums: Array[Int]): Int = {
val sorted = nums.sorted
sorted(sorted.length / 2)
}
}
Boyer–Moore voting keeps one candidate and an Int counter in two vars. A zero counter hands the candidacy to the current value; a match adds a vote and anything else removes one. Every lost vote cancels two different values, and the majority has more copies than the rest combined, so it is the candidate at the end, in O(1) extra space.
object Solution {
def majorityElement(nums: Array[Int]): Int = {
var candidate = 0
var count = 0
for (n <- nums) {
if (count == 0) candidate = n
count += (if (n == candidate) 1 else -1)
}
candidate
}
}
FAQ for Python
Is max(set(nums), key=nums.count) a good one-liner?
It is short but quadratic: nums.count scans the whole list for every distinct value, so a 5,000-element list with 2,500 distinct values costs about 12.5 million comparisons where a Counter needs 5,000 steps. Counter(nums).most_common(1)[0][0] is the linear one-liner.
Why does the middle element of the sorted list always work?
The majority value fills more than n // 2 consecutive slots once sorted. If that run starts at index 0 it reaches past the middle; if it ends at the last index it starts before the middle; anywhere in between it covers it too. So index n // 2 is always inside the run.
What does Boyer–Moore return if there is no majority?
Some value, but not necessarily a meaningful one: on [1, 2, 3] it returns 3. The vote only finds the majority when one exists. If the input might not have one, run a second pass, nums.count(candidate) > len(nums) // 2, to confirm it.
Can statistics.mode solve it?
statistics.mode(nums) returns the most common value, which is the majority here, and it runs in linear time because it uses a Counter internally. It is fine for this problem, but it hides the idea, and in an interview the voting pass is what is usually asked for.
How do I find every value that appears more than n / 3 times?
At most two values can, so extend the vote to two candidates with two counters: a value that matches either candidate adds to its counter, a value that matches neither decrements both, and an empty slot adopts the value. Afterwards count both candidates again with nums.count to keep only the ones that really pass n // 3.
FAQ for JavaScript
Why does sort() without a comparator give the wrong middle?
The default sort converts values to strings and compares them as text, so [10, 9, 1, 1, 1].sort() gives [ 1, 1, 1, 10, 9 ] and [-1, -2, -10].sort() gives [ -1, -10, -2 ]. With negatives or mixed digit counts the middle can be the wrong value. Always pass (a, b) => a - b for numbers.
Can I count with a plain object instead of a Map?
Yes, counts[n] = (counts[n] || 0) + 1 works, but every key becomes a string, so returning the winner from Object.keys hands back '8' instead of 8 and a strict comparison with a number fails. A Map keeps the number keys as numbers.
What does the voting pass return if no value is a majority?
Just the last surviving candidate, which may mean nothing: [1, 2, 3] returns 3. The vote is only correct when a majority is guaranteed. Otherwise confirm it with a second pass, for example nums.filter((n) => n === candidate).length > nums.length / 2.
Does the hash-map version need a final return?
Not here: the statement guarantees a majority, so the early return n always fires. Without that guarantee the function would fall off the end and return undefined, so add an explicit fallback such as return null if you reuse it on arbitrary input.
Is reduce a cleaner way to write the vote?
It fits in one expression: nums.reduce(([c, k], n) => (k === 0 ? [n, 1] : [c, n === c ? k + 1 : k - 1]), [0, 0])[0]. It allocates a small array per element, though, and the plain for…of loop is easier to read and to step through.
FAQ for TypeScript
Why does the Map version end with a throw?
The compiler cannot know that a majority always exists. A function typed : number whose loop can finish without returning is rejected with "Function lacks ending return statement". The throw documents the precondition and satisfies the checker without inventing a fake value such as -1.
Why pass a comparator to sort?
Without one, sort converts the numbers to strings, so [10, 9, 1].sort() gives [1, 10, 9] and negatives come out in text order. TypeScript does not warn about this, because a number[] with no comparator is still valid code. (a, b) => a - b gives the numeric order the middle-element trick relies on.
Should I sort nums in place?
nums.sort changes the caller's array, which a function called majorityElement should not do. [...nums].sort(...) or nums.toSorted(...) (ES2023 lib) sorts a copy. The copy costs O(n) memory, which is why the outline lists the sorting approach as O(1) to O(n) space.
Does the voting pass work if there is no majority?
It always returns something, but without a majority that value is arbitrary: [1, 2, 3] yields 3. When the input is not guaranteed to have one, check the candidate in a second pass by counting it and comparing with nums.length / 2.
Can I type the counts as a Record instead of a Map?
A Record<number, number> compiles, but object keys are strings at run time, so Object.entries(counts) gives [string, number] pairs and you would need Number(key) to get the value back. A Map<number, number> keeps the keys as numbers end to end.
FAQ for Java
Why does the HashMap version need a throw at the end?
Java requires every path of an int method to return or throw. The compiler cannot see that the loop always returns early, so without the last line it reports "missing return statement". Throwing states the precondition instead of returning a made-up value such as -1.
Is merge better than getOrDefault and put?
counts.put(n, counts.getOrDefault(n, 0) + 1) hashes the key twice and needs a separate get to read the new count. merge(n, 1, Integer::sum) does the insert-or-add in one lookup and returns the updated value, which is exactly what the early exit needs.
Can I compare two counts from the map with ==?
Not safely. The map stores Integer objects, and == on two of them compares references; values outside the cached range -128 to 127 are separate objects, so two equal counts of 200 can compare unequal. Compare with equals, or unbox one side to int. Comparing an Integer with an int literal, as in merge(...) > nums.length / 2, unboxes and is fine.
Is a stream one-liner a good idea?
Arrays.stream(nums).boxed().collect(Collectors.groupingBy(n -> n, Collectors.counting())) builds the counts, and a second stream over the entry set picks the largest. It works but boxes every element, builds Long counts and reads less clearly than the loop. For this problem the plain loop or the voting pass is the better Java.
What does the voting pass return when there is no majority?
An arbitrary survivor: {1, 2, 3} returns 3. The vote is only correct when a majority exists. If the input might not have one, count the candidate in a second loop and check that it appears more than nums.length / 2 times.
FAQ for Go
Why does the map version still need a return after the loop?
Go requires a function with a result to end in a terminating statement, and a for range loop is not one. The compiler reports "missing return" without it. Returning 0 with a comment is the usual choice when the input guarantees the early return; panic("no majority") is the stricter alternative.
Why clone the slice before sorting?
A slice is a view onto an array. slices.Sort(nums) would reorder the caller's data too, because both share the same backing array. slices.Clone(nums) copies the elements first; on older Go versions append([]int(nil), nums...) does the same.
Is counts[n]++ safe for a key that is not in the map yet?
Yes. A missing key reads as 0, so the increment stores 1. Only a nil map panics on write, which is why the code creates it with make(map[int]int); a var counts map[int]int declaration would panic on the first counts[n]++.
Should I use sort.Ints or slices.Sort?
Both sort an []int in ascending order. slices.Sort (Go 1.21+) is generic and works for any ordered element type; sort.Ints is the older API and now calls slices.Sort internally. New code generally uses the slices package.
What does the voting pass return without a majority?
Whatever candidate survives, which means nothing on such input: []int{1, 2, 3} returns 3. When a majority is not guaranteed, count the candidate in a second loop and check it against len(nums)/2, returning (value, ok) in the comma-ok style.
FAQ for C#
Can LINQ solve it in one line?
nums.GroupBy(n => n).OrderByDescending(g => g.Count()).First().Key works and reads well, but it builds a group per distinct value and sorts the groups, so it costs more time and memory than the dictionary loop. nums.GroupBy(n => n).MaxBy(g => g.Count())!.Key (.NET 6+) skips the sort.
Why does the dictionary version end with a throw?
C# requires every code path of an int method to return a value or throw; without the last line the compiler reports CS0161, "not all code paths return a value". Throwing documents the guarantee instead of returning a fake answer.
Why clone before Array.Sort?
Array.Sort(nums) reorders the array the caller passed in, since arrays are reference types. (int[])nums.Clone() makes a shallow copy first, which for an int[] is a full copy of the values. nums.Order().ToArray() (.NET 7+) is the LINQ alternative.
GetValueOrDefault or TryGetValue?
Both do a single lookup. GetValueOrDefault(n) returns 0 for a missing key, which is exactly the starting count, so the loop body stays one line. TryGetValue(n, out int c) is the choice when you need to tell "missing" apart from a stored zero.
What does the voting pass return if no value is a majority?
The last surviving candidate, which is meaningless on such input: [1, 2, 3] returns 3. If a majority is not guaranteed, confirm it with nums.Count(n => n == candidate) > nums.Length / 2 before trusting the result.
FAQ for C++
Is counts[n] safe here when it is a bug in other problems?
Yes. operator[] inserts a value-initialised 0 for a missing key, which is the right starting count, so ++counts[n] both creates and increments the entry. It is only a bug when you mean to look a key up without adding it; then use find or contains (C++20).
Can nth_element replace the sort?
Only the middle element matters, so a full sort does more work than needed. auto mid = v.begin() + v.size() / 2; nth_element(v.begin(), mid, v.end()); places at *mid exactly what a full sort would put there, with smaller elements before it and larger after, in linear time on average. It is a drop-in replacement for the sort line.
Why copy the vector before rearranging it?
The method takes vector<int>& nums, so sort or nth_element on nums would reorder the caller's vector. Copying into vector<int> v(nums) costs O(n) memory and keeps the input intact; if the caller does not care, work on nums directly and the extra space drops to O(1).
Why return nums[0] after the loop in the map version?
Falling off the end of a non-void function is undefined behaviour in C++, and compilers warn about it. The guarantee makes the line unreachable, but returning a real element keeps the function well defined without inventing a sentinel.
What does the voting pass return when there is no majority?
An arbitrary survivor: {1, 2, 3} returns 3. The vote only finds a majority that exists. When it is not guaranteed, confirm with count(nums.begin(), nums.end(), candidate) > (int)nums.size() / 2 from <algorithm>.
FAQ for C
Why not write the qsort comparator as return x - y?
With values near ±10⁹ the difference can pass INT_MAX, and signed overflow is undefined behaviour in C; in practice the sign flips and qsort gets a wrong order. (x > y) - (x < y) only ever yields -1, 0 or 1.
Why copy the array before calling qsort?
qsort reorders the memory it is given, and nums belongs to the caller. Sorting a malloc'ed copy leaves the input untouched; the copy is freed before returning. If you own the buffer and its order does not matter, sorting nums in place saves the allocation.
Why make the hash table twice the input size?
Linear probing slows down as the table fills, because collisions form long runs of occupied slots. A power-of-two capacity at least 2 * numsSize keeps the load at half or less, and the power of two lets & mask replace the slower %.
Why cast to unsigned before hashing?
Multiplying signed ints can overflow, which is undefined behaviour. Unsigned arithmetic wraps by definition, so (unsigned)nums[i] * 2654435761u is a well-defined scramble, and masking keeps the slot in range for negative values too.
What does the voting pass return when there is no majority?
An arbitrary survivor: {1, 2, 3} returns 3. The vote is only correct when a majority exists. If the input might not have one, count candidate in a second loop and check that it appears more than numsSize / 2 times.
FAQ for Kotlin
Why does the HashMap version end with error()?
Kotlin requires a function with an Int return type to return on every path, and the compiler cannot see that the loop always returns early. error("...") throws an IllegalStateException and has type Nothing, so it satisfies the check without inventing a value such as -1.
Is groupingBy { it }.eachCount() a good alternative?
nums.groupingBy { it }.eachCount().maxBy { it.value }.key builds the same counts and reads well. It boxes every value, cannot stop early and walks the map once more to find the largest count, but for this input size it passes too.
What is the difference between sorted(), sortedArray() and sort()?
sort() sorts the IntArray in place and returns Unit. sortedArray() returns a new sorted IntArray. sorted() returns a List<Int> of boxed values. The middle-element approach only needs the copy, so sortedArray() is the fit.
Why counts[n] ?: 0 and not counts.getValue(n)?
The map's get operator returns Int?, null for a missing key, and the Elvis operator turns that into 0. getValue throws NoSuchElementException for a missing key, which is every value the first time it is seen.
What does the voting pass return when there is no majority?
An arbitrary survivor: intArrayOf(1, 2, 3) returns 3. The vote is only correct when a majority exists. If the input might not have one, check the result with nums.count { it == candidate } > nums.size / 2.
FAQ for Rust
Why does the HashMap version end with unreachable!()?
The function returns i32, so the code after the loop must produce one too, and the compiler cannot prove that the loop always returns. unreachable! panics with a message and has type !, which fits any return type, so it states the precondition instead of returning a made-up value.
What does entry(n).or_insert(0) return?
A &mut usize pointing at the count stored for n, inserting 0 first when the key is new. *count += 1 then updates the map in place. The alternative *counts.entry(n).or_default() += 1 does the same with the type's default value.
Is it fine to write mut nums in the parameter list?
Yes. mut on a parameter only makes the local binding mutable; the signature is still Vec<i32> by value. The caller moved the vector into the function, so sorting it changes nothing the caller can see.
Why sort_unstable instead of sort?
sort is a stable merge sort that allocates a buffer of half the length. sort_unstable sorts in place and is usually faster. Equal integers are indistinguishable, so stability buys nothing here.
Could select_nth_unstable replace the full sort?
nums.select_nth_unstable(mid) places the median at mid in O(n) on average, which is faster than a full sort. It is a selection algorithm rather than sorting, so the sorting approach keeps the plain sort_unstable; the voting pass is the O(n) answer that needs no extra work at all.
FAQ for Swift
What does the default: subscript do?
counts[n, default: 0] reads 0 for a missing key, so a new value needs no special case. Used with += 1 it also writes the result back, inserting or incrementing in one line. Plain counts[n] returns Int?, which would need unwrapping before adding.
Why fatalError at the end of the dictionary version?
A function that returns Int must return on every path, and the compiler cannot see that the loop always returns early. fatalError has return type Never, so it counts as leaving the function, and it stops loudly if the precondition is ever broken.
Can I sort nums in place with nums.sort()?
Not directly: function parameters are constants in Swift. Write var copy = nums and then copy.sort(), or use nums.sorted(), which does the same in one expression. Arrays are copy-on-write, so the copy is made when the sort first writes.
Is there a one-expression way to build the counts?
Dictionary(nums.map { ($0, 1) }, uniquingKeysWith: +) builds every count in one expression, and .max { $0.value < $1.value }!.key picks the largest. It works, but it allocates an array of tuples first and cannot stop early, so the loop is the leaner Swift.
What does the voting pass return when there is no majority?
An arbitrary survivor: [1, 2, 3] returns 3. The vote is only correct when a majority exists. If the input might not have one, check nums.filter { $0 == candidate }.count > nums.count / 2 before returning.
FAQ for PHP
Could array_count_values do the counting?
Yes: $counts = array_count_values($nums); arsort($counts); return array_key_first($counts); counts in C inside the engine and is short. It always counts the whole array and then sorts the counts, while the loop can stop as soon as one count passes half.
Why intdiv(count($nums), 2) and not count($nums) / 2?
The / operator returns a float when the division is not exact, so 5 / 2 is 2.5. Comparing a count with 2.5 still works, but indexing $nums[2.5] is deprecated in PHP 8.1 and later. intdiv gives the integer 2 in both places.
Does sort($nums) change the caller's array?
No. PHP passes arrays by value with copy-on-write, so the first write inside the method makes a private copy. Only a by-reference parameter, array &$nums, would let sort reorder the caller's array.
Why $counts[$n] ?? 0 instead of isset?
Reading a missing key raises an "Undefined array key" warning. The null coalescing operator ?? checks the key and falls back to 0 in one expression, which is shorter than an isset branch and does the same thing.
What does the voting pass return when there is no majority?
An arbitrary survivor: [1, 2, 3] returns 3. The vote is only correct when a majority exists. If the input might not have one, count $candidate in a second loop and check that it appears more than intdiv(count($nums), 2) times.
FAQ for Ruby
Is nums.tally.max_by a good one-liner?
nums.tally.max_by { |_, count| count }.first counts every value into a hash and picks the largest count. It is idiomatic since Ruby 2.7 and runs the counting in C, but it cannot stop early; the loop returns as soon as one count passes half.
Why Hash.new(0) and not {}?
A plain {} returns nil for a missing key, and nil + 1 raises NoMethodError. Hash.new(0) returns the default 0 instead, without storing it, so counts[n] += 1 works for new and seen values alike.
What is the difference between sort and sort!?
sort returns a new sorted array and leaves the receiver alone. sort! sorts the receiver in place and returns it. The argument is the caller's array, so the non-bang version is the polite choice.
Is nums.length / 2 integer division?
Yes. Dividing two Integer values floors the result, so 5 / 2 is 2. Only a Float operand, as in 5 / 2.0, gives 2.5.
What does the voting pass return when there is no majority?
An arbitrary survivor: [1, 2, 3] returns 3. The vote is only correct when a majority exists. If the input might not have one, check nums.count(candidate) > nums.length / 2 before returning.
FAQ for Dart
What does Map.update return?
The value stored after the call. With ifAbsent it inserts 1 for a new key; otherwise it applies the update function to the old count. Without ifAbsent, update throws an ArgumentError for a missing key.
Why ~/ instead of /?
In Dart / always returns a double, so 5 / 2 is 2.5, and a double cannot index a list. ~/ is integer division and gives 2.
What does [...nums]..sort() mean?
The spread [...nums] builds a new list with the same elements. The cascade ..sort() calls sort on that new list and evaluates to the list itself rather than to sort's void result, so the sorted copy lands in sorted.
Why throw at the end of the Map version?
With sound null safety, a method returning a non-nullable int must not reach its end without returning, and the analyzer cannot tell that the loop always returns. A throw ends the path and makes the broken precondition loud instead of returning a made-up value.
What does the voting pass return when there is no majority?
An arbitrary survivor: [1, 2, 3] returns 3. The vote is only correct when a majority exists. If the input might not have one, check nums.where((n) => n == candidate).length > nums.length ~/ 2 before returning.
FAQ for Scala
Why boundary and break instead of return inside the for?
A for over an array desugars to foreach with a closure, so return inside it would be a non-local return, which Scala 3 deprecates and warns about on every compile. boundary { ... break(n) ... } exits the block with n as its value, and the method body is that block.
Is groupMapReduce a good one-liner?
nums.groupMapReduce(identity)(_ => 1)(_ + _).maxBy(_._2)._1 builds an immutable map of counts and picks the largest. It reads well, but it boxes every value and always counts the whole array; the loop stops as soon as one count passes half.
Can the voting pass be written as a foldLeft?
Yes: nums.foldLeft((0, 0)) { case ((cand, cnt), n) => if (cnt == 0) (n, 1) else if (n == cand) (cand, cnt + 1) else (cand, cnt - 1) }._1. It avoids vars, but it allocates a tuple per element; the two vars are the faster and, here, clearer version.
Does nums.sorted change the input array?
No. sorted always returns a new collection. To sort in place, use scala.util.Sorting.quickSort(nums) or java.util.Arrays.sort(nums), both of which reorder the array they are given.
What does the voting pass return when there is no majority?
An arbitrary survivor: Array(1, 2, 3) returns 3. The vote is only correct when a majority exists. If the input might not have one, check nums.count(_ == candidate) > nums.length / 2 before returning.
Keep going
Maximum Depth of a Binary Tree16 / 40 · Trees · EasyTry Majority Element in Python (Majority Element in Python), TypeScript (Majority Element in TypeScript), Java (Majority Element in Java), Go (Majority Element in Go), C# (Majority Element in C#), C++ (Majority Element in C++), C (Majority Element in C), Kotlin (Majority Element in Kotlin), Rust (Majority Element in Rust), Swift (Majority Element in Swift), PHP (Majority Element in PHP), Ruby (Majority Element in Ruby), Dart (Majority Element in Dart) or Scala (Majority Element in Scala) instead.