[Leetcode] 2145. Count the Hidden Sequences

2145. Count the Hidden Sequences

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.

Constraints:

n == differences.length

1 <= n <= 10^5

-10^5 <= differences[i] <= 10^5

-10^5 <= lower <= upper <= 10^5 

Analysis:

This question is quick interesting, which needs some derivations. 

If check the first example carefully, this question is equivalent to ask for the total number of valid first element A0.

Since the values of all the elements should be in some range, then we just need to take care of the minimum and maximum of the elements. Or if the minimum and maximum elements valid, then all the rest should be valid as well.

So we can write down some equations first:

lower <= A0 <= upper        (1)

lower <= Amin <= upper    (2)

lower <= Amax <= upper    (3)

How to find the Amin and Amax?

The only thing we know is the diffs. So we can get the (Amin - A0) and (Amax - A0) by cumulating the diffs from the first one.

Once we get these two values, Dmin and Dmax, we can modify the equations above a little bit:

Amin - A0 = Dmin   =>  Amin = A0 + Dmin

Amax - A0 = Dmax  =>  Amax = A0 + Dmax

Then we can re-write (2) and (3)

lower <= A0 + Dmin <= upper    => lower - Dmin <= A0 <= upper - Dmin    (4)

lower <= A0 + Dmax <= upper   => lower - Dmax <= A0 <= upper - Dmax   (5)

Putting (1), (4) and (5) together, we can derive the valid range of A0,

max(lower, lower - Dmin, lower - Dmax)  <= A0 <= min(upper, upper - Dmin, upper - Dmax)

Since (lower - Dmin) is always no larger than (lower - Dmax), and (upper - Dmin) <= (upper - Dmax), the above range can be re-written as

max(lower, lower - Dmin) <= A0 <= min(upper, upper - Dmax).

The time complexity is O(n), and space complexity is O(1), where n is the number of elements.

See the code below:

class Solution {
public:
    int numberOfArrays(vector<int>& differences, int lower, int upper) {
        long sum = 0, mn = differences[0], mx = mn;
        for(auto &a : differences) {
            sum += a;
            mn = min(mn, sum);
            mx = max(mx, sum);
        }
        // d0: the first element
        // d_min: the min element exclude d0
        // d_max: the max element exclude d0
        // d_min - d0 = mn ---> d_min = d0 + mn
        // d_max - d0 = mx ---> d_max = d0 + mx
        // lower(L) <= di <= upper(R) for all i, so
        // (1) L <= d0 + mn <= R ---> L - mn <= d0 <= R - mn
        // (2) L <= d0 + mx <= R ---> L - mx <= d0 <= R - mx
        // (3) L <= d0 <= R
        // combine (1) - (3)
        // max(L-mn, L) <= d0 <= min(R, R - mx)
        // so question becomes: how many valid d0?
        long l = max((long)lower, lower - mn), r = min((long)upper, upper - mx);
        return r >= l ? r - l + 1 : 0;
    }
};