Saturday, January 18, 2020

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]```

Video Tutorial

You can find the detailed video tutorial here

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