Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2145.html
2145. Count the Hidden Sequences (Medium)
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}
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/countthehiddensequences/ // 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); } };

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) ############ # 2145. Count the Hidden Sequences # https://leetcode.com/problems/countthehiddensequences/ class Solution: def numberOfArrays(self, differences: List[int], lower: int, upper: int) > int: mmax = mmin = s = 0 for x in differences: s += x mmax = max(mmax, s) mmin = min(mmin, s) return max(0, (upper  lower)  (mmax  mmin) + 1)

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

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) } func max(a, b int) int { if a > b { return a } return b } func min(a, b int) int { if a < b { return a } return b }
Discuss
https://leetcode.com/problems/countthehiddensequences/discuss/1709710/C%2B%2BOnepassO(N)time