Majority Element

Try to solve the Majority Element problem.

We'll cover the following

Statement#

Given an array, nums, having nn integers, return the majority element. An element will be considered a majority element if it occurs more than ⌊n/2⌋⌊n / 2⌋ times in the array.

Note: It is safe to assume that the majority element always exists in the array.

Constraints

  • n==n == nums.length
  • 1≤n≤3∗1031\leq n\leq 3 * 10^3
  • −104≤−10^4 \leq nums[i] ≤104\leq10^4

Examples#

Created with Fabric.js 3.6.6

1 of 2

Created with Fabric.js 3.6.6

2 of 2

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Majority Element

1

What is the output if the following array is given as input?

nums = [1, 2, 2, 2, 1, 2, 1, 2, 3, 4, 1, 2, 1, 2, 2]

A)

1

B)

2

C)

3

D)

4

Question 1 of 20 attempted

Try it yourself#

Implement your solution in the following coding playground:

An optimal solution to this problem runs in O(n) time and takes O(n) space.

Python
usercode > main.py
Input #1
%0 node_01 1 node_11 2 node_21 1 node_31 1 node_41 1
Visualization for Input #1
Majority Element

You might want to go over the Knowing What To Track pattern again.

Solution: Contains Duplicate

Solution: Majority Element