Count the Hidden Sequences

main.md

Question

Approach

I started with an initial number x, each subsequent number in the sequence is just x plus the running total (or prefix sum) of the differences. So, the sequence becomes x, x + diff1, x + diff1 + diff2, and so on.

To ensure the entire hidden sequence stays within the bounds of [lower, upper], I tracked the minimum and maximum values that the prefix sums could reach. These represent how low or high the hidden sequence can potentially go relative to the starting number. To guarantee that the entire sequence remains within the valid range, the starting number x must be large enough to lift the lowest point above lower, and small enough to keep the highest point below upper.

So I calculated the valid range of starting values using those bounds. The number of valid sequences then came down to counting how many integers x satisfy that condition. If the range was invalid (i.e., no such x exists), I returned 0. Otherwise, the count of valid x values directly gave me the number of possible hidden sequences.

Implementation

class Solution:
    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:
        total = 0
        min_sum = 0
        max_sum = 0
        curr = 0

        for d in differences:
            curr += d
            min_sum = min(min_sum, curr)
            max_sum = max(max_sum, curr)

        return max(0, (upper - max_sum) - (lower - min_sum) + 1)

Complexities

• Time: O(n)
• Space: O(1)