Count the hidden sequences

Array Prefix Sum

56.7% acceptance

Feb 25, 2026

1040

You are given a 0-indexed array of n integers differences, which describes the differences between each pair of consecutive integers of a hidden sequence of length (n + 1). More formally, call the hidden sequence hidden, then we have that differences[i] = hidden[i + 1] - hidden[i]. You are further given two integers lower and upper that describe the inclusive range of values [lower, upper] that the hidden sequence can contain. Return the number of possible hidden sequences there are. If there are no possible sequences, return 0.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn number_of_arrays(differences: Vec<i32>, lower: i32, upper: i32) -> i32 {
    let mut cur = 0i64;
    let (mut mn, mut mx) = (0i64, 0i64);
    for d in differences {
      cur += d as i64;
      mn = mn.min(cur);
      mx = mx.max(cur);
    }
    // hidden[0] must satisfy:
    // lower <= hidden[0] + mn  =>  hidden[0] >= lower - mn
    // hidden[0] + mx <= upper  =>  hidden[0] <= upper - mx
    // count = (upper - mx) - (lower - mn) + 1 = upper - lower - (mx - mn) + 1
    let count = (upper - lower) as i64 - (mx - mn) + 1;
    count.max(0) as i32
  }
}