Show problems as
Classic problem #3737MediumArrayHash TableDivide and ConquerSegment TreeMerge SortCountingPrefix Sum

Count Subarrays With Majority Element I

Real-world version: Stretches Carried by One Candidate
Tracked in this browser only
Read Count Subarrays With Majority Element I on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A returning officer has emptied a ballot box and recorded ballots, where ballots[i] is the identifier of the candidate marked on the i-th ballot in the order they came out. One candidate, pick, is under review.

A stretch is one or more ballots sitting next to each other in that order. A stretch is carried by pick when strictly more than half of the ballots in it are marked for pick.

Return how many stretches pick carries. Two stretches count separately whenever they begin or end at different positions, even if they hold the same identifiers.

Examples

Example 1

Input
ballots = [7, 7, 4, 4], pick = 7
Output
4

Four stretches are carried by 7: position 0 on its own, position 1 on its own, positions 0 through 1 with two of two ballots marked 7, and positions 0 through 2 with two of three.

Example 2

Input
ballots = [4, 9, 4, 9, 4], pick = 4
Output
6

The single ballots at positions 0, 2 and 4 are carried, as are positions 0 through 2 and 2 through 4 with two of three ballots each, and positions 0 through 4 with three of five.

Example 3

Input
ballots = [1, 2, 3], pick = 4
Output
0

No ballot is marked for 4, so no stretch can have more than half of its ballots marked for 4.

Constraints

  • 1 <= ballots.length <= 1000
  • 1 <= ballots[i] <= 10^9
  • 1 <= pick <= 10^9

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def count_carried_runs(ballots: list[int], pick: int) -> int:
Java
public int countCarriedRuns(int[] ballots, int pick)

More on the same topics