# Count the Hidden Sequences
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-the-hidden-sequences)
Canonical: https://scaleengineer.com/dsa/problems/count-the-hidden-sequences
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array
**Companies:** [Zomato](https://scaleengineer.com/companies/zomato)
---
## Problem
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 = 6
**Output:** 2
**Explanation:** 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 = 5
**Output:** 4
**Explanation:** 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 = 6
**Output:** 0
**Explanation:** There are no possible hidden sequences. Thus, we return 0.

**Constraints:**

* `n == differences.length`
* `1 <= n <= 105`
* `-105 <= differences[i] <= 105`
* `-105 <= lower <= upper <= 105`

# Approaches
## Brute Force on the First Element
This approach recognizes that the entire hidden sequence is determined by its first element, `hidden[0]`. We can iterate through all possible values for `hidden[0]` within the given `[lower, upper]` range. For each potential starting value, we construct the complete sequence and check if all its elements fall within the `[lower, upper]` bounds. If they do, we count it as a valid sequence.
**Time:** O(N * (U - L)), where N is the length of `differences`, U is `upper`, and L is `lower`. We pre-calculate prefix sums in O(N). Then, we iterate up to `U - L + 1` times for the first element. For each choice, we validate the sequence of length N+1, which takes O(N) time. This leads to a total time complexity dominated by the nested loops. · **Space:** O(N), where N is the length of `differences`. This space is used to store the `relative_seq` (prefix sums).
**Pros:** Simple to understand and implement.; Correctly solves the problem for small ranges of `[lower, upper]`.
**Cons:** Extremely inefficient and will result in a 'Time Limit Exceeded' error for the given constraints.; The runtime depends on the magnitude of `lower` and `upper`, not just the size of the input array, making it unsuitable for large value ranges.
### Explanation
The core idea is that if we fix the value of `hidden[0]`, say to `h_0`, every other element `hidden[k]` is uniquely determined by the formula `hidden[k] = h_0 + sum(differences[0]...differences[k-1])`.

To implement this, we can first pre-calculate the prefix sums of the `differences` array. Let's call this `relative_seq`, where `relative_seq[k]` is the sum of the first `k` differences, and `relative_seq[0]` is 0.

Then, we loop through each possible integer value for `h_0` from `lower` to `upper`. In each iteration, we generate the full candidate sequence by adding `h_0` to each element of `relative_seq`. We then validate this candidate sequence by checking if all its elements are between `lower` and `upper`. A counter is incremented for each valid sequence found.

```java
class Solution {
    public int numberOfArrays(int[] differences, int lower, int upper) {
        int n = differences.length;
        long[] relativeSeq = new long[n + 1];
        relativeSeq[0] = 0;
        for (int i = 0; i < n; i++) {
            relativeSeq[i + 1] = relativeSeq[i] + differences[i];
        }

        int count = 0;
        // Iterate through all possible starting values
        for (long h0 = lower; h0 <= upper; h0++) {
            boolean isValid = true;
            // Check if this starting value creates a valid sequence
            for (int i = 0; i <= n; i++) {
                long element = h0 + relativeSeq[i];
                if (element < lower || element > upper) {
                    isValid = false;
                    break;
                }
            }
            if (isValid) {
                count++;
            }
        }
        return count;
    }
}
```
### Algorithm
- Create a `relative_seq` array of size `n+1` to store prefix sums. Initialize `relative_seq[0] = 0`.
- For `i` from 1 to `n`, calculate `relative_seq[i] = relative_seq[i-1] + differences[i-1]`.
- Initialize a counter `count = 0`.
- Iterate through each possible integer value for the first element, `h_0`, from `lower` to `upper`.
- For each `h_0`:
    - Assume the generated sequence is valid by setting a flag `isValid = true`.
    - Iterate from `k = 0` to `n` to check each element of the potential hidden sequence.
    - Calculate the current element: `current_element = h_0 + relative_seq[k]`.
    - If `current_element` is outside the `[lower, upper]` range, set `isValid = false` and break the inner loop.
- If `isValid` remains true after checking all elements, increment `count`.
- After checking all possible values for `h_0`, return `count`.

## Single Pass Prefix Sum Optimization
This highly efficient approach determines the number of valid sequences without constructing any of them. It leverages the insight that the entire hidden sequence is a translation of a relative sequence derived from the `differences` array. By finding the minimum and maximum values of this relative sequence, we can calculate the exact range of valid starting values for `hidden[0]` in constant time after a single pass.
**Time:** O(N), where N is the length of `differences`. We iterate through the array once to compute the min and max prefix sums. · **Space:** O(1). We only use a few variables to store the running sum, minimum sum, and maximum sum, regardless of the input size.
**Pros:** Extremely efficient with linear time and constant space complexity.; Scales perfectly for large inputs as specified by the constraints.; Avoids constructing any sequences, operating only on their range properties.
**Cons:** The logic is slightly more abstract and relies on a mathematical insight about the sequence's properties, which might be less intuitive than a direct brute-force approach.
### Explanation
Let the hidden sequence be `h = [h_0, h_1, ..., h_n]`. We can express each element `h_k` in terms of the first element `h_0`: `h_k = h_0 + (differences[0] + ... + differences[k-1])`. Let's define a relative sequence `P` where `P_k = (differences[0] + ... + differences[k-1])`, with `P_0 = 0`. The hidden sequence is then `[h_0 + P_0, h_0 + P_1, ..., h_0 + P_n]`.

For this sequence to be valid, every element must be in `[lower, upper]`. This means `lower <= h_0 + P_k <= upper` for all `k`. This gives us a range for `h_0`: `lower - P_k <= h_0 <= upper - P_k`.

To satisfy this for all `k`, `h_0` must be greater than or equal to the maximum of all `lower - P_k` values, and less than or equal to the minimum of all `upper - P_k` values. This simplifies to: `lower - min(P_k) <= h_0 <= upper - max(P_k)`.

Let `minP = min(P_0, ..., P_n)` and `maxP = max(P_0, ..., P_n)`. The number of possible integer values for `h_0` is `(upper - maxP) - (lower - minP) + 1`. We can find `minP` and `maxP` in a single pass through the `differences` array, calculating the prefix sums on the fly and updating the minimum and maximum values seen so far. It's crucial to use `long` for prefix sums to avoid integer overflow, as the cumulative sum can exceed the bounds of a 32-bit integer.

```java
class Solution {
    public int numberOfArrays(int[] differences, int lower, int upper) {
        long currentSum = 0;
        long minSum = 0;
        long maxSum = 0;

        for (int diff : differences) {
            currentSum += diff;
            minSum = Math.min(minSum, currentSum);
            maxSum = Math.max(maxSum, currentSum);
        }

        // The range of values in the relative sequence is (maxSum - minSum).
        // The range of allowed values is (upper - lower).
        // The number of ways to place the relative sequence within the allowed range is:
        // (upper - lower) - (maxSum - minSum) + 1
        
        long validRangeWidth = (long)upper - lower;
        long sequenceRangeWidth = maxSum - minSum;

        if (validRangeWidth < sequenceRangeWidth) {
            return 0;
        }

        long count = validRangeWidth - sequenceRangeWidth + 1;
        return (int) count;
    }
}
```
### Algorithm
- Initialize `long current_sum = 0`, `long min_sum = 0`, `long max_sum = 0`. These will track the prefix sum, and its minimum and maximum values respectively, starting from a base of 0.
- Iterate through each `diff` in the `differences` array.
- In each iteration, update the running sum: `current_sum += diff`.
- Update the minimum and maximum sums seen so far: `min_sum = Math.min(min_sum, current_sum)` and `max_sum = Math.max(max_sum, current_sum)`.
- After the loop, `min_sum` and `max_sum` hold the minimum and maximum values of the relative sequence.
- Calculate the range of the relative sequence: `sequenceRangeWidth = max_sum - min_sum`.
- Calculate the available range for values: `validRangeWidth = (long)upper - lower`.
- The number of possible valid sequences is the number of ways the sequence's range can fit into the allowed value range, which is `validRangeWidth - sequenceRangeWidth + 1`.
- If this count is negative, it means no sequence is possible. Therefore, return `max(0, count)`.

# Solutions
### Java

```java
class Solution {
public
  int numberOfArrays(int[] differences, int lower, int upper) {
    long num = 0, mi = 0, mx = 0;
    for (int d : differences) {
      num += d;
      mi = Math.min(mi, num);
      mx = Math.max(mx, num);
    }
    return Math.max(0, (int)(upper - lower - (mx - mi) + 1));
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numberOfArrays(vector<int> &differences, int lower, int upper) {
    long long num = 0, mi = 0, mx = 0;
    for (int &d : differences) {
      num += d;
      mi = min(mi, num);
      mx = max(mx, num);
    }
    return max(0, (int)(upper - lower - (mx - mi) + 1));
  }
};

```

### Python

```python
class Solution:
    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int: num = mi = mx = 0 for d in differences: num += d mi = min(mi, num) mx = max(mx, num) return max(0, upper - lower - (mx - mi) + 1)

```