Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

The differences determine every element relative to the first. All possible hidden arrays are vertical shifts of one prefix-sum sequence. A shift is valid exactly when its smallest value is at least lower and its largest value is at most upper.

Approach

Build the relative sequence starting at zero and successively adding each difference. Find its minimum and maximum. Valid starting shifts range from lower - minimum through upper - maximum, inclusive, giving (upper - lower + 1) - (maximum - minimum) choices. Return that count if positive, otherwise zero. Including the initial zero ensures the first hidden element is constrained along with the later ones.

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

        for d in differences:
            hidden.append(hidden[-1] + d)

        mn = min(hidden)
        mx = max(hidden)
        res = (upper - lower + 1) - (mx - mn)

        return res if res > 0 else 0

Complexity analysis

Let d = differences.length. Time: O(d) to build and scan the implied prefix values. Auxiliary space: O(d) for that prefix sequence.