Leetcode 2145 Count the hidden sequences

The problem asks us to find the number of possible hidden sequences of length n+1 where all the values are in the range [lower, upper]. Moreover, sequence must follow the pattern:

seq[i] = seq[i-1] + diffs[i-1]

Our aim is just to figure out the max value and min value of the seq[0] such that all values must be in [lower, upper] range. By using the prefix sum approach, we figure out the min and max values of the sequence. Now, calculating minimum and maximum values for seq[0] is all about the following mathematical equation:

Since, seq[i] = seq[0] + prefixSum[i-1] seq[0] + minPrefix >= lower seq[0] + maxPrefix <= upper

And total sequences = maxSeq0 — minSeq0 + 1

class Solution {
public:
    int numberOfArrays(vector<int>& diffs, int lower, int upper) {
        long minPrefix = 0, maxPrefix = 0, sum = 0;

        // prefix sum
        for (int diff : diffs) {
            sum += diff;
            minPrefix = min(minPrefix, sum);
            maxPrefix = max(maxPrefix, sum);
        }

        long mini = lower - minPrefix;
        long maxi = upper - maxPrefix;

        return max(0L, maxi - mini + 1);
    }
};

• T.C. = O(n)
• S.C. = O(1)