Welcome to Subscribe On Youtube
2145. Count the Hidden Sequences
Description
You are given a 0indexed 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 length4
whose elements are in between1
and6
(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 than6
.[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 <= 10^{5}
10^{5} <= differences[i] <= 10^{5}
10^{5} <= lower <= upper <= 10^{5}
Solutions

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)); } }

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)); } };

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)

func numberOfArrays(differences []int, lower int, upper int) int { num, mi, mx := 0, 0, 0 for _, d := range differences { num += d mi = min(mi, num) mx = max(mx, num) } return max(0, upperlower(mxmi)+1) }