Count the Hidden Sequences — Solution in Python, Java & C++
Count the Hidden Sequences solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Count the Hidden Sequences is a medium coding problem on arrays and prefix sum, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Prefix Sum
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A hidden sequence of n + 1 integers was recorded only by its consecutive differences: differences[i] = hidden[i + 1] - hidden[i]. You also know every value of the hidden sequence lies in the inclusive range [lower, upper].
Return how many hidden sequences are possible. If none is, return 0.
Example 1
Input: differences = [1,-3,4], lower = 1, upper = 6
Output: 2
Explanation: [3,4,1,5] and [4,5,2,6] both fit in [1, 6].
Example 2
Input: differences = [3,-4,5,1,-2], lower = -4, upper = 5
Output: 4
Explanation: Starting values -3, -2, -1 and 0 all keep the sequence within [-4, 5].
Example 3
Input: differences = [4,-7,2], lower = 3, upper = 6
Output: 0
Explanation: The sequence swings across 7 values, but the range only holds 4.
Constraints
n == differences.length1 <= n <= 10^5-10^5 <= differences[i] <= 10^5-10^5 <= lower <= upper <= 10^5
Hints for Count the Hidden Sequences
Hint 1
Once the first value is fixed, the whole sequence is fixed. So count the valid first values.
Hint 2
Shift the sequence to start at
0and track its minimumloand maximumhialong the way (including the starting0).Hint 3
The sequence starting at
xspans[x + lo, x + hi]; it fits ifflower - lo <= x <= upper - hi. Count the integers in that range.
How to solve Count the Hidden Sequences
The differences fix the shape of the sequence; only the starting value is free. The shape occupies a band of width hi - lo, and the number of positions of that band inside [lower, upper] is (upper - lower) - (hi - lo) + 1, or zero if it does not fit.
Approach
- Walk the prefix sums starting from
0, tracking the minimumloand maximumhi(both start at0). - Return
max(0, (upper - lower) - (hi - lo) + 1). - (Optional) stop early once
hi - lo > upper - lower— the answer is already0.
Why it works
With start x the sequence's values are x + s for each prefix sum s, so its minimum is x + lo and maximum x + hi. All values lie in [lower, upper] iff x + lo >= lower and x + hi <= upper, i.e. x in [lower - lo, upper - hi], which contains (upper - hi) - (lower - lo) + 1 integers when non-negative.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Prefix sums reach
10^10in magnitude — use 64-bit integers (or stop early once the band is wider than the range). - Include the starting value
0inloandhi.
Reference solution
Python
from typing import List
def numberOfArrays(differences: List[int], lower: int, upper: int) -> int:
cur = lo = hi = 0
for d in differences:
cur += d
lo = min(lo, cur)
hi = max(hi, cur)
return max(0, (upper - lower) - (hi - lo) + 1)Java
public static int numberOfArrays(int[] differences, int lower, int upper) {
long cur = 0, lo = 0, hi = 0;
for (int d : differences) {
cur += d;
lo = Math.min(lo, cur);
hi = Math.max(hi, cur);
}
return (int) Math.max(0L, (long) (upper - lower) - (hi - lo) + 1);
}C++
int numberOfArrays(vector<int>& differences, int lower, int upper) {
long long cur = 0, lo = 0, hi = 0;
for (int d : differences) {
cur += d;
lo = min(lo, cur);
hi = max(hi, cur);
}
return (int) max(0LL, (long long) (upper - lower) - (hi - lo) + 1);
}JavaScript
var numberOfArrays = function(differences, lower, upper) {
var cur = 0, lo = 0, hi = 0;
for (var i = 0; i < differences.length; i++) {
cur += differences[i];
if (cur < lo) lo = cur;
if (cur > hi) hi = cur;
}
return Math.max(0, (upper - lower) - (hi - lo) + 1);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Prefix Sum