Frequent Element Finder

You are ten minutes into a Google phone screen when the interviewer asks, "Given an integer array, find all elements that appear more than n/3 times. Can you do it in constant space?" The hash map approach springs to mind immediately, but constant space? That requires a different tool entirely. This problem, a favorite at Adobe, Google, and Atlassian, tests whether you can extend the classic Boyer-Moore Voting Algorithm beyond its textbook form.

TL;DR

Use the extended Boyer-Moore Voting Algorithm with two candidates and two counters. In the first pass, track two potential majority elements by adopting new candidates when a counter hits zero and decrementing both counters when the current element matches neither candidate. In the second pass, count actual occurrences of each candidate and return those exceeding the n/3 threshold. This runs in O(n) time and O(1) space.

Why This Problem Matters

The standard majority element problem (n/2 threshold) is a well-known warm-up. The n/3 variant raises the difficulty by requiring you to track two candidates simultaneously and understand why the verification pass is necessary. It also tests a key combinatorial insight: at most two elements can appear more than n/3 times in any array. Companies use this problem to gauge whether candidates can adapt known algorithms to new constraints rather than just memorizing solutions.

The Key Insight: Pigeonhole Principle

Before writing any code, there is an observation that simplifies the entire problem. If an element appears more than n/3 times, how many such elements can exist?

Suppose three distinct elements each appeared more than n/3 times. Their combined count would exceed n, but the array only has n elements. That is a contradiction. So at most two elements can satisfy the condition. This tells us we only need to track two candidates, not an arbitrary number.

Understanding the Problem

Given an integer array nums of length n, return all elements that appear more than n/3 times. The output order does not matter.

Example 1: nums = [3, 2, 3] returns [3] because 3 appears twice, and 2/3 rounds down to 0, so 2 > 0 qualifies 3.

Example 2: nums = [1, 1, 1, 3, 3, 2, 2, 2] returns [1, 2] because both appear 3 times and 8/3 rounds down to 2, so 3 > 2 qualifies both.

Example 3: nums = [1, 2, 3, 4, 5] returns [] because every element appears once and 5/3 rounds down to 1, so no element has a count greater than 1.

Constraints

• Array length is between 1 and 50,000
• Element values range from -1,000,000,000 to 1,000,000,000
• Target: O(n) time and O(1) space

Edge Cases to Consider

1. Single element: Always appears more than n/3 times (1/3 rounds to 0, count 1 > 0)
2. Two distinct elements like [1, 2]: Both qualify (2/3 rounds to 0)
3. All distinct: No element qualifies when n >= 3
4. Uniform array: The single repeated value qualifies

Approach 1: Hash Map (Straightforward)

The most direct approach is to count every element's frequency using a hash map, then collect elements whose count exceeds n/3.

public List<Integer> majorityElement(int[] nums) {
    Map<Integer, Integer> counts = new HashMap<>();
    List<Integer> result = new ArrayList<>();
    int threshold = nums.length / 3;

    for (int num : nums) {
        counts.put(num, counts.getOrDefault(num, 0) + 1);
    }

    for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
        if (entry.getValue() > threshold) {
            result.add(entry.getKey());
        }
    }

    return result;
}

This runs in O(n) time but uses O(n) space for the hash map. In an interview, this is a solid starting point. The interviewer will then ask: "Can you do it in O(1) space?"

Approach 2: Extended Boyer-Moore Voting Algorithm

The Boyer-Moore Voting Algorithm, originally designed for the n/2 majority element, can be extended to handle the n/3 threshold. Since at most two elements can exceed n/3, we maintain two candidate slots.

How the Algorithm Works

Pass 1 - Candidate Selection: Walk through the array while maintaining two candidates and their counts. For each element:

• If it matches candidate1, increment count1
• Otherwise if it matches candidate2, increment count2
• Otherwise if count1 is zero, adopt this element as candidate1
• Otherwise if count2 is zero, adopt this element as candidate2
• Otherwise, decrement both counts (cancellation)

Pass 2 - Verification: Reset both counts, scan the array again to count actual occurrences, and return candidates that exceed n/3.

Tracing Through [3, 2, 3]

