Count the Hidden Sequences

Problem

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 length 4 whose elements are in between 1 and 6 (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 than 6.
- [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.

Examples

Example 1:

1
2
3
4
5
6


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:

1
2
3
4
5
6
7
8


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:

1
2
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

Method 1 - Using Prefix sum

The differences array tells you the change in values for a sequence. Starting with some initial value (let’s call it hidden[0]), you can compute all subsequent values in the sequence using the differences.
You are tasked with finding how many valid sequences exist, such that the elements are within the range [lower, upper]. Here are key insights:
The sequence is fully determined if we know hidden[0] since all subsequent values can be calculated using the differences array.
Valid sequences have all values within [lower, upper]. Thus, we need to identify the range of values for hidden[0] that does not produce values outside [lower, upper].

Here is the approach:

Compute cumulative sums from the differences array to find the largest and smallest values in the generated sequence relative to hidden[0].
Find the range for hidden[0] that ensures all values remain within [lower, upper].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution {

    public int numberOfArrays(int[] differences, int lower, int upper) {
        int minPossible = 0, maxPossible = 0; // Tracking cumulative sum range
        int currSum = 0;

        for (int d : differences) {
            currSum += d;
            minPossible = Math.min(minPossible, currSum);
            maxPossible = Math.max(maxPossible, currSum);

            if (maxPossible - minPossible > upper - lower) {
                return 0;
            }
        }

        // Valid starting values for hidden[0]:
        return upper - maxPossible - (lower - minPossible) + 1;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution:
    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:
        min_val, max_val = 0, 0  # Tracks cumulative sum range
        curr_sum = 0
        
        for diff in differences:
            curr_sum += diff
            min_val = min(min_val, curr_sum)
            max_val = max(max_val, curr_sum)
            if max_val - min_val > upper - lower:
                return 0
        
        # Calculate the range of valid starting values for hidden[0]
        return upper - max_val - (lower - min_val) + 1

Complexity

⏰ Time complexity: O(n) where n is the length of the differences array (cumulative sums involve a single traversal).
🧺 Space complexity: O(1) as we only use a few variables for computation.

Problem#

Examples#

Solution#

Method 1 - Using Prefix sum#

Code#

Complexity#