Date: 2026-06-06
Time: 17:29
This file solves LeetCode 169 — Majority Element. It implements the Boyer-Moore Voting Algorithm to find the element that appears more than n/2 times in an array, and includes inline unit tests. Like every other problem directory in this repo, it's a self-contained solution + test pair.
majority_element(nums: list[int]) -> intThe sole function. Takes a non-empty list guaranteed to contain one element with a strict majority (> n/2 occurrences) and returns that element.
The algorithm uses two variables:
candidate — the current guess for the majority elementcount — a running "confidence score" for the candidateNine tests covering: basic LeetCode examples, single-element and uniform arrays, majority at different positions, negative numbers, and a dominant-majority case. No edge case for empty input, consistent with the problem's guarantee that nums is non-empty with a valid majority.
Boyer-Moore Voting Algorithm — This is the canonical O(n) time, O(1) space solution. The key insight: if you pair each occurrence of the majority element with a different element, at least one occurrence of the majority is left unpaired. The counter tracks this surplus.
The algorithm works in a single pass with no data structures — no hash maps, no sorting. This is the optimal approach for this problem.
Inline tests — The unittest import and test class live in the same file as the solution, a pattern used across this repo. The if _name == "main_" guard means tests run via python solution.py directly.
Imports: Only unittest from the standard library. No external dependencies.
Imported by: The "imported by" list in the prompt is misleading — those 400+ testsolution.py files aren't actually importing *this* file. They each import unittest independently. The majority-element/testsolution.py file likely imports majority_element from this module.
1. Initialize candidate = 0, count = 0
2. For each num in nums:
count == 0, adopt num as the new candidate (previous candidate was "cancelled out")num == candidate, increment count; otherwise decrement3. Return candidate
The algorithm never validates that the candidate actually has a majority — it relies on the precondition that one exists. If no majority element exists, the return value is undefined.
nums is non-empty and contains exactly one element appearing > n/2 times. Violating this makes the output meaningless.nums[0..i], the candidate is the majority of the "unmatched" suffix — every non-candidate seen so far has been paired with and cancelled against a candidate occurrence.None. Empty input would return 0 (the initial value of candidate) silently. Invalid input (no majority exists) returns an arbitrary element. This is fine for a LeetCode solution where constraints are guaranteed.
majority-element/plan.md — Planning doc that likely discusses algorithm choice (hash map vs. sorting vs. Boyer-Moore)majority-element/review.md — Code review notes that may cover the missing verification pass tradeoffcheck-if-a-number-is-majority-element-in-a-sorted-array/solution.py — Related problem that uses binary search on sorted input; contrasts with the unsorted-array approach hereboyer-moore-voting-generalization — The algorithm generalizes to finding elements appearing > n/k times using k-1 candidates (LeetCode 229 — Majority Element II)majority-element/test_solution.py:TestMajorityElement — The separate test file may contain additional or different test cases from the inline onesboyer-moore-no-verification — majority_element does not include a second pass to verify the candidate; it assumes the precondition (majority exists) holdsboyer-moore-constant-space — The algorithm uses exactly two scalar variables (candidate, count) regardless of input size — O(1) auxiliary spacesingle-pass-linear — The function iterates through nums exactly once, making it O(n) time with no early exitsempty-input-returns-zero — If called with an empty list, the function returns 0 without raising, because the loop body never executes and candidate retains its initial value