Here is how the first pass processes each element:

After the first pass, candidate1 = 3 with count 2 and candidate2 = 2 with count 1. Now we verify:

The threshold is 3/3 = 1. Candidate 3 has count 2 > 1, so it qualifies. Candidate 2 has count 1, which equals the threshold but does not exceed it, so it is excluded. The result is [3].

Tracing Through [1, 1, 1, 3, 3, 2, 2, 2]

This longer example shows the cancellation mechanism at work:

After the first pass, candidate1 = 1 and candidate2 = 2. The second pass counts: 1 appears 3 times and 2 appears 3 times. The threshold is 8/3 = 2. Both 3 > 2, so the result is [1, 2].

Notice how the two occurrences of 2 that did not match either candidate caused both counters to decrement. This is the cancellation at work: three distinct values each lose one count. Elements that truly appear more than n/3 times have enough "weight" to survive these cancellations.

Why Cancellation Works

Think of it this way: every time the algorithm decrements both counters, it removes one occurrence from three different groups (candidate1, candidate2, and the current non-matching element). After all such cancellations, any element with more than n/3 occurrences must still have some count remaining, making it a candidate. The second pass then confirms this.

Implementation

Prefer a different language? Jump to solutions in other languages.

import java.util.*;

public class Solution {

  public List<Integer> majorityElement(int[] nums) {
    List<Integer> result = new ArrayList<>();
    if (nums == null || nums.length == 0) {
      return result;
    }

    int candidate1 = 0, candidate2 = 0, count1 = 0, count2 = 0;

    // Pass 1: Find up to two candidates
    for (int num : nums) {
      if (num == candidate1) {
        count1++;
      } else if (num == candidate2) {
        count2++;
      } else if (count1 == 0) {
        candidate1 = num;
        count1 = 1;
      } else if (count2 == 0) {
        candidate2 = num;
        count2 = 1;
      } else {
        count1--;
        count2--;
      }
    }

    // Pass 2: Verify candidates
    count1 = 0;
    count2 = 0;
    for (int num : nums) {
      if (num == candidate1) {
        count1++;
      } else if (num == candidate2) {
        count2++;
      }
    }

    int n = nums.length;
    if (count1 > n / 3) {
      result.add(candidate1);
    }
    if (count2 > n / 3) {
      result.add(candidate2);
    }

    return result;
  }
}

A few things to note about this implementation:

1. Initialization: candidate1 and candidate2 start at 0 with counts at 0. The order of conditions matters. Checking num == candidate1 before count1 == 0 ensures an existing candidate is incremented rather than replaced.

2. The else if chain: Each element triggers exactly one branch. An element cannot be both candidates simultaneously because the else if on candidate2 only fires when the element does not match candidate1.

3. Integer division: Java's n / 3 performs floor division naturally, matching the problem's n/3 specification.

Complexity Analysis

Time Complexity: O(n)

Two sequential passes over the array, each visiting every element once. The first pass performs at most 5 comparisons per element (the if/else if chain). The second pass performs at most 2 comparisons. Total work per element is bounded by a constant, giving O(n) overall.

Space Complexity: O(1)

Four integer variables (two candidates, two counts) plus the result list. The result list contains at most 2 elements, so it is bounded by a constant. No auxiliary data structures scale with the input.

Alternative Approaches

The Boyer-Moore approach is the only one achieving O(n) time with O(1) space. Sorting-based approaches lose on time complexity. Hash maps lose on space.

Common Pitfalls

1. Skipping the verification pass: The first pass produces candidates, not guaranteed answers. Without verification, arrays like [1, 2, 3, 4, 5] would incorrectly return two elements.

2. Using >= instead of >: The problem specifies more than n/3, not at least n/3. Using count >= n / 3 will produce wrong answers for cases like [3, 2, 3] where element 2 has count 1 equal to 3/3 = 1.

3. Condition ordering in the first pass: Checking count1 == 0 before num == candidate1 can replace a valid candidate prematurely. Always check for matches first, then check for empty slots.

4. Forgetting that both candidates can be equal initially: When both candidates initialize to 0 and the array contains 0, the algorithm still works because the count checks handle this correctly. In languages where candidates initialize to null, this is not an issue.

