Majority Element

Given an array arr[] of size n, find the element that appears more than ⌊n/2⌋ times. If no such element exists, return -1.

Examples:

Input: arr[] = [1, 1, 2, 1, 3, 5, 1]
Output: 1
Explanation: Element 1 appears 4 times. Since ⌊7/2⌋ = 3, and 4 > 3, it is the majority element.

Input: arr[] = [7]
Output: 7
Explanation: Element 7 appears once. Since ⌊1/2⌋ = 0, and 1 > 0, it is the majority element.

Input: arr[] = [2, 13]
Output: -1
Explanation: No element appears more than ⌊2/2⌋ = 1 time, so there is no majority element.

[Naive Approach] Using Two Nested Loops - O(n^2) Time and O(1) Space

The idea is to use nested loops to count frequencies. The outer loop selects each element as a candidate, and the inner loop counts how many times it appears. If any element appears more than n / 2 times, it is the majority element.

#include <iostream>
#include <vector>
using namespace std;

int majorityElement(vector<int>& arr) {
    int n = arr.size();  

    // Loop to consider each element as a 
    // candidate for majority
    for (int i = 0; i < n; i++) {
        int count = 0; 

        // Inner loop to count the frequency of arr[i]
        for (int j = 0; j < n; j++) {
            if (arr[i] == arr[j]) {
                count++;
            }
        }

        // Check if count of arr[i] is more 
        // than half the size of the array
        if (count > n / 2) {
            return arr[i]; 
        }
    }

    // If no majority element found, return -1
    return -1;
}

int main() {
    vector<int> arr = {1, 1, 2, 1, 3, 5, 1};
    
    cout << majorityElement(arr) << endl;

    return 0;
}

#include <stdio.h>

int majorityElement(int arr[], int n) {
    
    // Loop to consider each element as 
    // a candidate for majority
    for (int i = 0; i < n; i++) {
        int count = 0; 

        // Inner loop to count the frequency of arr[i]
        for (int j = 0; j < n; j++) {
            if (arr[i] == arr[j]) {
                count++;
            }
        }

        // Check if count of arr[i] is more
        // than half the size of the array
        if (count > n / 2) {
            return arr[i]; 
        }
    }

    // If no majority element found, return -1
    return -1;
}

int main() {
    int arr[] = {1, 1, 2, 1, 3, 5, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("%d\n", majorityElement(arr, n));

    return 0;
}

class GfG {

    static int majorityElement(int[] arr) {
        int n = arr.length; 

        // Loop to consider each element as 
        // a candidate for majority
        for (int i = 0; i < n; i++) {
            int count = 0;

            // Inner loop to count the frequency of arr[i]
            for (int j = 0; j < n; j++) {
                if (arr[i] == arr[j]) {
                    count++;
                }
            }

            // Check if count of arr[i] is more
            // than half the size of the array
            if (count > n / 2) {
                return arr[i];
            }
        }

        // If no majority element found, return -1
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 1, 2, 1, 3, 5, 1};

        System.out.println(majorityElement(arr));
    }
}

def majorityElement(arr):

    n = len(arr)  

    # Loop to consider each element as
    # a candidate for majority
    for i in range(n):
        count = 0

        # Inner loop to count the frequency of arr[i]
        for j in range(n):
            if arr[i] == arr[j]:
                count += 1

        # Check if count of arr[i] is more 
        # than half the size of the array
        if count > n // 2:
            return arr[i]

    # If no majority element found, return -1
    return -1

if __name__ == "__main__":
	arr = [1, 1, 2, 1, 3, 5, 1]
	print(majorityElement(arr))

using System;

class GfG {

    static int majorityElement(int[] arr) {
        int n = arr.Length; 

        // Loop to consider each element
        // as a candidate for majority
        for (int i = 0; i < n; i++) {
            int count = 0;

            // Inner loop to count the frequency of arr[i]
            for (int j = 0; j < n; j++) {
                if (arr[i] == arr[j]) {
                    count++;
                }
            }

            // Check if count of arr[i] is more 
            // than half the size of the array
            if (count > n / 2) {
                return arr[i];
            }
        }

        // If no majority element found, return -1
        return -1;
    }

    static void Main(string[] args) {
        int[] arr = { 1, 1, 2, 1, 3, 5, 1 };
        Console.WriteLine(majorityElement(arr));
    }
}

function majorityElement(arr) {

    let n = arr.length;  

    // Loop to consider each element as
    // a candidate for majority
    for (let i = 0; i < n; i++) {
        let count = 0;

        // Inner loop to count the frequency of arr[i]
        for (let j = 0; j < n; j++) {
            if (arr[i] === arr[j]) {
                count++;
            }
        }

        // Check if count of arr[i] is more than
        // half the size of the array
        if (count > n / 2) {
            return arr[i];
        }
    }

    // If no majority element found, return -1
    return -1;
}

// Driver Code 
let arr = [1, 1, 2, 1, 3, 5, 1];
console.log(majorityElement(arr));

1

Note : We can also solve this problem by sorting and then doing a single traversal. This would solve the problem in O(n Log n) time. Another approach can be to count frequencies using hashing. This would work in linear time, but requires O(n) extra space. The below approach solves in linear time and constant extra space.

[Expected Approach] Using Moore's Voting Algorithm - O(n) Time and O(1) Space

The algorithm is based on the idea that if an element occurs more than n/2 times, then all the remaining elements together must occur less than n/2 times.

