Majority Element (Editorial)

Algorithm Analysis

Let $x$ be the majority element. We will start processing the input numbers. Each number equal to $x$ will be placed on a stack. Upon receiving a number not equal to $x$, we will remove one number from the stack. Thus, at the end of data processing, the top of the stack will contain the majority element.

First, we will clear the stack. When processing the next element $a$:

• if the stack is empty, then push(a);

• if the top of the stack contains the number $a$, then push(a);

• if the top of the stack contains a number not equal to $a$, then pop().

If at the end of processing all numbers the top of the stack contains the number $x$ (if the stack is empty, then there is no majority), it is necessary to check whether it is the majority element. To do this, count how many times the number $x$ appears in the initial set of numbers. If $x$ appears more than \frac{n}{2} times, then the answer is affirmative.

Since the stack contains one number at any time (possibly multiple times), we will model the stack with two variables:

• $maj$ – the number in the stack;

• $cnt$ – the number of times the number $maj$ is in the stack;

Example

Consider the first example. At the end of the algorithm, the stack contains 3. Let's check if it is the majority element. To do this, count how many times the number 3 appears in the initial array. The number 3 appears 4 times in an array of length n = 7. Since 4 > \frac{n}{2}, the number 3 is the majority element.

Algorithm Implementation

We will save the input sequence of numbers in an array m.

int m[110];

Declare the variables maj and cnt to model the stack:

• maj – the number in the stack;

• cnt – the number of times the number maj is in the stack;

int maj, cnt;

Read the input data.

scanf("%d",&n);
for(int i = 0; i < n; i++)
    scanf("%d",&m[i]);

Initially, set the stack to be empty.

maj = 0; cnt = 0;

Process the input numbers, simulating the operation of the stack.

for(int i = 0; i < n; i++) {
    if (cnt == 0) {maj = m[i]; cnt++;}
    else if (m[i] == maj) cnt++;
    else cnt--;
}

In the variable cnt, count how many times the number maj appears in the array m.

cnt = 0;
for(int i = 0; i < n; i++)
    if (m[i] == maj) cnt++;

If 2 * cnt > n, then the majority exists. Otherwise, no (res will be assigned -1).

if(2 * cnt > n) res = maj; else res = -1;

Print the answer.

printf("%d\n",res);

Java Implementation

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m[] = new int[n];
        for(int i = 0; i < n; i++)
            m[i] = sc.nextInt();
        int maj = 0, cnt = 0;
        for(int i = 0; i < n; i++) {
            if (cnt == 0) {maj = m[i]; cnt++;}
            else if (m[i] == maj) cnt++;
            else cnt--;
        }
        cnt = 0;
        int res;
        for(int i = 0; i < n; i++)
            if (m[i] == maj) cnt++;
        if(2 * cnt > n) res = maj; else res = -1;
        System.out.println(res);
    }
}

Python Implementation

n = int(input())
m = list(map(int, input().split()))

maj = 0
cnt = 0

for num in m:
    if cnt == 0:
        maj = num
        cnt += 1
    elif num == maj:
        cnt += 1
    else:
        cnt -= 1

cnt = 0
for num in m:
    if num == maj: cnt += 1

if 2 * cnt > n: res = maj
else: res = -1

print(res)