Count Target-Majority Subarrays in a Large Array
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
Given an integer array `nums` and an integer `target`, count the nonempty contiguous subarrays in which `target` occurs strictly more than half as many times as the subarray's length.
An occurrence count equal to exactly half the length does not qualify. Intervals with different endpoints count separately, even when they contain identical values.
```cpp
class Solution {
public:
long long countMajoritySubarrays(vector<int>& nums, int target);
};
```
### Examples
**Example 1:**
```text
Input: nums = [4,9,4,4], target = 4
Output: 7
Explanation: The qualifying inclusive intervals are [0,0], [2,2], [3,3], [2,3], [0,2], [1,3], and [0,3].
```
**Example 2:**
```text
Input: nums = [8,8,8,8,8], target = 8
Output: 15
Explanation: Every nonempty interval qualifies. There are 5+4+3+2+1 = 15 such intervals.
```
### Constraints
- `1 <= nums.length <= 100000`.
- `1 <= nums[i] <= 1000000000`.
- `1 <= target <= 1000000000`.
### Clarifying Questions
- Is the requested majority specifically `target`? Yes.
- Must a subarray use consecutive positions? Yes.
- Is `target` guaranteed to appear? No; an absent target gives a count of zero.
- Can the answer exceed a 32-bit signed integer? Yes; preserve the `long long` return type.
### What a Strong Answer Covers
- The fixed-target requirement, contiguity, and strictly-more-than-half threshold.
- Counting every qualifying interval exactly once, including repeated values.
- Exactly-half ties, an absent target, and arrays consisting only of the target.
- A complete proof, numeric safety, and resource bounds for length 100000.
### Follow-up Questions
- How would returning all qualifying endpoint pairs affect output size?
- How would asking for a majority of any value change the output condition?
```hint Turn majority into a strict prefix comparison
Give target occurrences weight +1 and other entries weight -1. A qualifying interval has positive total weight, so its ending prefix sum is greater than its starting prefix sum. Count earlier strictly smaller prefix sums with an indexed frequency structure; equal prefix sums must not contribute.
```
Overview: Count subarrays where a fixed target has a strict majority at length up to 100000. Includes fresh examples, a complete proof, wide counts, and C++ code.
