Majority Element

Big-O & the Python Toolkit, problem 3 of 7

Majority Element

Easy

LC #169

arraycountingboyer-moore

Not attempted yet

Given a list nums of length n, return the value that appears more than n / 2 times. Such a value is guaranteed to exist.

Can you do it in O(n) time and O(1) extra space?

Example 1

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

Example 2

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

Example 3

Input: nums = [8, 6, 6]
Output: 6

Constraints

  • 1 ≤ nums.length ≤ 10⁵
  • -10⁹ ≤ nums[i] ≤ 10⁹
  • A majority element always exists.

Python

Loading draft…

Test results

8 tests available

No results yet

Run tests your code against the examples; Submit runs the hidden tests too.

3 examples, 5 hidden

Run examples, then submit all tests.