easyArraysPattern: Moore's Voting
Dominant Array Value Solution
Problem Statement
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. You may assume that the input array is non-empty and that a dominant value is guaranteed to exist in the array.
Examples
Example 1:
Input:nums = [3, 2, 3]
Output:3
Explanation: The size of the array is 3. The value 3 appears 2 times, which is strictly greater than ⌊3 / 2⌋ = 1.
Example 2:
Input:nums = [4, 4, 1, 4, 2, 4, 4]
Output:4
Explanation: The size of the array is 7. The value 4 appears 5 times, which is strictly greater than ⌊7 / 2⌋ = 3.
Constraints
- 1 <= nums.length <= 5 * 10^4
- -10^9 <= nums[i] <= 10^9
Time: O(n) Space: O(1)
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.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
import sys
import re
def find_dominant(nums):
candidate = None
count = 0
for num in nums:
if count == 0:
candidate = num
count += 1 if num == candidate else -1
return candidate
def main():
input_data = sys.stdin.read().strip()
if not input_data:
return
cleaned = re.sub(r'[\[\]]', '', input_data)
tokens = re.split(r'[\s,]+', cleaned)
nums = [int(x) for x in tokens if x.strip() != '']
if len(nums) > 1 and nums[0] == len(nums) - 1:
nums = nums[1:]
print(find_dominant(nums))
if __name__ == '__main__':
main()