1039MediumArrayPrefix Sum

Cuts Where the Front Holds Its Own

Tracked in this browser only

Trains the technique from

LeetCode 2270Number of Ways to Split Array

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 strip of readings reads readings. A cut falls between two neighbouring readings, so there is one fewer cut than there are readings, and every cut leaves a front piece and a back piece, neither of them empty.

A cut is sound when the front piece's total is at least the back piece's.

Return how many cuts are sound.

Examples

Example 1

Input: readings = [5, -5, 5, -5]
Output: 3

The whole strip totals nothing. After the first reading the front holds five and the back minus five, after the second both hold nothing, and after the third the front holds five again, so all three cuts are sound.

Example 2

Input: readings = [1, 6]
Output: 0

The only cut leaves a front of one against a back of six, so it is not sound.

Example 3

Input: readings = [3, 3, 3, 3]
Output: 2

The first cut leaves three against nine and fails. The second leaves six against six and passes, and the third leaves nine against three and passes too.

Constraints

2 <= readings.length <= 10^5
-10^5 <= readings[i] <= 10^5

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 ways_to_split_array(readings: list[int]) -> int:

Java

public int waysToSplitArray(int[] readings)

The intended approach

Time O(n) over the strip's length.Space O(1).

Add the whole strip up once. Then walk the cuts from left to right carrying the front piece's total: each reading joins the front, and the back piece's total is the whole strip's total less the front's, so it never has to be added up separately. Compare the two at each cut and count it when the front is at least the back. The walk stops one reading short of the end, since the back piece may not be left empty. One pass for the total and one for the cuts, with two running numbers and nothing else held.

Pythonentry point: ways_to_split_array

def ways_to_split_array(readings):
    total = 0
    for value in readings:
        total += value
    front = 0
    sound = 0
    for at in range(len(readings) - 1):
        front += readings[at]
        if front >= total - front:
            sound += 1
    return sound

The obvious version

Take each cut in turn and add both pieces up from scratch, counting the cut when the front reaches the back. Costs the strip's length squared rather than one pass with a running front total.

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_ways_to_split_array(readings):
    n = len(readings)
    sound = 0
    for cut in range(n - 1):
        front = 0
        for at in range(cut + 1):
            front += readings[at]
        back = 0
        for at in range(cut + 1, n):
            back += readings[at]
        if front >= back:
            sound += 1
    return sound

How this problem was checked

Reference solution executed against 15 test cases — 15 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