Network Network Resolver 22 — Problem Statement & Solution Guide

GreedyEasyFrequency Hash Map

TimeO(n)

SpaceO(1)

Problem Description

Given an integer array nums representing a sequence of packet identifiers, determine the identifier that occurs strictly more than half of the total number of packets. If such an identifier exists, return its value; otherwise, return -1. The solution must run in linear time and use O(1) additional space beyond the input array, employing a greedy counting technique (e.g., Boyer‑Moore majority vote) or a frequency hash map as a fallback.

DSA Pattern Breakdown

"Network Network Resolver 22"

easy

WHY DOES IT MATTER?

Identifying a majority element in O(n) time and O(1) space is a classic greedy pattern that teaches cancellation reasoning.

OPTIMIZATION CHALLENGE

The key is reducing auxiliary storage from linear to constant while still guaranteeing a correct answer.

REAL-WORLD CONNECTION

It mirrors leader election in distributed systems where the most frequent vote wins without storing all votes.

Always add a verification pass; the first pass only yields a potential majority, not proof.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The majority‑element problem can be solved with the Boyer‑Moore Voting Algorithm, which maintains a candidate and a counter while scanning the array once. The counter increments when the current element matches the candidate and decrements otherwise; when the counter reaches zero, the next element becomes the new candidate, guaranteeing that any element occurring more than ⌊n/2⌋ times will survive as the final candidate. Naïve solutions such as sorting (O(n log n)) or hash‑map counting (O(n) time but O(n) extra space) become prohibitive for massive streams because they either exceed the required linear‑time bound or violate the O(1) auxiliary‑space constraint. The greedy nature of Boyer‑Moore leverages the cancellation principle: pairs of different elements neutralize each other, leaving the majority element unpaired, which is why it is optimal for this specific frequency threshold.

Interview Questions on This Problem

Q1Explain why the Boyer‑Moore algorithm works only when the majority element appears more than n/2 times.

If an element appears more than half the time, it cannot be completely cancelled by all other elements combined. The algorithm’s pair‑cancellation guarantees that such an element will remain as the final candidate.

Q2What additional step must you perform after the first pass of Boyer‑Moore to ensure correctness?

You must verify the candidate by counting its occurrences in a second pass, because the algorithm only guarantees a candidate, not its frequency. This confirms whether it truly exceeds the n/2 threshold.

Q3How would you adapt the algorithm to find an element occurring more than ⌊n/3⌋ times?

Maintain two candidates and two counters, applying a similar cancellation rule for three‑way majority. After the first pass, verify each candidate with a second pass.

Examples

Example 1

Input

[3,3,4,2,3,3,3]

Output

Explanation: The array length is 7, so a majority must appear at least 4 times. Counting frequencies: 3 appears 5 times, 4 appears once, 2 appears once. Since 5 > 7/2, the dominant identifier is 3.

Example 2

Input

[1,2,3,4]

Output

-1

Explanation: The array length is 4; a majority would need >2 occurrences. Each value appears only once, so no identifier satisfies the condition. The function returns -1.

Example 3

Input

[5,5,5,5]

Output

Explanation: Length = 4, required count >2. The value 5 appears 4 times, which exceeds the half‑length threshold, therefore 5 is returned as the dominant identifier.

Constraints

1 <= nums.length <= 100000
-10^9 <= nums[i] <= 10^9
The algorithm should run in O(n) time where n is nums.length
Only O(1) extra space (excluding the input array) is allowed for the greedy approach

Optimal Approach & Strategy

Apply Boyer‑Moore Voting to obtain a candidate in one pass, then verify its count in a second pass, achieving linear time and constant extra space.

Brute Force Approach

Count each element with a hash map or sort the array, then check frequencies; both exceed the O(1) space or O(n log n) time limits.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    let candidate = 0;
    let count = 0;
    
    for (let num of nums) {
        if (count === 0) {
            candidate = num;
            count = 1;
        } else if (num === candidate) {
            count++;
        } else {
            count--;
        }
    }
    
    let verifyCount = 0;
    for (let num of nums) {
        if (num === candidate) {
            verifyCount++;
        }
    }
    
    return verifyCount > Math.floor(nums.length / 2) ? candidate : -1;
};

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate = 0;
        int count = 0;
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
                count = 1;
            } else if (num == candidate) {
                count++;
            } else {
                count--;
            }
        }
        
        int verifyCount = 0;
        for (int num : nums) {
            if (num == candidate) {
                verifyCount++;
            }
        }
        
        return verifyCount > nums.size() / 2 ? candidate : -1;
    }
};

class Solution {
    public int majorityElement(int[] nums) {
        int candidate = 0;
        int count = 0;
        
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
                count = 1;
            } else if (num == candidate) {
                count++;
            } else {
                count--;
            }
        }
        
        int verifyCount = 0;
        for (int num : nums) {
            if (num == candidate) {
                verifyCount++;
            }
        }
        
        return verifyCount > nums.length / 2 ? candidate : -1;
    }
}

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        candidate = 0
        count = 0
        
        for num in nums:
            if count == 0:
                candidate = num
                count = 1
            elif num == candidate:
                count += 1
            else:
                count -= 1
        
        verify_count = sum(1 for num in nums if num == candidate)
        return candidate if verify_count > len(nums) // 2 else -1

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    let candidate = 0;
    let count = 0;
    
    for (let num of nums) {
        if (count === 0) {
            candidate = num;
            count = 1;
        } else if (num === candidate) {
            count++;
        } else {
            count--;
        }
    }
    
    let verifyCount = 0;
    for (let num of nums) {
        if (num === candidate) {
            verifyCount++;
        }
    }
    
    return verifyCount > Math.floor(nums.length / 2) ? candidate : -1;
};

Asked in Top Tech Interviews

GoogleAmazonMicrosoft

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.

Network Network Resolver 22 Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Constraints

More Greedy

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Network Network Resolver 22 — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor