Formatted question description: https://leetcode.ca/all/2145.html

# 2145. Count the Hidden Sequences (Medium)

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.

- For example, given
`differences = [1, -3, 4]`

,`lower = 1`

,`upper = 6`

, the hidden sequence is a sequence of length`4`

whose elements are in between`1`

and`6`

(**inclusive**).`[3, 4, 1, 5]`

and`[4, 5, 2, 6]`

are possible hidden sequences.`[5, 6, 3, 7]`

is not possible since it contains an element greater than`6`

.`[1, 2, 3, 4]`

is not possible since the differences are not correct.

Return *the number of possible hidden sequences there are.* If there are no possible sequences, return

`0`

.

**Example 1:**

Input:differences = [1,-3,4], lower = 1, upper = 6Output:2Explanation:The possible hidden sequences are: - [3, 4, 1, 5] - [4, 5, 2, 6] Thus, we return 2.

**Example 2:**

Input:differences = [3,-4,5,1,-2], lower = -4, upper = 5Output:4Explanation:The possible hidden sequences are: - [-3, 0, -4, 1, 2, 0] - [-2, 1, -3, 2, 3, 1] - [-1, 2, -2, 3, 4, 2] - [0, 3, -1, 4, 5, 3] Thus, we return 4.

**Example 3:**

Input:differences = [4,-7,2], lower = 3, upper = 6Output:0Explanation:There are no possible hidden sequences. Thus, we return 0.

**Constraints:**

`n == differences.length`

`1 <= n <= 10`

^{5}`-10`

^{5}<= differences[i] <= 10^{5}`-10`

^{5}<= lower <= upper <= 10^{5}

## Solution 1.

Assume `hidden[0] = 0`

.

We can get all `hidden[i+1] = hidden[i] + diff[i]`

.

The `hidden`

array forms a polyline. Assume the max/min values are `max`

/`min`

.

By changing `hidden[0]`

, we can shift this range up or down.

If we snap `max`

to `upper`

, we move up by `upper - max`

steps. Then the number of possible of hidden sequences is `min + (upper - max) - lower + 1`

.

Another way to think about it:

```
// OJ: https://leetcode.com/problems/count-the-hidden-sequences/
// Time: O(N)
// Space: O(1)
class Solution {
public:
int numberOfArrays(vector<int>& A, int lower, int upper) {
long sum = 0, mn = 0, mx = 0;
for (int n : A) {
sum += n;
mn = min(mn, sum);
mx = max(mx, sum);
}
return max(0L, mn - mx + upper - lower + 1);
}
};
```

## Discuss

https://leetcode.com/problems/count-the-hidden-sequences/discuss/1709710/C%2B%2B-One-pass-O(N)-time