2145. Count the Hidden Sequences

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

Approach 01:

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
  int numberOfArrays(vector<int>& differences, int lower, int upper) {
    vector<long> prefixSum(differences.size() + 1);

    for (int i = 0; i < differences.size(); ++i)
      prefixSum[i + 1] = prefixSum[i] + differences[i];

    const long maxPrefix = *max_element(prefixSum.begin(), prefixSum.end());
    const long minPrefix = *min_element(prefixSum.begin(), prefixSum.end());

    return max(0L, (upper - lower) - (maxPrefix - minPrefix) + 1);
  }
};

from typing import List

class Solution:
    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:
        prefixSum = [0]

        for diff in differences:
            prefixSum.append(prefixSum[-1] + diff)

        maxPrefix = max(prefixSum)
        minPrefix = min(prefixSum)

        return max(0, (upper - lower) - (maxPrefix - minPrefix) + 1)

Time Complexity:

• Prefix Sum Computation:

  Each element is processed once to compute the prefix sum → \( O(n) \)

• Finding Min and Max:

  We scan the prefix sum array twice → \( O(n) \)

• Total Time Complexity:

  \( O(n) \), where \( n \) is the size of the differences array.

Space Complexity:

• Prefix Sum Array:

  We store an additional array of size \( n + 1 \) → \( O(n) \)

• Total Space Complexity:

  \( O(n) \)