0236MediumArrayHash TableDivide and ConquerSegment TreeMerge SortCountingPrefix Sum

Stretches Carried by One Candidate

Tracked in this browser only

Trains the technique from

LeetCode 3737Count Subarrays With Majority Element I

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def count_carried_runs(ballots: list[int], pick: int) -> int:

Java

public int countCarriedRuns(int[] ballots, int pick)

The intended approach

Time O(n log n)Space O(n) for the Fenwick tree

Score every ballot as +1 when it is marked for `pick` and -1 otherwise, and keep the running total after each ballot. A stretch is carried exactly when the running total at its end exceeds the running total just before its start, so the answer is the number of ordered pairs of running totals where the later one is the larger. Feed the totals into a Fenwick tree indexed by the total shifted up by the ballot count, querying for the totals already stored that are strictly smaller before storing each new one. The total before the first ballot is stored first, so stretches that begin at position 0 are included.

Pythonentry point: count_carried_runs

def count_carried_runs(ballots, pick):
    total = len(ballots)
    span = 2 * total + 2
    tree = [0] * (span + 1)

    def record(value):
        index = value + 1
        while index <= span:
            tree[index] += 1
            index += index & -index

    def below_or_equal(value):
        index = value + 1
        seen = 0
        while index > 0:
            seen += tree[index]
            index -= index & -index
        return seen

    # running = (ballots for pick so far) - (ballots against pick so far); a stretch
    # is carried exactly when the running figure grows across it, so every earlier
    # running figure that is strictly smaller than the current one ends one stretch
    running = 0
    record(running + total)
    carried = 0
    for marked in ballots:
        running += 1 if marked == pick else -1
        carried += below_or_equal(running + total - 1)
        record(running + total)
    return carried

The obvious version

Fix each start, extend the stretch one ballot at a time keeping a tally for pick, and test the tally against the stretch length. O(n^2).

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_count_carried_runs(ballots, pick):
    # Walk every start, extend one ballot at a time and test the tally directly.
    total = len(ballots)
    carried = 0
    for start in range(total):
        hits = 0
        for end in range(start, total):
            if ballots[end] == pick:
                hits += 1
            if 2 * hits > end - start + 1:
                carried += 1
    return carried

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in