Interview Tips

When presenting this solution in an interview:

1. Start with the pigeonhole argument. Mentioning that at most two elements can exceed n/3 shows you understand the mathematical structure before coding.

2. Present the hash map solution first. Demonstrate you can solve the problem, then optimize. Jumping straight to Boyer-Moore without showing the simpler approach can seem like memorization.

3. Trace through a short example. Use [3, 2, 3] to show both passes. It is small enough to fit on a whiteboard but covers all branches.

4. Explain why verification is needed. This is the most common follow-up question. Prepare an example where the first pass produces a false candidate.

5. Mention the generalization. For n/k threshold, you need k-1 candidates. This shows deeper understanding and opens discussion about stream processing applications.

Key Takeaways

• At most two elements can appear more than n/3 times in any array. This pigeonhole observation is the foundation for the constant-space solution.
• The extended Boyer-Moore Voting Algorithm uses two candidates and two counters, running in two passes: candidate selection followed by verification.
• The cancellation step (decrementing both counters) is what eliminates non-majority elements. Each cancellation neutralizes one occurrence from three different values.
• Always verify candidates with a second pass. The first pass finds "survivors" of cancellation, not confirmed majority elements.
• In interviews, present the O(n) space hash map first, then optimize to O(1) space Boyer-Moore. This progression demonstrates problem-solving ability, not just pattern matching.

Solutions in Other Languages

Python

from typing import List

class Solution:
    def majority_element(self, nums: List[int]) -> List[int]:
        if not nums:
            return []

        candidate1, candidate2, count1, count2 = None, None, 0, 0

        for num in nums:
            if candidate1 == num:
                count1 += 1
            elif candidate2 == num:
                count2 += 1
            elif count1 == 0:
                candidate1, count1 = num, 1
            elif count2 == 0:
                candidate2, count2 = num, 1
            else:
                count1 -= 1
                count2 -= 1

        result = []
        count1, count2 = 0, 0

        for num in nums:
            if num == candidate1:
                count1 += 1
            elif num == candidate2:
                count2 += 1

        n = len(nums)
        if count1 > n // 3:
            result.append(candidate1)
        if count2 > n // 3:
            result.append(candidate2)

        return result

Python's tuple unpacking with candidate1, count1 = num, 1 makes the adoption step concise. Using None for initial candidates avoids the zero-initialization pitfall, since None will never accidentally match an integer in the array.

JavaScript

class Solution {
  majorityElement(nums) {
    const n = nums.length;
    if (n === 0) return [];

    let candidate1 = null, candidate2 = null, count1 = 0, count2 = 0;

    for (let num of nums) {
      if (candidate1 !== null && num === candidate1) {
        count1++;
      } else if (candidate2 !== null && num === candidate2) {
        count2++;
      } else if (count1 === 0) {
        candidate1 = num;
        count1 = 1;
      } else if (count2 === 0) {
        candidate2 = num;
        count2 = 1;
      } else {
        count1--;
        count2--;
      }
    }

    count1 = 0;
    count2 = 0;
    for (let num of nums) {
      if (num === candidate1) count1++;
      else if (num === candidate2) count2++;
    }

    const result = [];
    if (count1 > Math.floor(n / 3)) result.push(candidate1);
    if (count2 > Math.floor(n / 3)) result.push(candidate2);

    return result;
  }
}

The JavaScript version adds explicit null checks before comparing candidates. This prevents null === num from accidentally matching when num is 0. Math.floor(n / 3) handles the floor division since JavaScript uses floating-point division by default.

TypeScript

class Solution {
    majorityElement(nums: number[]): number[] {
        const n = nums.length;
        if (n === 0) return [];

        let candidate1: number | null = null, candidate2: number | null = null;
        let count1 = 0, count2 = 0;

        for (const num of nums) {
            if (candidate1 !== null && num === candidate1) {
                count1++;
            } else if (candidate2 !== null && num === candidate2) {
                count2++;
            } else if (count1 === 0) {
                candidate1 = num;
                count1 = 1;
            } else if (count2 === 0) {
                candidate2 = num;
                count2 = 1;
            } else {
                count1--;
                count2--;
            }
        }

        count1 = 0;
        count2 = 0;
        for (const num of nums) {
            if (num === candidate1) count1++;
            else if (num === candidate2) count2++;
        }

        const result: number[] = [];
        if (count1 > Math.floor(n / 3)) result.push(candidate1!);
        if (count2 > Math.floor(n / 3)) result.push(candidate2!);

        return result;
    }
}

