Grokking Data Structures & Algorithms for Coding Interviews

0% completed

​

Solution: Majority Element

Problem Statement

Given an array nums having an n elements, identify the element that appears the majority of the time, meaning more than n/2 times.

Examples

  1. Example 1:

    • Input: [1, 2, 2, 3, 2]
    • Expected Output: 2
    • Justification: Here, '2' appears 3 times in a 5-element array, making it the majority element.

  2. Example 2:

    • Input: [4, 4, 4, 4, 7, 4, 4]
    • Expected Output: 4
    • Justification: '4' is the majority element as it appears 5 out of 7 times.

  3. Example 3:

    • Input: [9, 9, 1, 1, 9, 1, 9, 9]
    • Expected Output: 9

.....

.....

.....

Like the course? Get enrolled and start learning!
L

Lee

· 2 years ago

There's a way less complex O(n) solution that iterates over the array once at the cost of having O(n) space.

Sahil Khurana

Sahil Khurana

· 8 months ago

You should also consider adding a solution using Moore's voting algorithm. Takes O(n) time and O(1) space.