Majority Element
Easy About 10 min Free, no account needed
Find the element that appears more than half the time.
The brief
Given an array of integers nums, return the majority element, the value
that appears more than n / 2 times.
- A majority element always exists in the input.
The obvious approach counts every element's occurrences with a nested scan, O(n2). The hidden test runs on 200,001 elements, where forty billion comparisons are far too slow. You will need to find it in O(n).
Starter code
using System;
public class Solution
{
// TODO: return the value appearing more than n/2 times (guaranteed to exist).
public int MajorityElement(int[] nums)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Hash maps and sets
- Trade memory for constant-time lookups, membership tests and frequency counts.
Related katas
- Contains Duplicate Easy Free Decide whether an array contains any repeated value.
- Count Distinct Letters Easy Free How many different letters appear? A 26-slot array already knows.
- Count Pairs With Difference K Easy Free Count the pairs of indices whose values differ by exactly k.
- Isomorphic Strings Easy Free Can one string be turned into the other by a consistent character substitution?