Show problems as
Classic problem #713MediumArrayBinary SearchSliding WindowPrefix Sum

Subarray Product Less Than K

Real-world version: Safe Stretches of the Filter Cascade
Tracked in this browser only
Read Subarray Product Less Than K on LeetCode(opens in a new tab)

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

Learn the pattern firstPrefix Sums · Arrays, animated step by step

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

More on the same topics