MediumNo. 2145
Count the Hidden Sequences — LeetCode 2145 Python Solution
- Pattern
- Prefix Sum
- Topics
- Array, Prefix Sum
- Reading time
- 2 min
- Source
- leetcode.com
The problem
You are given a 0-indexed array of n integers differences, which describes the differences between each pair of consecutive integers of a hidden sequence of length (n + 1). More formally, call the hidden sequence hidden, then we have that differences[i] = hidden[i + 1] - hidden[i].
Example
- Input
- differences = [1,-3,4], lower = 1, upper = 6
- Output
- 2
- Explanation
- The possible hidden sequences are:
Python solution
class Solution:
def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:
x = mi = mx = 0
for d in differences:
x += d
mi = min(mi, x)
mx = max(mx, x)
return max(upper - lower - (mx - mi) + 1, 0)Complexity
- Time
- O(n)where n is the length of the array differences
- Space · auxiliary
- O(1)
Pattern: Prefix Sum
Precompute running totals once so any range query becomes a single subtraction. LeetCode 2145. Count the Hidden Sequences is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Prefix Sum.
The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0238 | Product of Array Except Self | Medium |
| 0303 | Range Sum Query - Immutable | Easy |
| 0304 | Range Sum Query 2D - Immutable | Medium |
| 0724 | Find Pivot Index | Easy |
| 0798 | Smallest Rotation with Highest Score | Hard |
| 0848 | Shifting Letters | Medium |
Frequently asked questions
- How hard is LeetCode 2145. Count the Hidden Sequences?
LeetCode 2145. Count the Hidden Sequences is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2145. Count the Hidden Sequences?
The Python solution on this page runs in O(n), where n is the length of the array \textit{differences}.
- What is the space complexity of LeetCode 2145. Count the Hidden Sequences?
The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 2145. Count the Hidden Sequences cover?
LeetCode 2145. Count the Hidden Sequences is tagged Array and Prefix Sum on LeetCode.