BackeasyHashingSwiggy

Majority Element Identifier Solution

Problem Statement

You are given an integer array arr containing N numbers. Your task is to identify whether there exists a majority element within the sequence. An element is considered a majority element if its frequency of occurrence is strictly greater than N / 2 (where N is the total number of elements in the array).

If such an element exists, return its value. Otherwise, return -1 to indicate that no element meets the required frequency threshold. The array may contain positive integers, negative integers, and zeros.

Example 1
Input
arr = [4, -2, 4, 4, 1, 4, 4]
Output
4

Explanation: The array contains N = 7 elements. The threshold for a majority element is strictly greater than 7 / 2 = 3.5 (i.e., at least 4 occurrences). The number 4 appears 5 times, which exceeds 3.5. Therefore, the output is 4.

Example 2
Input
arr = [10, 20, 10, 30, 20, 30]
Output
-1

Explanation: The array length N = 6. To be a majority element, an integer must appear strictly more than 6 / 2 = 3 times (at least 4 times). The numbers 10, 20, and 30 each appear only 2 times. Since no number appears more than 3 times, the output is -1.

Example 3
Input
arr = [-5, -5, 0, -5]
Output
-5

Explanation: The array length N = 4. The required frequency must be strictly greater than 4 / 2 = 2. The integer -5 occurs 3 times, satisfying the majority condition. Thus, the output is -5.

Example 4
Input
arr = [7, 7, 7, 8, 8, 8]
Output
-1

Explanation: The array length N = 6. A majority element must appear strictly more than 3 times. Both 7 and 8 appear exactly 3 times, which does not strictly exceed 3. Hence, the output is -1.

Constraints

  • 1 <= arr.length <= 10^5
  • -10^9 <= arr[i] <= 10^9
Live Compiler1 Free Run Available
Loading Editor...
Test Cases & Output
Click "Run" to test your 1 free compile trial!

🚀 Practice this problem

Run code, get AI hints & track streak

Sign Up Free

Majority Element Identifier — Problem Statement & Solution Guide

HashingEasyBoyer-Moore Voting
TimeO(N)
|
SpaceO(1)

Problem Description

You are given an integer array arr containing N numbers. Your task is to identify whether there exists a majority element within the sequence. An element is considered a majority element if its frequency of occurrence is strictly greater than N / 2 (where N is the total number of elements in the array).

If such an element exists, return its value. Otherwise, return -1 to indicate that no element meets the required frequency threshold. The array may contain positive integers, negative integers, and zeros.

DSA Pattern Breakdown

DSA Pattern Breakdown

"Majority Element Identifier"

easy

WHY DOES IT MATTER?

Mastering element cancellation techniques transitions developers from relying on memory-intensive hash tables to designing ultra-efficient O(1) auxiliary space algorithms.

OPTIMIZATION CHALLENGE

The key insight is realizing that tracking an absolute frequency map is unnecessary; we only need to maintain a single relative balance state between the lead candidate and non-candidate elements.

REAL-WORLD CONNECTION

In fault-tolerant distributed consensus systems (like Raft or Paxos) and stream telemetry, identifying majority votes or dominant error codes under tight memory limits relies on majority voting dynamics.

Always clarify with the interviewer whether a majority element is guaranteed to exist. If it is guaranteed, one pass suffices; if not guaranteed, explicitly code the second verification pass.

COMPLEXITY AT A GLANCE

⏱ Time:O(N)
💾 Space:O(1)

Core Theory — Why This Approach?

The Majority Element problem asks us to find an element that appears more than half the time (frequency > N / 2) in an array of size N. A naive solution uses two nested loops to count the occurrence of every element, leading to an O(N^2) time complexity. For large inputs (e.g., N = 10^5), this brute-force method requires billions of operations, causing a Time Limit Exceeded (TLE) error. Using a Hash Map reduces the time complexity to O(N) by storing element frequencies in a single pass, but requires O(N) auxiliary space.

To achieve both optimal O(N) time and O(1) space, we leverage the Boyer-Moore Voting Algorithm. The core theory behind Boyer-Moore rests on the principle of cancellation: if we pair distinct elements and remove them from consideration, a majority element (appearing strictly more than N / 2 times) will always remain in the pool. By maintaining a running candidate and a counter, distinct elements effectively cancel each other out, leaving the majority element as the final candidate.