The TypeScript version uses number | null union types for candidates. The non-null assertion candidate1! when pushing to the result is safe because the count check guarantees the candidate was assigned.

C++

#include <vector>

class Solution {
public:
  std::vector<int> majorityElement(std::vector<int> &nums) {
    int n = nums.size();
    if (n == 0) return {};

    int candidate1 = 0, candidate2 = 1, count1 = 0, count2 = 0;

    for (int num : nums) {
      if (num == candidate1) {
        count1++;
      } else if (num == candidate2) {
        count2++;
      } else if (count1 == 0) {
        candidate1 = num;
        count1 = 1;
      } else if (count2 == 0) {
        candidate2 = num;
        count2 = 1;
      } else {
        count1--;
        count2--;
      }
    }

    count1 = count2 = 0;
    for (int num : nums) {
      if (num == candidate1) count1++;
      else if (num == candidate2) count2++;
    }

    std::vector<int> result;
    if (count1 > n / 3) result.push_back(candidate1);
    if (count2 > n / 3) result.push_back(candidate2);

    return result;
  }
};

The C++ version initializes candidate1 and candidate2 to different values (0 and 1) to prevent them from starting equal. Since C++ integers cannot be null, this is the standard workaround. The count-based logic ensures incorrect initial values are replaced before being used.

Go

package solution

func (s *Solution) MajorityElement(nums []int) []int {
    if len(nums) == 0 {
        return []int{}
    }

    var candidate1, candidate2, count1, count2 int

    for _, num := range nums {
        if num == candidate1 {
            count1++
        } else if num == candidate2 {
            count2++
        } else if count1 == 0 {
            candidate1, count1 = num, 1
        } else if count2 == 0 {
            candidate2, count2 = num, 1
        } else {
            count1--
            count2--
        }
    }

    count1, count2 = 0, 0
    for _, num := range nums {
        if num == candidate1 {
            count1++
        } else if num == candidate2 {
            count2++
        }
    }

    result := []int{}
    n := len(nums)
    if count1 > n/3 {
        result = append(result, candidate1)
    }
    if count2 > n/3 {
        result = append(result, candidate2)
    }

    return result
}

Go's zero-value initialization means both candidates start at 0 and both counts at 0. The range loop and multiple return values with candidate1, count1 = num, 1 keep the code idiomatic.

Scala

class Solution {
  def majorityElement(nums: Array[Int]): List[Int] = {
    if (nums.isEmpty) return List()

    var candidate1: Option[Int] = None
    var candidate2: Option[Int] = None
    var count1 = 0
    var count2 = 0

    for (num <- nums) {
      if (candidate1.contains(num)) {
        count1 += 1
      } else if (candidate2.contains(num)) {
        count2 += 1
      } else if (count1 == 0) {
        candidate1 = Some(num)
        count1 = 1
      } else if (count2 == 0) {
        candidate2 = Some(num)
        count2 = 1
      } else {
        count1 -= 1
        count2 -= 1
      }
    }

    count1 = 0
    count2 = 0
    for (num <- nums) {
      if (candidate1.contains(num)) count1 += 1
      else if (candidate2.contains(num)) count2 += 1
    }

    val result = scala.collection.mutable.ListBuffer[Int]()
    val n = nums.length
    if (count1 > n / 3) result += candidate1.get
    if (count2 > n / 3) result += candidate2.get

    result.toList
  }
}

Scala uses Option[Int] for candidates, making the null-safety explicit. The contains method on Option handles the check-and-match in a single call.

Ruby

