### 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:**

Problem linkInput:[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 sizeSpace Complexity: O(1) Constant space

References

## No comments:

## Post a Comment

Thank your for your comment! Check out us at https://baozitraining.org/ if you need mock interviews!