0139MediumArrayBinary SearchSliding WindowPrefix Sum

Safe Stretches of the Filter Cascade

Tracked in this browser only

Trains the technique from

LeetCode 713Subarray Product Less Than K

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.

An optical bench holds a row of amplifying filters. Filter i multiplies the beam by the whole number factors[i], so a stretch of neighbouring filters multiplies it by the product of their values.

A stretch is safe when that product stays strictly below ceiling. Count the safe stretches of one or more neighbouring filters. Stretches that begin or end at different positions count separately, even when they scale the beam by the same amount.

Every factor is at least 1, so a ceiling of 0 leaves nothing safe and the count is 0.

Examples

Example 1

Input: factors = [3, 1, 4, 2], ceiling = 12
Output: 8

All four single filters are safe, as are the neighbouring pairs [3, 1], [1, 4] and [4, 2] and the triple [1, 4, 2]. The two stretches holding both 3 and 4 reach 12 or beyond, so they are out.

Example 2

Input: factors = [9, 9, 9], ceiling = 9
Output: 0

One filter on its own already scales the beam by 9, which is not below the ceiling, so no stretch qualifies.

Example 3

Input: factors = [10, 5, 2, 6], ceiling = 100
Output: 8

The four single filters, the pairs [10, 5], [5, 2] and [2, 6], and the triple [5, 2, 6] stay under 100. Anything holding 10, 5 and 2 together lands on 100 exactly, which is already too high.

Constraints

1 <= factors.length <= 3 * 10^4
1 <= factors[i] <= 1000
0 <= ceiling <= 10^6

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_safe_stretches(factors: list[int], ceiling: int) -> int:

Java

public int countSafeStretches(int[] factors, int ceiling)

The intended approach

Time O(n)Space O(1)

Slide a window over the row while holding the product of the filters inside it. After taking in the filter on the right, divide the leftmost filters out until the product drops below the ceiling; every window ending here and starting at or after the left edge is then safe, which adds the window length to the tally. Because each factor is at least 1 the product never shrinks as the window grows, so both edges only ever move forward. A ceiling of 0 or 1 admits nothing and is answered up front.

Pythonentry point: count_safe_stretches

def count_safe_stretches(factors, ceiling):
    if ceiling <= 1:
        return 0
    total = 0
    product = 1
    left = 0
    for right in range(len(factors)):
        product *= factors[right]
        while product >= ceiling:
            product //= factors[left]
            left += 1
        total += right - left + 1
    return total

The obvious version

For every starting position, extend to the right and multiply as you go, counting each stretch whose running product stays under the ceiling. Quadratic and no window at all.

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_safe(factors, ceiling):
    n = len(factors)
    total = 0
    for i in range(n):
        product = 1
        for j in range(i, n):
            product *= factors[j]
            if product < ceiling:
                total += 1
    return total

How this problem was checked

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