Coding

Majority Element-II

Asked at

Ebay

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The 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) {

    }
}

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

There can be at most two values occurring more than n/3 times. Keep two candidate slots. For each value, increment its matching candidate count; otherwise assign it to an empty slot; otherwise decrement both counts. The decrement represents cancelling three distinct occurrences, which cannot eliminate every occurrence of a true majority-over-third value. The first pass only produces candidates, not proofs. Reset the counters and count both candidates in a second pass, then return those with count strictly greater than n/3. Time is O(n), space is O(1). Do not use >= n/3, and do not skip verification because arbitrary candidates can survive cancellation.

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

Hiring now

Ebay has 217 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Software Engineer - Cloud SRE
Bengaluru, India
Senior Software Engineer, Infrastructure
Dublin
Software Engineer – Cloud Platform
Dublin

Or practice this question first

Next question