Count the Hidden Sequences

Leetcode Problem:

• Count the Hidden Sequences

Summary

• This problem is about finding the number of possible hidden sequences given the differences between consecutive integers, a lower bound, and an upper bound.

Approach

• The approach used is to calculate the maximum and minimum possible values of the hidden sequence by summing the differences, then checking if the difference between the maximum and minimum possible values is within the given range
• If it is, the number of possible sequences is the difference between the upper and lower bounds plus one.

Complexity

• O(n), where n is the number of differences

Explanation

• The solution iterates through the differences, calculating the cumulative sum and updating the maximum and minimum possible values
• It then checks if the difference between the maximum and minimum possible values is within the given range
• If it is, the number of possible sequences is calculated by subtracting the difference from the difference between the upper and lower bounds and adding one.

Solution Code:

class Solution {
public:
    int numberOfArrays(vector& differences, int lower, int upper) {
        long long maxV = 0;
        long long minV = 0;
        long long cur = 0;
        for(int i = 0; i < differences.size(); i++){
            cur += differences[i];
            maxV = max(maxV, cur);
            minV = min(minV, cur);
        }
        int diff1 = maxV - minV;
        int diff2 = upper - lower;
        if(diff1 > diff2){
            return 0;
        } else{
            return diff2 - diff1 + 1;
        }
    }
};