Majority Element-II
EbayThe problem
Given an **integer **array **nums **of size n. Return **all **elements which appear more than n/3 times in the array. The output can be returned in **any **order.
Input: nums = [1, 2, 1, 1, 3, 2] Output: [1] Explanation: Here, n / 3 = 6 / 3 = 2. Therefore the elements appearing 3 or more times is : [1]
Input: nums = [1, 2, 1, 1, 3, 2, 2] Output: [1, 2] Explanation: Here, n / 3 = 7 / 3 = 2. Therefore the elements appearing 3 or more times is : [1, 2]
Input: nums = [1, 2, 1, 1, 3, 2, 2, 3](Give the solution sorted in ascending order)
- n == nums.length.
- 2 <= n <= 105
- -104 <= nums[i] <= 104
cpp
class Solution {
public:
vector<int> majorityElementTwo(vector<int>& nums) {
}
};java
class Solution {
public List<Integer> majorityElementTwo(int[] nums) {
}
}python
class Solution:
def majorityElementTwo(self, nums):javascript
class Solution {
majorityElementTwo(nums) {
}
}csharp
public class Solution {
public List<int> MajorityElementTwo(List<int> nums) {
}
}go
func majorityElementTwo(nums []int) []int {
}Stuck? Show a way to structure it+
- 01Maintain two candidate values and two counters.
- 02Match an existing candidate, fill an empty slot, or decrement both counters.
- 03Make a second pass to count the surviving candidates.
- 04Return candidates whose actual count exceeds n/3.
Reference answer
Then expect these follow-ups
How does the method generalize to values occurring more than n/k times?
Tests: algorithm generalization
Why can there be at most two qualifying values?
Tests: counting proof
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question