How hard is LeetCode 169. Majority Element?

LeetCode 169. Majority Element is rated Easy on LeetCode.

What is the time complexity of LeetCode 169. Majority Element?

The Python solution on this page runs in O(n), where n is the length of the array nums.

What is the space complexity of LeetCode 169. Majority Element?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 169. Majority Element cover?

LeetCode 169. Majority Element is tagged Array, Hash Table, Divide and Conquer, Counting and Sorting on LeetCode.

Majority Element — LeetCode 169 Python Solution

EasyArrayHash TableDivide and ConquerCountingSorting

Problem: #169
Pattern: Sorting
Reading time: 2 min
Source: leetcode.com

The problem

Given an array nums of size n, return the majority element. The majority element is the element that appears more than ⌊n / 2⌋ times.

Example

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

Python solution

Python

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        cnt = m = 0
        for x in nums:
            if cnt == 0:
                m, cnt = x, 1
            else:
                cnt += 1 if m == x else -1
        return m

Complexity

Measure	Complexity
Time	O(n), where n is the length of the array nums
Space	O(1) auxiliary

Pattern: Sorting

Spend O(n log n) once to buy an ordering that makes the rest of the problem trivial. LeetCode 169. Majority Element is filed here because LeetCode tags it Sorting, which is the vocabulary this hub collects.

The sorting guide has the Python template for the pattern and the 401 LeetCode problems that use it.

On study lists

This problem is on Grind 75 and Top Interview 150.

Frequently asked questions

How hard is LeetCode 169. Majority Element?: LeetCode 169. Majority Element is rated Easy on LeetCode.
What is the time complexity of LeetCode 169. Majority Element?: The Python solution on this page runs in O(n), where n is the length of the array nums.
What is the space complexity of LeetCode 169. Majority Element?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 169. Majority Element cover?: LeetCode 169. Majority Element is tagged Array, Hash Table, Divide and Conquer, Counting and Sorting on LeetCode.