Skip to content

← leetcode

Count the Hidden Sequences

· Medium

LeetCode problem 2145

For this question, you just need to realise that the only important information to track is the minimum and maximum values, mn and mx, obtained while summing all the differences in the sequence.

This is because all the possible hidden sequences are just the same sequences of values just shifted a variable number of positions up or down; the answer is therefore just simply the number of positions you can shift up or down (which you can find by comparing upper-lower and mx-mn).

code

class Solution {
public:
    int numberOfArrays(vector<int>& differences, int lower, int upper) {
        long long mn = 0, mx = 0, current = 0;
        for (int &n : differences) {
            current += n;
            mn = min(mn, current);
            mx = max(mx, current);
        }
        return max((long long) 0, upper-lower-(mx-mn)+1);
    }
};

complexity

  • Time: O(n) where n is the length of differences
  • Space: O(1)

time taken

  • 4 minutes and 59 seconds