Majority Element II

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?

SOLUTION:

# class Solution:
#     def majorityElement(self, nums: List[int]) -> List[int]:
#         k = len(nums) // 3
#         ctr = {}
#         for num in nums:
#             ctr[num] = ctr.get(num, 0) + 1
#         return [num for num, count in ctr.items() if count > k]

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        nums.sort()
        n = len(nums)
        elms = set(nums)
        op = []
        for x in elms:
            ctr = bisect.bisect_right(nums, x) - bisect.bisect_left(nums, x)
            if ctr > n // 3:
                op.append(x)
        return op