beingsde
Sign In
Back to all DSA patterns
Array•Pattern: Boyer-Moore Voting•Medium

Find the majority element in an array (appears > n/2 times)

Problem Intuition & Objective

Identify the element that appears more than half the times in an array without using extra space.

Time ComplexityO(n)
Optimal
Space ComplexityO(1)
Memory Bounds
Optimal Algorithmic Approach

Boyer-Moore Voting: pick a candidate, sweep through incrementing count for a match and decrementing otherwise. When count hits 0, replace candidate.

Core Invariants & Edge Cases

  • Boyer-Moore Voting Algorithm reduces to O(1) space
  • Maintain a candidate and counter; increment/decrement as you scan
  • Verify the candidate in a second pass if not guaranteed to exist
Next Problem Product of array except self

System Design & Architecture Roadmap

Coding interviews are only 50% of the bar. Master High-Level Design, distributed systems, and Object-Oriented LLD.

60+ HLD QuestionsSharding, caching, and real-time distributed systems.27 LLD BlueprintsObject-oriented design patterns with class diagrams.SDE Quick ReferenceLatency numbers and database selection matrix.