Given an array nums of size n, return its majority element: the value that appears more than n / 2 times. You can assume such an element always exists.
Example 1
Input: nums = [3,2,3]
Output: 3
3 appears 2 times, which is more than
3 / 2.Example 2
Input: nums = [2,2,1,1,1,2,2]
Output: 2
Constraints
- 1 <= nums.length <= 5 * 10^4
- -10^9 <= nums[i] <= 10^9
- A majority element always exists
Hints
Frequently asked at: Amazon, Google, Microsoft, Adobe, TCS
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Counting every value with a hash map is O(n) time but O(n) space, and sorting then taking the middle is O(n log n). The Boyer-Moore voting idea: if we cancel one copy of the majority against one copy of any other value, the majority still survives because it has more copies than everything else combined. So we keep one candidate and a count; when the count drops to zero we pick the current number as the new candidate.
Algorithm
- Set
count = 0andcandidateto anything. - For each
x: ifcount == 0, setcandidate = x. - Add 1 to
countifx == candidate, otherwise subtract 1. - Return
candidate.
Time:
O(n)Space: O(1)Interview tip: If the problem does not promise a majority exists, you need a second pass to count the candidate and confirm it really appears more than
n / 2 times.class Solution: def majorityElement(self, nums: List[int]) -> int: candidate, count = None, 0 for x in nums: if count == 0: candidate = x # start a new candidate count += 1 if x == candidate else -1 return candidateCtrl + Enter runs the examples