โ† ServiceNow questions

Find Majority Element without extra space

Filed under ServiceNow

Free read 1 of 3

Confirm 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

  1. Confirm if the majority element is guaranteed to exist.

Solution

O(n) time, O(1) space

Python
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.