Dominant Array Value — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Majority element detection
O(n)O(1)Problem Description
You are provided with a non-empty integer array nums of length n. Your task is to determine if there exists a 'dominant' element within this array. An element is considered dominant if its frequency of occurrence is strictly greater than half the total number of elements in the array, i.e., count > n / 2. If such an element exists, return its value. If no element satisfies this condition, return the string "No dominant value exists".
The problem guarantees that the input array will always contain at least one element. You may assume that the values in the array are integers within a standard 32-bit signed integer range. The solution should efficiently identify the candidate and verify its dominance, ideally in linear time complexity.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Dominant Array Value"
WHY DOES IT MATTER?
Identifying a majority element is a classic example of the "linear‑time, constant‑space" pattern, which appears in streaming analytics, fault‑tolerant consensus, and voting systems where memory is at a premium.
OPTIMIZATION CHALLENGE
The breakthrough is realizing that you don't need full frequency counts; you can eliminate non‑majority elements in pairs, reducing the problem to tracking a single candidate and a net count.
REAL-WORLD CONNECTION
In distributed leader election, nodes exchange votes; pairs of opposing votes cancel out, leaving the true leader—mirroring the cancellation principle of Boyer‑Moore.
During an interview, first state the O(n) hash‑map solution, then immediately propose Boyer‑Moore as the O(1) space improvement, and remember to add the verification pass to avoid false positives.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The problem asks for a majority element—an element whose occurrence count exceeds half the array length. A naive solution would tally frequencies with a hash map, which is linear time but linear extra space, and still requires a second pass to verify the majority condition. For very large inputs, the extra memory can be prohibitive, especially in constrained environments like embedded systems or streaming pipelines. The optimal paradigm leverages the Boyer‑Moore Majority Vote algorithm, which maintains a candidate and a counter while scanning the array once. The key insight is that pairs of different elements can be cancelled out without affecting the majority candidate, guaranteeing that if a majority exists it will survive as the final candidate. A second linear pass is then used to confirm that the candidate truly appears more than n/2 times, ensuring correctness even when no majority exists.
Interview Questions on This Problem
Q1How would you modify the Boyer‑Moore algorithm to find all elements that appear more than ⌊n/3⌋ times?
Maintain up to two candidates with their counters because at most two numbers can satisfy the > n/3 condition. Iterate to update candidates similarly to the majority vote, then verify both candidates in a second pass.
Q2If the array is read-only and you cannot use extra space, can you still determine the majority element?
Yes. The Boyer‑Moore algorithm uses O(1) extra space and works on a read‑only array because it only needs to keep a candidate and a counter while scanning the data.
Q3Explain why a hash‑map based solution may fail on a distributed system where the array is sharded across multiple nodes.
Each node would compute local frequencies, but the global majority may be split across shards, requiring a reduction step to aggregate counts. This adds network overhead and O(k) extra space per node, whereas a streaming majority vote can be performed locally and merged with minimal communication.
Examples
Input
nums = [7, 3, 7, 7, 2, 7, 7]
Output
7
Explanation: The array length n is 7. The threshold for dominance is strictly greater than 7 / 2 = 3.5, so the count must be at least 4. The element 7 appears 5 times, which is greater than 3.5. Therefore, 7 is the dominant value.
Input
nums = [1, 2, 3, 4, 5]
Output
No dominant value exists
Explanation: The array length n is 5. The threshold is strictly greater than 5 / 2 = 2.5, so the count must be at least 3. Each element (1, 2, 3, 4, 5) appears exactly once. Since no element appears more than 2.5 times, no dominant value exists.
Input
nums = [4, 4, 4, 1, 2]
Output
4
Explanation: The array length n is 5. The threshold is strictly greater than 2.5. The element 4 appears 3 times. Since 3 > 2.5, 4 is the dominant value.
Input
nums = [10, 10, 20, 20]
Output
No dominant value exists
Explanation: The array length n is 4. The threshold is strictly greater than 4 / 2 = 2.0, so the count must be at least 3. The element 10 appears 2 times, and 20 appears 2 times. Neither count is strictly greater than 2.0. Thus, no dominant value exists.
Constraints
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
- The input array is guaranteed to be non-empty.
Optimal Approach & Strategy
Apply Boyer‑Moore Majority Vote to find a candidate in one pass, then verify its count in a second pass, achieving O(n) time and O(1) space.
Brute Force Approach
Count the occurrences of each element using a nested loop or a hash map, then check if any count exceeds n/2.
Code Solutions
function findDominant(nums) {
let candidate = null;
let count = 0;
let maxCount = Math.floor(nums.length / 2);
let maxCandidate = null;
for (let i = 0; i < nums.length; i++) {
if (count === 0) {
candidate = nums[i];
count = 1;
} else if (nums[i] === candidate) {
count++;
} else {
count = 1;
candidate = nums[i];
}
if (count > maxCount) {
maxCandidate = candidate;
maxCount = count;
}
}
return maxCandidate === null ? 'No dominant value exists' : candidate;
}#include <iostream>
#include <vector>
using namespace std;
int findDominantValue(const 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--;
}
}
return candidate;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int val;
vector<int> nums;
while (cin >> val) {
nums.push_back(val);
}
if (!nums.empty()) {
cout << findDominantValue(nums) << "\n";
}
return 0;
}class Solution {
public String dominantValue(int[] nums) {
Map<Integer, Integer> countMap = new HashMap<>();
int maxCandidate = 0;
int maxCount = 0;
for (int num : nums) {
countMap.put(num, countMap.getOrDefault(num, 0) + 1);
if (countMap.get(num) > maxCount) {
maxCandidate = num;
maxCount = countMap.get(num);
}
}
if (maxCount > nums.length / 2) {
return String.valueOf(maxCandidate);
} else {
return 'No dominant value exists';
}
}
}def dominantValue(nums):
count_map = {}
max_candidate = None
max_count = 0
for num in nums:
if num in count_map:
count_map[num] += 1
else:
count_map[num] = 1
if count_map[num] > max_count:
max_candidate = num
max_count = count_map[num]
if max_count > len(nums) // 2:
return max_candidate
else:
return 'No dominant value exists'function findDominant(nums) {
let candidate = null;
let count = 0;
let maxCount = Math.floor(nums.length / 2);
let maxCandidate = null;
for (let i = 0; i < nums.length; i++) {
if (count === 0) {
candidate = nums[i];
count = 1;
} else if (nums[i] === candidate) {
count++;
} else {
count = 1;
candidate = nums[i];
}
if (count > maxCount) {
maxCandidate = candidate;
maxCount = count;
}
}
return maxCandidate === null ? 'No dominant value exists' : candidate;
}Asked in Top Tech Interviews
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.