Generated by Codex with GPT 5.6 Sol XHigh

Quick facts

Problem gist

Given an integer array of length n, return every value that appears more than floor(n / 3) times. The output can contain at most two values: three different values cannot each occur more than one third of the time because their combined count would exceed n.

A hash table can count every value in linear time, but it needs linear extra space in the worst case. Sorting exposes equal values in consecutive runs, but costs O(n log n) time. The optimal approach keeps only two possible winners while scanning the array, then verifies them in a second pass. It runs in O(n) time and uses O(1) auxiliary space.

Deriving the optimal solution

The key idea is to repeatedly cancel groups of three different values. Removing one occurrence of each of three distinct values cannot erase a true answer: a value that originally appeared more than n / 3 times still appears more than one third of the remaining array after such a cancellation.

There is no need to build those groups explicitly. Two candidate slots and two vote counts simulate the cancellations:

  1. If the current value matches a candidate, increase that candidate’s votes.
  2. Otherwise, if a candidate has no votes, place the current value in that slot.
  3. If the current value matches neither candidate and both slots have votes, decrease both vote counts. Together with the current value, that removes one virtual group of three different values.

After the first pass, every value that could occur more than floor(n / 3) times must be in one of the two slots. The candidates are only possibilities, however. An array such as [1, 2, 3] can leave candidates even though no value crosses the threshold, so a second pass must count the surviving candidates exactly.

Python solution

class Solution:
    def majorityElement(self, nums: list[int]) -> list[int]:
        """Return all values occurring more than floor(len(nums) / 3) times."""
        candidates = self._select_candidates(nums)
        occurrence_counts = self._count_candidates(nums, candidates)
        required_count = len(nums) // 3

        # Sorting at most two values makes the result deterministic without
        # changing the asymptotic time or auxiliary-space complexity.
        return sorted(
            candidate
            for candidate in candidates
            if occurrence_counts[candidate] > required_count
        )

    @staticmethod
    def _select_candidates(nums: list[int]) -> tuple[int, ...]:
        """Use two-slot Boyer-Moore voting to find every possible answer."""
        first_candidate: int | None = None
        second_candidate: int | None = None
        first_votes = 0
        second_votes = 0

        for value in nums:
            if value == first_candidate:
                first_votes += 1
            elif value == second_candidate:
                second_votes += 1
            elif first_votes == 0:
                first_candidate = value
                first_votes = 1
            elif second_votes == 0:
                second_candidate = value
                second_votes = 1
            else:
                # The current value and the two candidates are distinct.
                # Cancel one virtual occurrence of each.
                first_votes -= 1
                second_votes -= 1

        return tuple(
            candidate
            for candidate in (first_candidate, second_candidate)
            if candidate is not None
        )

    @staticmethod
    def _count_candidates(
        nums: list[int], candidates: tuple[int, ...]
    ) -> dict[int, int]:
        """Count only the constant-size candidate set in one verification pass."""
        occurrence_counts = {candidate: 0 for candidate in candidates}

        for value in nums:
            if value in occurrence_counts:
                occurrence_counts[value] += 1

        return occurrence_counts

The selection pass and verification pass each examine every element once, so the total time is O(n). The algorithm stores at most two candidates and their counts, so its auxiliary space is O(1). It does not modify the input.

Interview follow-ups

How would the solution change for elements occurring more than n / k times?

Use the Misra-Gries generalization of the same cancellation idea. Keep at most k - 1 candidate counters. When a value matches a candidate, increment it; when there is an empty slot, insert it; otherwise, decrement every counter. At most k - 1 values can exceed the threshold, and canceling k distinct values cannot remove a true answer.

A second pass must still verify the candidates. For fixed k, the running time is linear and the extra space is O(k). A direct implementation may spend O(k) time on a decrement step, making the worst-case time O(nk) when k is part of the input. More elaborate counter data structures can reduce that overhead, but they add complexity that is unnecessary for the original k = 3 problem.

Could the verification pass be removed?

Not while keeping both exactness and constant extra space for arbitrary input. Voting guarantees that every true answer survives as a candidate, but it does not preserve each candidate’s exact frequency. Candidates can change during the scan, so a counter attached to a late candidate does not include all of its earlier occurrences.

If one pass is mandatory, a full frequency table produces an exact result in O(n) time but may require O(n) space. With constant memory, the voting pass can provide only a small set of possible answers or approximate frequency guarantees unless the data can be replayed.

What if the threshold were more than n / 2?

Only one value can cross that threshold, so ordinary Boyer-Moore voting needs a single candidate and one vote count. Matching values add a vote and different values cancel a vote. If the problem guarantees that a majority exists, the surviving candidate can be returned immediately; otherwise, it must be verified with a second pass.

This version still takes O(n) time and O(1) auxiliary space, but the guarantee about existence determines whether verification is optional.

Could sorting be a reasonable alternative?

Yes. Sort the array, scan each run of equal values, and return the values whose run lengths exceed floor(n / 3). The reasoning is straightforward, and the approach may be attractive when the input is already sorted or sorting is required for later work.

The tradeoff is O(n log n) time instead of O(n). An in-place sort can use little extra memory, but it mutates the input; sorting a copy preserves the input at the cost of O(n) additional space.

How would this work for a stream that is too large to store in memory?

Run the candidate-selection pass while the stream arrives; it needs only two counters. For an exact result, replay the stream or read the source again to count the final candidates. The total work remains linear and memory remains constant.

If the stream cannot be replayed, there is a fundamental tradeoff. Keeping exact counts for every distinct value may require linear memory, while retaining only the two voting candidates cannot reconstruct occurrences seen before those candidates entered their slots. In that setting, the interviewer should clarify whether approximate heavy hitters are acceptable.

How could the computation be distributed across several machines?

Each worker can build a small Misra-Gries summary for its partition. Those weighted candidate summaries can then be merged by applying the same cancellation rule to their counts, producing a global set of at most two possible answers. A final distributed pass counts those candidates exactly across all partitions, and the coordinator sums the partial counts.

The total data scanned is still O(n), while communication is constant per worker for this threshold. The important caveat is the same as in the sequential algorithm: merged summaries identify candidates, not their exact global frequencies, so verification remains necessary.