Problem of The Day: Count the Hidden Sequences

Problem Statement

leetcode problem link

Brute Force [TLE]

class Solution:
    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:
        res = 0
        for i in range(lower, upper + 1):
            hidden_val = i
            for x in differences:
                next_hidden_val = x + hidden_val
                if not (lower <= next_hidden_val <= upper):
                    break
                hidden_val = next_hidden_val
            else:
                res += 1
        return res

Editorial

Approach: Determine the Difference Between the Hidden Array’s Upper and Lower Bounds

class Solution:
    def numberOfArrays(
        self, differences: List[int], lower: int, upper: int
    ) -> int:
        x = y = cur = 0
        for d in differences:
            cur += d
            x = min(x, cur)
            y = max(y, cur)
            if y - x > upper - lower:
                return 0
        return (upper - lower) - (y - x) + 1