DSA problem
Majority Element II
Given an integer array nums of size n, return all the elements that appear more than ⌊n / 3⌋ times.
There can be at most two such elements, because any element appearing more than ⌊n / 3⌋ times accounts for over a third of the array, and three such elements would exceed the array size.
Follow-up: Could you solve the problem in linear time O(n) and in O(1) space?
Examples
Example 1
Input:
nums = [3,2,3]Output:
[3]Explanation: n = 3 so the threshold is ⌊3/3⌋ = 1. The value 3 appears twice, which is more than 1, so it qualifies.
Example 2
Input:
nums = [1]Output:
[1]Explanation: n = 1 so the threshold is 0. The value 1 appears once, which is more than 0.
Example 3
Input:
nums = [1,2]Output:
[1,2]Explanation: n = 2 so the threshold is 0. Both 1 and 2 appear once, which exceeds 0, so both qualify.
Constraints
- 1 <= nums.length <= 5 * 10^4
- -10^9 <= nums[i] <= 10^9
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.