Majority Element II Python Solution with Tests

Tested Python solution for LeetCode 229 with 15 pytest cases. Generate a practice environment with lcpy.

LeetCode 229, Medium. Topics: Array, Hash Table, Sorting, Counting. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 15 parametrized pytest cases, and a playground notebook:

lcpy gen -n 229   # by problem number
lcpy gen -s majority_element_ii   # by problem name

​

Problem

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

​

Examples

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

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

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

​

Constraints

• 1 <= nums.length <= 5 * 10^4
• -10^9 <= nums[i] <= 10^9

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

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(n)
    # Space: O(1)
    def majority_element(self, nums: list[int]) -> list[int]:
        candidate1 = 0
        candidate2 = 0
        count1 = 0
        count2 = 0

        for num in nums:
            if candidate1 == num:
                count1 += 1
            elif candidate2 == num:
                count2 += 1
            elif count1 == 0:
                candidate1 = num
                count1 = 1
            elif count2 == 0:
                candidate2 = num
                count2 = 1
            else:
                count1 -= 1
                count2 -= 1

        threshold = len(nums) // 3
        result: list[int] = []
        if nums.count(candidate1) > threshold:
            result.append(candidate1)
        if candidate2 != candidate1 and nums.count(candidate2) > threshold:
            result.append(candidate2)

        return result

​

Complexity

Time	Space
O(n)	O(1)

​

Tags

NeetCode 250, NeetCode All.