leet code - 2145. Count the Hidden Sequences (medium, math)

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

 

 

 

 

 

differences 라는 리스트가 주어지고, 이는 어떤 숨겨진 시퀀수 hidden의 인접한 값들 간의 차이를 의미한다. 

 

즉, differences[i] = hidden[i+1] - hidden[i]

hidden 시퀀스의 첫 원소 x는 는 알 수 없으나, 그 이후는 x + prefix sum 으로 결정된다.

 

hidden[i] = x + prefix_sum[i-1] 형태로 표현 가능하다.

모든 hidden[i]는 [lower, upper]의 범위 안이여야 한다.

 

 

 

 

모든 hidden 값들은 x에 prefix sum을 더한 형태이기 때문에, 전체 시퀀스가 [lower, upper]를 벗어나지 않도록 만드는 x의 유효 범위를 계산할 수 있다.

 

class Solution:
    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:
        min_sum = 0
        max_sum = 0
        current = 0

        for diff in differences:
            current += diff
            min_sum = min(min_sum, current)
            max_sum = max(max_sum, current)
        
        min_start = lower - min_sum
        max_start = upper - max_sum

        if max_start < min_start:
            return 0
        else:
            return max_start - min_start + 1

 

x에 대한 정보는 없지만, differences 배열을 통해 누적합(prefix sum)을 만들 수 있다.

 

 

x의 범위는 lower ≤ x + prefix_sum[i] ≤ upper 이며

이는 다시

 

lower - min_start <= x

x <= upper - max_start 

로 유도 된다.

 

답은 이의 inclusive 한 범위 의 개수.

max_start - min_start + 1 이된다.