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 Array

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.

Majority Element In An Array
DSA desktop gif
DSA mobile gif

Introduction  to Arrays

Introduction to 2-D Arrays

Array Rotation

Reverse an Array or String

Sort the array in Waveform

Algorithm

  1. Initialize a variable candidate to store the candidate element, and set it to the first element of the array arr[0].
  2. Initialize a variable count to store the count of occurrences of the candidate element, and set it to 1.
  3. 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.
  4. Reset count to 0.
  5. 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.
  6. If count is greater than n/2, return the candidate element as the majority element.
  7. 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

Get Prime
Course List
Course List

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout
Checkout

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