2145. Count the Hidden Sequences LeetCode Solution

In this guide, you will get 2145. Count the Hidden Sequences LeetCode Solution with the best time and space complexity. The solution to Count the Hidden Sequences problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Count the Hidden Sequences solution in C++
Count the Hidden Sequences solution in Java
Count the Hidden Sequences solution in Python
Additional Resources

2145. Count the Hidden Sequences LeetCode Solution image

Problem Statement of Count the Hidden Sequences

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].
You are further given two integers lower and upper that describe the inclusive range of values [lower, upper] that the hidden sequence can contain.

For example, given differences = [1, -3, 4], lower = 1, upper = 6, the hidden sequence is a sequence of length 4 whose elements are in between 1 and 6 (inclusive).

[3, 4, 1, 5] and [4, 5, 2, 6] are possible hidden sequences.
[5, 6, 3, 7] is not possible since it contains an element greater than 6.
[1, 2, 3, 4] is not possible since the differences are not correct.

Return the number of possible hidden sequences there are. If there are no possible sequences, return 0.

Example 1:

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]
Thus, we return 2.

Example 2:

Input: differences = [3,-4,5,1,-2], lower = -4, upper = 5
Output: 4
Explanation: The possible hidden sequences are:
– [-3, 0, -4, 1, 2, 0]
– [-2, 1, -3, 2, 3, 1]
– [-1, 2, -2, 3, 4, 2]
– [0, 3, -1, 4, 5, 3]
Thus, we return 4.

Example 3:

Input: differences = [4,-7,2], lower = 3, upper = 6
Output: 0
Explanation: There are no possible hidden sequences. Thus, we return 0.

Constraints:

n == differences.length
1 <= n <= 105
-105 <= differences[i] <= 105
-105 <= lower <= upper <= 105

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

2145. Count the Hidden Sequences LeetCode Solution in C++

class Solution {
 public:
  int numberOfArrays(vector<int>& differences, int lower, int upper) {
    // Starts from 0, so prefix[0] = 0.
    // Changing prefix[0] to any other number doesn't affect the answer.
    vector<long> prefix(differences.size() + 1);

    for (int i = 0; i < differences.size(); ++i)
      prefix[i + 1] += prefix[i] + differences[i];

    const long mx = ranges::max(prefix);
    const long mn = ranges::min(prefix);
    return max(0L, (upper - lower) - (mx - mn) + 1);
  }
};
/* code provided by PROGIEZ */

2145. Count the Hidden Sequences LeetCode Solution in Java

class Solution {
  public int numberOfArrays(int[] differences, int lower, int upper) {
    // Starts from 0, so prefix[0] = 0.
    // Changing prefix[0] to any other number doesn't affect the answer.
    long[] prefix = new long[differences.length + 1];

    for (int i = 0; i < differences.length; ++i)
      prefix[i + 1] += prefix[i] + differences[i];

    final long mx = Arrays.stream(prefix).max().getAsLong();
    final long mn = Arrays.stream(prefix).min().getAsLong();
    return (int) Math.max(0L, (upper - lower) - (mx - mn) + 1);
  }
}
// code provided by PROGIEZ

2145. Count the Hidden Sequences LeetCode Solution in Python

class Solution:
  def numberOfArrays(
      self,
      differences: list[int],
      lower: int,
      upper: int,
  ) -> int:
    prefix = list(itertools.accumulate(differences, initial=0))
    return max(0, (upper - lower) - (max(prefix) - min(prefix)) + 1)
 # code by PROGIEZ