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.
This highly efficient approach determines the number of valid sequences without constructing any of them. It leverages the insight that the entire hidden sequence is a translation of a relative sequence derived from the differences array. By finding the minimum and maximum values of this relative sequence, we can calculate the exact range of valid starting values for hidden[0] in constant time after a single pass.
Algorithm
- Initialize
long current_sum = 0,long min_sum = 0,long max_sum = 0. These will track the prefix sum, and its minimum and maximum values respectively, starting from a base of 0. - Iterate through each
diffin thedifferencesarray. - In each iteration, update the running sum:
current_sum += diff. - Update the minimum and maximum sums seen so far:
min_sum = Math.min(min_sum, current_sum)andmax_sum = Math.max(max_sum, current_sum). - After the loop,
min_sumandmax_sumhold the minimum and maximum values of the relative sequence. - Calculate the range of the relative sequence:
sequenceRangeWidth = max_sum - min_sum. - Calculate the available range for values:
validRangeWidth = (long)upper - lower. - The number of possible valid sequences is the number of ways the sequence's range can fit into the allowed value range, which is
validRangeWidth - sequenceRangeWidth + 1. - If this count is negative, it means no sequence is possible. Therefore, return
max(0, count).
Walkthrough
Let the hidden sequence be h = [h_0, h_1, ..., h_n]. We can express each element h_k in terms of the first element h_0: h_k = h_0 + (differences[0] + ... + differences[k-1]). Let's define a relative sequence P where P_k = (differences[0] + ... + differences[k-1]), with P_0 = 0. The hidden sequence is then [h_0 + P_0, h_0 + P_1, ..., h_0 + P_n].
For this sequence to be valid, every element must be in [lower, upper]. This means lower <= h_0 + P_k <= upper for all k. This gives us a range for h_0: lower - P_k <= h_0 <= upper - P_k.
To satisfy this for all k, h_0 must be greater than or equal to the maximum of all lower - P_k values, and less than or equal to the minimum of all upper - P_k values. This simplifies to: lower - min(P_k) <= h_0 <= upper - max(P_k).
Let minP = min(P_0, ..., P_n) and maxP = max(P_0, ..., P_n). The number of possible integer values for h_0 is (upper - maxP) - (lower - minP) + 1. We can find minP and maxP in a single pass through the differences array, calculating the prefix sums on the fly and updating the minimum and maximum values seen so far. It's crucial to use long for prefix sums to avoid integer overflow, as the cumulative sum can exceed the bounds of a 32-bit integer.
class Solution { public int numberOfArrays(int[] differences, int lower, int upper) { long currentSum = 0; long minSum = 0; long maxSum = 0; for (int diff : differences) { currentSum += diff; minSum = Math.min(minSum, currentSum); maxSum = Math.max(maxSum, currentSum); } // The range of values in the relative sequence is (maxSum - minSum). // The range of allowed values is (upper - lower). // The number of ways to place the relative sequence within the allowed range is: // (upper - lower) - (maxSum - minSum) + 1 long validRangeWidth = (long)upper - lower; long sequenceRangeWidth = maxSum - minSum; if (validRangeWidth < sequenceRangeWidth) { return 0; } long count = validRangeWidth - sequenceRangeWidth + 1; return (int) count; }}Complexity
Time
O(N), where N is the length of `differences`. We iterate through the array once to compute the min and max prefix sums.
Space
O(1). We only use a few variables to store the running sum, minimum sum, and maximum sum, regardless of the input size.
Trade-offs
Pros
Extremely efficient with linear time and constant space complexity.
Scales perfectly for large inputs as specified by the constraints.
Avoids constructing any sequences, operating only on their range properties.
Cons
The logic is slightly more abstract and relies on a mathematical insight about the sequence's properties, which might be less intuitive than a direct brute-force approach.
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)); }}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)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.