class Solution
  def majority_element(nums)
    result = []
    return result if nums.nil? || nums.empty?

    candidate1, candidate2, count1, count2 = 0, 0, 0, 0

    nums.each do |num|
      if num == candidate1
        count1 += 1
      elsif num == candidate2
        count2 += 1
      elsif count1 == 0
        candidate1 = num
        count1 = 1
      elsif count2 == 0
        candidate2 = num
        count2 = 1
      else
        count1 -= 1
        count2 -= 1
      end
    end

    count1, count2 = 0, 0

    nums.each do |num|
      if num == candidate1
        count1 += 1
      elsif num == candidate2
        count2 += 1
      end
    end

    threshold = nums.length / 3
    result << candidate1 if count1 > threshold
    result << candidate2 if count2 > threshold

    result
  end
end

Ruby's each block and inline conditionals (result << candidate1 if count1 > threshold) keep the code compact. Integer division in Ruby naturally floors, matching the problem specification.

Rust

pub struct Solution;

impl Solution {
    pub fn majority_element(&self, nums: Vec<i32>) -> Vec<i32> {
        let mut result: Vec<i32> = Vec::new();
        if nums.is_empty() {
            return result;
        }

        let (mut candidate1, mut candidate2) = (0_i32, 1_i32);
        let (mut count1, mut count2) = (0_usize, 0_usize);

        for &num in &nums {
            if num == candidate1 {
                count1 += 1;
            } else if num == candidate2 {
                count2 += 1;
            } else if count1 == 0 {
                candidate1 = num;
                count1 = 1;
            } else if count2 == 0 {
                candidate2 = num;
                count2 = 1;
            } else {
                count1 -= 1;
                count2 -= 1;
            }
        }

        count1 = 0;
        count2 = 0;

        for &num in &nums {
            if num == candidate1 {
                count1 += 1;
            } else if num == candidate2 {
                count2 += 1;
            }
        }

        let threshold = nums.len() / 3;
        if count1 > threshold {
            result.push(candidate1);
        }
        if count2 > threshold {
            result.push(candidate2);
        }

        result
    }
}

Rust uses &num pattern matching in the loop to borrow and dereference in one step. The 0_i32 and 1_i32 type suffixes make the initial distinct values explicit. Using usize for counts matches Rust's len() return type naturally.

Swift

import Foundation

class Solution {
    func majorityElement(_ nums: [Int]) -> [Int] {
        var result = [Int]()
        if nums.isEmpty {
            return result
        }

        var candidate1 = 0, candidate2 = 0
        var count1 = 0, count2 = 0

        for num in nums {
            if num == candidate1 {
                count1 += 1
            } else if num == candidate2 {
                count2 += 1
            } else if count1 == 0 {
                candidate1 = num
                count1 = 1
            } else if count2 == 0 {
                candidate2 = num
                count2 = 1
            } else {
                count1 -= 1
                count2 -= 1
            }
        }

        count1 = 0
        count2 = 0

        for num in nums {
            if num == candidate1 {
                count1 += 1
            } else if num == candidate2 {
                count2 += 1
            }
        }

        let n = nums.count
        if count1 > n / 3 {
            result.append(candidate1)
        }
        if count2 > n / 3 {
            result.append(candidate2)
        }

        return result
    }
}

Swift's nums.count provides the array length, and integer division with / floors by default.

Kotlin

class Solution {
  fun majorityElement(nums: IntArray): List<Int> {
    val result = mutableListOf<Int>()
    if (nums.isEmpty()) {
      return result
    }

    var candidate1 = 0
    var candidate2 = 0
    var count1 = 0
    var count2 = 0

    for (num in nums) {
      if (num == candidate1) {
        count1++
      } else if (num == candidate2) {
        count2++
      } else if (count1 == 0) {
        candidate1 = num
        count1 = 1
      } else if (count2 == 0) {
        candidate2 = num
        count2 = 1
      } else {
        count1--
        count2--
      }
    }

    count1 = 0
    count2 = 0

    for (num in nums) {
      if (num == candidate1) {
        count1++
      } else if (num == candidate2) {
        count2++
      }
    }

    val n = nums.size
    if (count1 > n / 3) {
      result.add(candidate1)
    }
    if (count2 > n / 3) {
      result.add(candidate2)
    }

    return result
  }
}

