2145. Count-The-Hidden-Sequences

A very math-y question, so many counts…

We can go through all of the differences, keeping track of the current value, the lowest value and the highest value.

Because we get a differences array, the current value keeps track of the relative difference of each number. Because we get the lower limit and the upper limit of our sequence, as we go through the current value, if at any point the current value is higher than lowest + (upper - lower), the sequence is not possible (it will not fit within those bounds). The same goes for when the current value is lower than highest - (upper - lower). So in these two cases, we can just immediately return 0.

Once we go through everything in the difference array, we can calculate the number of possible hidden subsequences based on the lowest value we have seen and the highest value we have seen.

class Solution(object):
    def numberOfArrays(self, differences, lower, upper):
        """
        :type differences: List[int]
        :type lower: int
        :type upper: int
        :rtype: int
        """
        count = 0
        max_diff = upper - lower

        curr = 0
        lowest = 0
        highest = 0

        for diff in differences:
            curr += diff
            if curr > lowest + max_diff:
                return 0
            if curr < highest - max_diff:
                return 0
            lowest = min(lowest, curr)
            highest = max(highest, curr)

        d = lowest - lower
        return upper - (highest - d) + 1

Time Complexity: O(n)

Space Complexity: O(1)

Time Taken: 8m 32s