LeetCode 229. Majority Element II

Description

https://leetcode.com/problems/majority-element-ii/

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

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

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

Explanation

Use a hashmap to store the counts of elements and find out the keys where appears more than ⌊ n/3 ⌋ times.

Python Solution

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        counter = {}
        
        
        for num in nums:
            counter[num] = counter.get(num, 0) + 1
            
        results = []
        
        for key, value in counter.items():
            if value > len(nums) // 3:
                results.append(key)
            
        return results
  • Time Complexity: O(N).
  • Space Complexity: O(N).

Leave a Reply

Your email address will not be published.