Majority Element in an Array in Java

April 28, 2023

Majority Element in array in Java Language

In this page we will look into a coding question where we will learn how to find the element which occurs majority number of times in array in Java Programming Language.
There might be different approach to solve this question, one you will find here. If your approach is bit different post it onto the comment section.

Majority Element In An Array In Java

The Boyer-Moore Majority Vote Algorithm is a widely used algorithm for finding the majority element in an array. The majority element in an array in Java is an element that appears more than n/2 times, where n is the size of the array.

This Algorithm is efficient with a time complexity of O(n) and a space complexity of O(1), as it uses constant extra space to maintain the candidate and count variables. It is a clever algorithm that leverages the properties of majority elements to find them efficiently in linear time.

Introduction to Arrays

Introduction to 2-D Arrays

Array Rotation

Reverse an Array or String

Sort the array in Waveform

Algorithm

Initialize a variable candidate to store the candidate element, and set it to the first element of the array arr[0].
Initialize a variable count to store the count of occurrences of the candidate element, and set it to 1.
Iterate through the array arr from index 1 to n-1:
- If count is 0, set the current element as the new candidate element and increment count to 1.
- If the current element is equal to the candidate element, increment count by 1.
- If the current element is not equal to the candidate element, decrement count by 1.
Reset count to 0.
Iterate through the array arr again to verify if the candidate element is a majority element:
- If the current element is equal to the candidate element, increment count by 1.
If count is greater than n/2, return the candidate element as the majority element.
If no majority element is found, return -1.

Program to find the element that occurs most of the time in an array

Run

import java.util.*;

public class Main
{
    
    public static int findMajoriytElement(int n, int [] arr)
    {
        int candidate = 0;
        int count = 0;
        
        for(int i  = 0; i < n; i++)
        {
            if(count == 0)
            {
                candidate = arr[i];
                count = 1;
            }
            else if(arr[i] == candidate)
            {
                count++;
            }
            else
            {
                count--;
            }
        }
        
        count = 0;
        for(int i =0; i < n; i++)
        {
            if(arr[i] == candidate)
            {
                count++;
            }
        }
        
        if((count >= n/2 && n%2 == 0) || (count > n/2 && n%2 != 0))
        {
            return candidate;
        }
        else
        {
            return -1;
        }
    }
    
    public static void main(String[] args) {
        int arr[] = {3, 3, 4, 2, 4, 4, 2, 4, 4,3};       
        int n = arr.length;
        int majorityElement = findMajoriytElement(n, arr);
        if(majorityElement != -1)
        {
            System.out.print("Majority element is : " + majorityElement);
        }
        else
        {
            System.out.print("No majority element found");
        }
    }
}

OUTPUT:
Majority element is : 4

Prime Course Trailer

Related Banners

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Arrays

Introduction to Arrays – C | C++ | Java
Introduction to 2-D Arrays – C | C++ | Java
Sorting of Array – C | C++ | Java
Array Rotation – C | C++ | Java
Reverse an array or string- C | C++ | Java
Find pairs in array with given sum – C | C++ | Java
Sort the array in Waveform – C | C++ | Java
Majority Element in Array – C | C++ | Java
Boyer-Moore’s Voting Algorithm – C | C++ | Java
K-pairs with smallest sum in 2 arrays – C | C++ | Java
Largest Sum Contigous SubArray – C | C++ | Java
Maximum Average Sub-array of K length – C | C++ | Java
Size of sub-array with max sum – C | C++ | Java
Sub-array with given sum – C | C++ | Java
Triplet that sum to a given value – C | C++ | Java
Segregate 0’s and 1’s in array – C | C++ | Java
Segregate 0’s 1’s and 2’s in array – C | C++ | Java
Sort elements in array by frequency – C | C++ | Java
Finding pythagorean triplets in an array – C | C++ | Java
Reorder array using given indexes – C | C++ | Java
Merging two sorted arrays – C | C++ | Java
Minimum number of Merge Operations to make an Array Palindrome – C | C++ | Java
Find Zeros to be Flipped so that number of Consecutive 1’s is maximized – C | C++ | Java