Kotlin uses IntArray for primitive int arrays (avoiding boxing overhead) and mutableListOf<Int>() for the result.

C#

using System.Collections.Generic;

public class Solution {
    public List<int> MajorityElement(int[] nums) {
        var result = new List<int>();
        if (nums == null || nums.Length == 0) {
            return result;
        }

        int candidate1 = 0, candidate2 = 0, count1 = 0, count2 = 0;

        foreach (var num in nums) {
            if (num == candidate1) {
                count1++;
            } else if (num == candidate2) {
                count2++;
            } else if (count1 == 0) {
                candidate1 = num;
                count1 = 1;
            } else if (count2 == 0) {
                candidate2 = num;
                count2 = 1;
            } else {
                count1--;
                count2--;
            }
        }

        count1 = 0;
        count2 = 0;

        foreach (var num in nums) {
            if (num == candidate1) {
                count1++;
            } else if (num == candidate2) {
                count2++;
            }
        }

        var n = nums.Length;
        if (count1 > n / 3) {
            result.Add(candidate1);
        }
        if (count2 > n / 3) {
            result.Add(candidate2);
        }

        return result;
    }
}

C# follows the same structure with foreach iteration and List<int> for the result. Integer division in C# truncates toward zero, matching the floor behavior for positive lengths.

Dart

class Solution {
  List<int> majorityElement(List<int> nums) {
    List<int> result = [];
    if (nums.isEmpty) {
      return result;
    }

    int candidate1 = 0, candidate2 = 0, count1 = 0, count2 = 0;

    for (int num in nums) {
      if (num == candidate1) {
        count1++;
      } else if (num == candidate2) {
        count2++;
      } else if (count1 == 0) {
        candidate1 = num;
        count1 = 1;
      } else if (count2 == 0) {
        candidate2 = num;
        count2 = 1;
      } else {
        count1--;
        count2--;
      }
    }

    count1 = 0;
    count2 = 0;

    for (int num in nums) {
      if (num == candidate1) {
        count1++;
      } else if (num == candidate2) {
        count2++;
      }
    }

    int n = nums.length;
    if (count1 > n ~/ 3) {
      result.add(candidate1);
    }
    if (count2 > n ~/ 3) {
      result.add(candidate2);
    }

    return result;
  }
}

Dart uses the ~/ operator for integer division (truncating division), which is distinct from / that returns a double.

PHP

class Solution {
    public function majorityElement(array $nums): array {
        $result = [];
        if (empty($nums)) {
            return $result;
        }

        $candidate1 = 0;
        $candidate2 = 0;
        $count1 = 0;
        $count2 = 0;

        foreach ($nums as $num) {
            if ($num === $candidate1) {
                $count1++;
            } elseif ($num === $candidate2) {
                $count2++;
            } elseif ($count1 === 0) {
                $candidate1 = $num;
                $count1 = 1;
            } elseif ($count2 === 0) {
                $candidate2 = $num;
                $count2 = 1;
            } else {
                $count1--;
                $count2--;
            }
        }

        $count1 = 0;
        $count2 = 0;

        foreach ($nums as $num) {
            if ($num === $candidate1) {
                $count1++;
            } elseif ($num === $candidate2) {
                $count2++;
            }
        }

        $n = count($nums);
        if ($count1 > intdiv($n, 3)) {
            $result[] = $candidate1;
        }
        if ($count2 > intdiv($n, 3)) {
            $result[] = $candidate2;
        }

        return $result;
    }
}

PHP uses strict comparison (===) to avoid type coercion surprises and intdiv() for integer division.

Practice Makes Perfect

Once you are comfortable with the n/3 threshold, try these related problems to build on the same ideas:

• Majority Element (n/2 threshold) - the simpler single-candidate version
• Top K Frequent Elements - frequency counting with different selection criteria
• Single Number - another problem where cancellation-style thinking applies

This problem and thousands of others are available on Firecode, where over 50,000 users have prepared for technical interviews and landed roles at top tech companies. Whether you are targeting Adobe, Google, or any company that values algorithmic thinking, building fluency with voting algorithms will serve you well.

Happy coding!