Leetcode solution 229: Major Element II

Problem Statement 

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Note: The algorithm should run in linear time and in O(1) space.

Example 1:

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

Example 2:

Input: [1,1,1,3,3,2,2,2]
Output: [1,2]

 Problem link

Video Tutorial

You can find the detailed video tutorial here

• Youtube
• B站

Thought Process

It's a follow up question on Majority Element, given the hint, there should only be at most 2 elements that can satisfy the requirement (You cannot have 3 elements that all appear more than n/3 times). We can perform the voting algorithm on two potential candidates and later do an actual sum to eliminate the false positive (e.g., [1, 2, 1] would have both 1 and 2 as potential candidate, but 2 should not be included)

You can refer to Majority Element for a detailed explanation on the voting algorithm.

An extension could be changing n/3 to n/k. We just need extra arrays to store votes and candidates. It will take O(Nk) time complexity

Solutions

Voting implementation

Time Complexity: O(N) where N is the array size
Space Complexity: O(1) Constant space

References

• Leetcode discussion solution