While traversing the array, we maintain a candidate and a vote count:

• If the current element matches the candidate, we increment the vote count.
• If it does not match, we decrement the vote count.
• When the vote count becomes 0, it means the current candidate cannot be the majority element, so we select a new candidate.

By the end of the first traversal, the remaining candidate is the potential majority element (if there is a majority element, then this elements has to be the one). A second traversal is required to verify whether it actually appears more than n/2 times.

There are mainly twos steps

Step 1: Find a Candidate

Initialize candidate = -1 and count = 0.

Traverse the array:

• If count == 0, set candidate = arr[i] and count = 1.
• If arr[i] == candidate, increment count.
• Otherwise, decrement count.

Step 2: Verify the Candidate

• Count the occurrences of the candidate in the array.
• If the count is greater than n/2, return the candidate.
• Otherwise, return -1.

#include <iostream>
#include <vector>
using namespace std;

int majorityElement(vector<int>& arr) {

    int n = arr.size();
    
    int candidate = -1;
    int count = 0;

    // Find a candidate
    for (int num : arr) {
       
        if (count == 0) {
            candidate = num;
            count = 1;
        } 
        else if (num == candidate) {
            count++;
        } 
        else {
            count--;
        }
    }

    // Validate the candidate
    count = 0;
    for (int num : arr) {
        if (num == candidate) {
            count++;
        }
    }

    // If count is greater than n / 2, return the
    // candidate; otherwise, return -1
    if (count > n / 2) {
        return candidate;
    } else {
        return -1;
    }
}

int main() {
    vector<int> arr = {1, 1, 2, 1, 3, 5, 1};
    cout << majorityElement(arr) << endl;
    return 0;
}

#include <stdio.h>

int majorityElement(int arr[], int n) {

    int candidate = -1;
    int count = 0;

    // Find a candidate
    for (int i = 0; i < n; i++) {

        if (count == 0) {
            candidate = arr[i];
            count = 1;
        }
        else if (arr[i] == candidate) {
            count++;
        }
        else {
            count--;
        }
    }

    // Validate the candidate
    count = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] == candidate) {
            count++;
        }
    }

  	// If count is greater than n / 2, return
  	// the candidate; otherwise, return -1
    if (count > n / 2) {
        return candidate;
    } else {
        return -1;
    }
}

int main() {
    int arr[] = {1, 1, 2, 1, 3, 5, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("%d\n", majorityElement(arr, n));
    return 0;
}

class GfG {
    
    static int majorityElement(int[] arr) {
    
        int n = arr.length;
        int candidate = -1;
        int count = 0;

        // Find a candidate
        for (int num : arr) {
            if (count == 0) {
                candidate = num;
                count = 1;
            } 
            else if (num == candidate) {
                count++;
            }
            else {
                count--;
            }
        }

        // Validate the candidate
        count = 0;
        for (int num : arr) {
            if (num == candidate) {
                count++;
            }
        }
	
      	// If count is greater than n / 2, return 
      	// the candidate; otherwise, return -1
        if (count > n / 2) {
            return candidate;
        } else {
            return -1;
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 1, 2, 1, 3, 5, 1};
        System.out.println(majorityElement(arr));
    }
}

def majorityElement(arr):

    n = len(arr)
    candidate = -1
    count = 0

    # Find a candidate
    for num in arr:
        if count == 0:
            candidate = num
            count = 1
        elif num == candidate:
            count += 1
        else:
            count -= 1

    # Validate the candidate
    count = 0
    for num in arr:
        if num == candidate:
            count += 1

    # If count is greater than n / 2, return 
    # the candidate; otherwise, return -1
    if count > n // 2:
        return candidate
    else:
        return -1

if __name__ == "__main__":
    
    arr = [1, 1, 2, 1, 3, 5, 1]
    print(majorityElement(arr))

using System;

class GfG {

     static int majorityElement(int[] arr) {

        int n = arr.Length;
        int candidate = -1;
        int count = 0;

        // Find a candidate
        foreach (int num in arr) {
            if (count == 0) {
                candidate = num;
                count = 1;
            } else if (num == candidate) {
                count++;
            } else {
                count--;
            }
        }

        // Validate the candidate
        count = 0;
        foreach (int num in arr) {
            if (num == candidate) {
                count++;
            }
        }
	
      	// If count is greater than n / 2, return 
      	// the candidate; otherwise, return -1
        if (count > n / 2) {
            return candidate;
        } else {
            return -1;
        }
    }

    static void Main() {
        int[] arr = {1, 1, 2, 1, 3, 5, 1};
        Console.WriteLine(majorityElement(arr));
    }
}

function majorityElement(arr) {

    const n = arr.length;
    let candidate = -1;
    let count = 0;

    // Find a candidate
    for (const num of arr) {
        if (count === 0) {
            candidate = num;
            count = 1;
        } 
        else if (num === candidate) {
            count++;
        }
        else {
            count--;
        }
    }

    // Validate the candidate
    count = 0;
    for (const num of arr) {
        if (num === candidate) {
            count++;
        }
    }
	
    // If count is greater than n / 2, return 
    // the candidate; otherwise, return -1
    if (count > n / 2) {
        return candidate;
    } else {
        return -1;
    }
}

// Driver Code 
const arr = [1, 1, 2, 1, 3, 5, 1];
console.log(majorityElement(arr));

1