Dominant Array Value — Problem Statement & Solution Guide
Problem Description
Given an integer array nums of size n, identify and return the dominant value. A dominant value is defined as the element that appears strictly more than ⌊n / 2⌋ times in the array. If no such value exists, return 'No dominant value exists'. You may assume that the input array is non-empty.
Examples
Input
[1, 1, 2, 2, 3, 3, 3, 3, 3]
Output
3
Explanation: Step-by-step: with input [1, 1, 2, 2, 3, 3, 3, 3, 3], we first count the frequency of each element. The frequency of 3 is 5, which is greater than ⌊9 / 2⌋ = 4. Therefore, the dominant value is 3.
Input
[1, 1, 1, 2, 2, 3, 3, 3, 3]
Output
No dominant value exists
Explanation: Step-by-step: with input [1, 1, 1, 2, 2, 3, 3, 3, 3], we first count the frequency of each element. The frequency of 1 is 3, the frequency of 2 is 2, and the frequency of 3 is 4. Since 4 is not strictly greater than ⌊9 / 2⌋ = 4, there is no dominant value.
Constraints
- 1 <= nums.length <= 5 * 10^4
- -10^9 <= nums[i] <= 10^9
Optimal Approach & Strategy
The optimal approach uses the Boyer-Moore Voting Algorithm to find the dominant element in a single linear pass. By maintaining a candidate variable and a counter that increments for matching elements and decrements for differing ones, the dominant element is guaranteed to be the final candidate. This achieves maximum efficiency with constant extra space.
Brute Force Approach
The brute force approach involves using nested loops to count the frequency of each element in the array. For each element, we scan the rest of the array to count its occurrences, returning the element if its count exceeds n / 2. This method is inefficient as it requires quadratic time.
Verified 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.