229 Majority Element II - Medium

Problem:

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Example 1:

Input: nums = [3,2,3] Output: [3]

Example 2:

Input: nums = [1] Output: [1]

Example 3:

Input: nums = [1,2] Output: [1,2]

Constraints:

• 1 <= nums.length <= 5 * 104
• -109 <= nums[i] <= 109

Follow up: Could you solve the problem in linear time and in O(1) space?

Problem Analysis:

• Very easy to come up with Time O(n) and Space O(n) solutions with Dictionary.
• Iterate through the list and construct a dictionary to get the count for each integer and return a list with integer with count more than n/3
• Note: logically, this array should be at most of length 2.

Solutions:

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        if len(nums) == 1:
            return nums        
        min_count = len(nums) // 3
        count = {}
        output = set()
        for n in nums:
            count[n] = count.get(n, 0) + 1
            if count[n] > min_count:
                output.add(n)

        return output

Alternative Solution

• Boyer-Moore Majority Voting Algorithm

Similar Questions

• 169-majority-element169 Majority Element - EasyProblem: Given an array nums of size n, return the majority element. The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array. Example 1: Input: nums = \[3,2,3\] Output: 3 Example 2: Input: nums = \[2,2,1,1,1,2,2\] Output: 2 Constraints: * n == nums.length * `1 int: count = 0 candidate = None for num in nums: if count == 0: candidate = num