Given an array of n integers, a contiguous subarray is called dominant if some single value occurs strictly more than half of the subarray's length within it (equivalently, more than every other value combined). Count the number of dominant contiguous subarrays (index ranges [i, j] with i ≤ j), out of all n(n+1)/2 possible contiguous subarrays.
Line 1: an integer n.
Line 2: n space-separated integers (the array).
A single integer: the number of dominant contiguous subarrays.
Example 1
Input
4 1 1 2 1
Expected
8
Explanation
Every single-element subarray is trivially dominant (4 of them). Among length-2 subarrays only [1,1] (positions 1-2) is dominant. Among length-3 subarrays, [1,1,2] and [1,2,1] are both dominant (value 1 appears twice out of three). The full array [1,1,2,1] is dominant (1 appears three times out of four). Total dominant subarrays: 4 + 1 + 2 + 1 = 8.
Example 2
Input
3 1 2 3
Expected
3
Explanation
The three single-element subarrays are trivially dominant. No subarray of length 2 or 3 has a value occurring more than half the time, since all three values are distinct. Total: 3.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →