Count the Hidden Sequences Python Solution

LeetCode 2145, Medium. Topics: Array, Prefix Sum. View on LeetCode. Generate this problem as a practice environment: tested reference solution, 12 parametrized pytest cases, and a playground notebook:

lcpy gen -n 2145   # by problem number
lcpy gen -s count_the_hidden_sequences   # by problem name

Problem

You are given a 0-indexed array differences of n integers, which describes the differences between each pair of consecutive integers of a hidden sequence of length n + 1. You are also given two integers lower and upper that describe the inclusive range of values that the hidden sequence can contain. Return the number of possible hidden sequences. If there are no possible sequences, return 0.

Examples

Input: differences = [1,-3,4], lower = 1, upper = 6
Output: 2
Explanation: The possible hidden sequences are:
- [3, 4, 1, 5]
- [4, 5, 2, 6]

Input: differences = [3,-4,5,1,-2], lower = -4, upper = 5
Output: 4

Input: differences = [4,-7,2], lower = 3, upper = 6
Output: 0

Constraints

n == differences.length
1 <= n <= 10^5
-10^5 <= differences[i] <= 10^5
-10^5 <= lower <= upper <= 10^5

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(n)
    # Space: O(1)
    def number_of_arrays(self, differences: list[int], lower: int, upper: int) -> int:
        offset = 0
        min_offset = 0
        max_offset = 0

        for difference in differences:
            offset += difference
            min_offset = min(min_offset, offset)
            max_offset = max(max_offset, offset)

        possible = (upper - lower) - (max_offset - min_offset) + 1
        return max(0, possible)

Complexity

Time	Space
O(n)	O(1)

Welcome

Getting Started

Practice

CLI

Catalog

Contributing

Troubleshooting

Count the Hidden Sequences Python Solution

Problem

Examples

Constraints

Solution

Complexity

Tags

​Problem

​Examples

​Constraints

​Solution

​Complexity

​Tags

Problem

Examples

Constraints

Solution

Complexity

Tags