Find majority element using Moore's Voting algorithm

Majority Element

A majority element in an array of size n is an element that appears more than n/2 times and hence there is at most one such element. For example, the majority element of the array {1, 2, 1, 1, 3} is 1.

Moore's voting algorithm

Moore's voting algorithm helps us find the majority element in an array using the following steps,

Initialize a result variable with value 0 and a count variable with value 1

Iterate through the array and increment the count variable if the element is same as result else decrement the count variable

If the count variable becomes 0, then reset the count variable with value 1 and set result variable as the array element.

Iterate through the array again and find the count of result variable from first iteration

If result variable count is less than n/2 then return -1 else return the result variable as Majority Element

Let arr = {2, 3, 4, 2, 2, 5}, n = 6

Code

import java.io.*;
import java.util.*;

class Test {

    // T(n) = Θ(n)
    // Aux space = Θ(1)

    public static int findMajority(int[] arr, int n) {
        int res=0, count=1;
        for(int i=0; i<n; i++) {
            if(arr[i] == res) {
                count++;
            } else {
                count--;
            }

            if(count == 0) {
                count = 1;
                res = arr[i];
            }
        }

        count = 0;
        for(int i=0; i<n; i++) {
            if(arr[i] == res) {
                count++;
            }
        }

        if(count < n/2) {
            return -1;
        }

        return res;
    }

    public static void main (String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        int[] arr = new int[n];
        for(int i=0; i<n; i++) {
            arr[i] = in.nextInt();
        }

        int res = findMajority(arr, n);
        System.out.println(res);
    }
}