Stealth Interview
  • Features
  • Pricing
  • Blog
  • Login
  • Sign up

How to Solve Majority Element on LeetCode

The Majority Element problem is a classic LeetCode question that tests your understanding of arrays, voting algorithms, and frequency counting.

Leetcode

Problem Statement

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊n / 2⌋ times. Assume that the array is non-empty and the majority element always exists.

Example:

Input: nums = [3,2,3] Output: 3

Why This Problem Matters for Interviews

This problem:

  • Introduces efficient frequency counting
  • Features the Boyer-Moore Voting Algorithm
  • Forms a basis for advanced frequency/majority logic

Approaches to Majority Element

1. Hash Map Frequency

Count occurrences of each element.

Time Complexity: O(n)
Space Complexity: O(n)

def majorityElement(nums: list[int]) -> int: counts = {} for n in nums: counts[n] = counts.get(n, 0) + 1 if counts[n] > len(nums) // 2: return n

2. Boyer-Moore Voting Algorithm (Optimal)

Track a candidate and its count.

Time Complexity: O(n)
Space Complexity: O(1)

def majorityElement(nums: list[int]) -> int: count, candidate = 0, None for n in nums: if count == 0: candidate = n count += (1 if n == candidate else -1) return candidate

Key Interview Talking Points

  • Why majority element must exist
  • Tradeoff between extra space and optimal in-place algorithms
  • Boyer-Moore's "voting" intuition
  • Edge cases (odd vs even n, all same, all different except one)

Big O Complexity Recap

ApproachTime ComplexitySpace Complexity
Hash MapO(n)O(n)
Boyer-MooreO(n)O(1)

Pro Interview Tips

  • Mention that result is always guaranteed (per problem statement).
  • Discuss how to extend to find elements > n/3 times.
  • Practice with test cases

Ace your next coding interview

We're here to help you ace your next coding interview.

Subscribe
Stealth Interview
© 2025 Stealth Interview ™All rights reserved.
Product
  • Blog
  • Pricing
Company
  • Terms of Service
  • Privacy Policy