Since the problem statement indicates that a majority element might not exist, the algorithm requires two phases: Candidate Selection using Boyer-Moore, followed by Candidate Verification. The verification step requires a second simple linear scan to count the exact occurrences of the candidate and verify that frequency strictly exceeds N / 2. If it does not, we return -1.

Interview Questions on This Problem

Q1How would you modify the Boyer-Moore Voting Algorithm if the problem required finding elements that appear more than N / 3 times?

To find elements appearing more than N / 3 times, there can be at most two such majority elements. We extend Boyer-Moore by keeping track of two candidate variables and two corresponding count variables. In a single pass, if an element matches either candidate, we increment its count; if a count is zero, we assign the new element as that candidate; otherwise, if the current element differs from both, we decrement both counts. Finally, a second verification pass counts exact occurrences for both candidates to confirm if their frequencies strictly exceed N / 3.

Q2Can the Boyer-Moore Voting Algorithm be applied to distributed data streams stored across multiple server nodes?

Yes. Using a MapReduce or stream-processing architecture, each worker node can run the Boyer-Moore algorithm on its local partition to output a local candidate along with its remaining candidate count. These local summaries can then be reduced and merged centrally. However, because local candidates might differ, a secondary consensus pass (or global frequency count pass across nodes) is required to accurately compute the global majority element.

Q3Why is the second verification pass mandatory when a majority element is not guaranteed to exist in the array?

Boyer-Moore always outputs a final candidate value at the end of the array traversal, even if no element actually appears strictly more than N / 2 times. For instance, in the array [1, 2, 3], the algorithm might terminate with 3 as the candidate, even though its frequency is only 1 (which is <= 3 / 2). Without a second pass to explicitly count frequency and check the > N / 2 condition, the algorithm would incorrectly return 3 instead of -1.

Examples

Example 1

Input

arr = [4, -2, 4, 4, 1, 4, 4]

Output

4

Explanation: The array contains N = 7 elements. The threshold for a majority element is strictly greater than 7 / 2 = 3.5 (i.e., at least 4 occurrences). The number 4 appears 5 times, which exceeds 3.5. Therefore, the output is 4.

Example 2

Input

arr = [10, 20, 10, 30, 20, 30]

Output

-1

Explanation: The array length N = 6. To be a majority element, an integer must appear strictly more than 6 / 2 = 3 times (at least 4 times). The numbers 10, 20, and 30 each appear only 2 times. Since no number appears more than 3 times, the output is -1.

Example 3

Input

arr = [-5, -5, 0, -5]

Output

-5

Explanation: The array length N = 4. The required frequency must be strictly greater than 4 / 2 = 2. The integer -5 occurs 3 times, satisfying the majority condition. Thus, the output is -5.

Example 4

Input

arr = [7, 7, 7, 8, 8, 8]

Output

-1

Explanation: The array length N = 6. A majority element must appear strictly more than 3 times. Both 7 and 8 appear exactly 3 times, which does not strictly exceed 3. Hence, the output is -1.

Constraints

  • 1 <= arr.length <= 10^5
  • -10^9 <= arr[i] <= 10^9

Optimal Approach & Strategy

Apply Boyer-Moore's Voting Algorithm in a single pass to identify a candidate element by maintaining a running vote counter. Run a second linear verification pass to validate if the candidate's actual frequency strictly exceeds N / 2, returning -1 if it does not.

Brute Force Approach

Iterate through each element of the array and count its total frequency by scanning the rest of the array using a nested loop. Return the element if its count strictly exceeds N / 2, resulting in an O(N^2) time complexity.

Verified Code Solutions

JavaScript Solution
Time: O(N)
const fs = require('fs');

function majorityElement(arr) {
    const n = arr.length;
    if (n === 0) return -1;
    const counts = new Map();
    for (const num of arr) {
        const count = (counts.get(num) || 0) + 1;
        if (count > Math.floor(n / 2)) {
            return num;
        }
        counts.set(num, count);
    }
    return -1;
}

function main() {
    const input = fs.readFileSync('/dev/stdin', 'utf-8').trim();
    if (!input) {
        console.log(-1);
        return;
    }
    const arr = input.split(/\s+/).map(Number);
    console.log(majorityElement(arr));
}

main();

Asked in Top Tech Interviews

Swiggy

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.