Count Subarrays with a Target Majority
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Given an integer array `nums` and an integer `target`, count its nonempty contiguous subarrays in which `target` is the majority element.
A value is a majority only when it occurs **strictly more than half** as many times as the subarray's length. An occurrence count of exactly half does not qualify. Subarrays with different start or end positions are counted separately, even if their values are identical.
```cpp
class Solution {
public:
int countMajoritySubarrays(vector<int>& nums, int target);
};
```
### Examples
**Example 1:**
```text
Input: nums = [7,1,7], target = 7
Output: 3
Explanation: The qualifying intervals are [0,0], [2,2], and [0,2]. Each length-two interval contains exactly one 7, so neither has a strict majority.
```
**Example 2:**
```text
Input: nums = [6,6,2,6], target = 6
Output: 7
Explanation: The qualifying intervals are [0,0], [1,1], [3,3], [0,1], [0,2], [1,3], and [0,3], using zero-based inclusive endpoints.
```
### Constraints
- `1 <= nums.length <= 1000`.
- `1 <= nums[i] <= 1000000000`.
- `1 <= target <= 1000000000`.
### Clarifying Questions
- Must the subarray be contiguous? Yes.
- Is the requested majority specifically `target`? Yes; a different majority value does not make an interval count.
- Is `target` guaranteed to occur? No; if it never occurs, the result is zero.
- Are equal values at different positions distinct occurrences? Yes.
### What a Strong Answer Covers
- The fixed target, nonempty contiguous intervals, and strict majority threshold.
- Counting each qualifying interval exactly once.
- Exactly-half ties, absent targets, and intervals consisting only of the target.
- Correct count bounds, completeness, and time and memory analysis.
### Follow-up Questions
- How would listing all qualifying intervals affect output size?
- How would requesting a majority of any value change the specification?
```hint Use this version's length limit
The length bound permits examining every start and end pair. While extending an interval, maintain its target occurrence count and test whether twice that count exceeds its length.
```
Overview: Count contiguous subarrays where a fixed target has a strict majority. Covers exact-half ties, absent targets, examples, proof, and a C++ solution.