Find Majority Element without extra space
Filed under ServiceNow
Free read 1 of 3Confirm if the majority element is guaranteed to exist.
The question
Given an array of positive integers, find the element that occurs more than n/2 times. The solution must run in O(n) time and use O(1) extra space.
Constraints
- Array length n >= 1
- Majority element always exists
Examples
- Input
- [3, 2, 3]
- Output
- 3
- Why
- 3 appears twice, which is > 3/2.
Approach
Confirm if the majority element is guaranteed to exist.
Maintain a candidate and a counter. Increment counter if current element matches candidate, else decrement. Reset candidate if counter hits zero.
Since the problem guarantees existence, the final candidate is the answer.
Solution
O(n) time, O(1) space
def majorityElement(nums):
cand, count = None, 0
for n in nums:
if count == 0: cand = n
count += (1 if n == cand else -1)
return cand
Tips
- What they are testing: Tests knowledge of the Boyer-Moore Voting Algorithm.
- Common mistake: Using a hash map to count frequencies, which violates the O(1) space constraint.
Related ServiceNow questions
Collected from public candidate posts and coding forums. Updated Nov 2026.