Count the Hidden Sequences
MedPrompt
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 length4whose elements are in between1and6(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.length1 <= n <= 105-105 <= differences[i] <= 105-105 <= lower <= upper <= 105
Approaches
2 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Create a
relative_seqarray of sizen+1to store prefix sums. Initializerelative_seq[0] = 0. - For
ifrom 1 ton, calculaterelative_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, fromlowertoupper. - For each
h_0:- Assume the generated sequence is valid by setting a flag
isValid = true. - Iterate from
k = 0tonto check each element of the potential hidden sequence. - Calculate the current element:
current_element = h_0 + relative_seq[k]. - If
current_elementis outside the[lower, upper]range, setisValid = falseand break the inner loop.
- Assume the generated sequence is valid by setting a flag
- If
isValidremains true after checking all elements, incrementcount. - After checking all possible values for
h_0, returncount.
Walkthrough
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.
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; }}Complexity
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).
Trade-offs
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
lowerandupper, not just the size of the input array, making it unsuitable for large value ranges.
Solutions
Solution
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)); }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.