LeetCode 2145 - Count the Hidden Sequences

The problem asks us to determine how many possible sequences of integers exist that match a given array of differences between consecutive elements, while staying within a specified inclusive range.

leetcodemediumarrayprefix-sum

LeetCode Problem 2145

Difficulty: 🟡 Medium
Topics: Array, Prefix Sum

Solution

Problem Understanding

The problem asks us to determine how many possible sequences of integers exist that match a given array of differences between consecutive elements, while staying within a specified inclusive range. Specifically, you are given an array differences of length n where each element represents the difference between consecutive elements of a hidden sequence of length n + 1. You are also given integers lower and upper that define the valid bounds for every element in this hidden sequence.

The goal is to count all valid sequences where the differences match and all elements are within [lower, upper]. Importantly, the sequence is not given; only the differences are. The first element of the sequence is flexible, as long as the entire sequence stays within bounds after applying the differences.

Constraints indicate that n can be as large as 10^5, which rules out naive enumeration of all possible sequences. Differences can be negative or positive and can also span the full range of -10^5 to 10^5. The bounds lower and upper also span the same range, including negative numbers. This means we need to handle potentially large numbers and edge cases where sequences could exceed limits immediately. Edge cases include sequences where differences oscillate greatly, sequences with a single element, or where lower == upper.

Approaches

A brute-force approach would iterate through every possible starting number x within [lower, upper], then reconstruct the sequence using the differences array. For each starting number, we check if all subsequent numbers remain within the range. This is correct but too slow because there may be up to 10^5 differences and up to 2 * 10^5 + 1 possible starting numbers. Its complexity is roughly O(n * (upper - lower + 1)), which is infeasible for large bounds.

The key insight for an optimal solution is that the valid sequence depends only on the minimum and maximum prefix sums of the differences. Let prefix[i] be the sum of the first i differences. Then the sequence elements can be represented as hidden[0] + prefix[i]. To stay within [lower, upper], we require:

lower <= hidden[0] + min_prefix <= hidden[i] <= hidden[0] + max_prefix <= upper

This reduces the problem to a simple range check: compute the minimum and maximum prefix sums and then determine how many starting numbers hidden[0] satisfy lower - min_prefix <= hidden[0] <= upper - max_prefix.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * (upper - lower + 1)) O(n) Try every possible starting value and validate sequence
Optimal O(n) O(1) Compute prefix min/max and determine valid starting range

Algorithm Walkthrough

  1. Initialize min_prefix and max_prefix to 0. These will track the minimum and maximum of the running sum of differences.
  2. Initialize a variable current_sum to 0, representing the prefix sum as we iterate.
  3. Iterate through the differences array. For each diff, update current_sum += diff. Update min_prefix = min(min_prefix, current_sum) and max_prefix = max(max_prefix, current_sum).
  4. After processing all differences, compute the valid range for the first element hidden[0] as [lower - min_prefix, upper - max_prefix].
  5. The number of valid sequences is the number of integers in this range, i.e., max(0, (upper - max_prefix) - (lower - min_prefix) + 1).

Why it works: The algorithm works because the relative offsets between elements are fixed by differences. Once we know the minimum and maximum offsets, the only factor controlling validity is the starting element. By constraining hidden[0] to keep all elements within [lower, upper], we ensure all sequences are valid. No other factors need checking.

Python Solution

from typing import List

class Solution:
    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:
        min_prefix = 0
        max_prefix = 0
        current_sum = 0
        
        for diff in differences:
            current_sum += diff
            min_prefix = min(min_prefix, current_sum)
            max_prefix = max(max_prefix, current_sum)
        
        # Calculate the valid range for hidden[0]
        valid_start_min = lower - min_prefix
        valid_start_max = upper - max_prefix
        
        return max(0, valid_start_max - valid_start_min + 1)

This implementation computes the running prefix sum and tracks the minimum and maximum observed sums. Then it directly calculates the range of valid starting numbers. The max(0, ...) ensures that if the range is invalid (empty), it returns 0.

Go Solution

func numberOfArrays(differences []int, lower int, upper int) int {
    minPrefix, maxPrefix := 0, 0
    currentSum := 0

    for _, diff := range differences {
        currentSum += diff
        if currentSum < minPrefix {
            minPrefix = currentSum
        }
        if currentSum > maxPrefix {
            maxPrefix = currentSum
        }
    }

    validStartMin := lower - minPrefix
    validStartMax := upper - maxPrefix
    result := validStartMax - validStartMin + 1
    if result < 0 {
        return 0
    }
    return result
}

The Go solution mirrors the Python logic. Go uses explicit conditionals for min/max updates, and the final calculation ensures a non-negative return.

Worked Examples

Example 1

Input: differences = [1, -3, 4], lower = 1, upper = 6

  1. Compute prefix sums: 1 → -2 → 2
  2. min_prefix = -2, max_prefix = 2
  3. Valid hidden[0] range: [1 - (-2), 6 - 2] = [3, 4]
  4. Count: 4 - 3 + 1 = 2

Result = 2

Example 2

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

  1. Prefix sums: 3 → -1 → 4 → 5 → 3
  2. min_prefix = -1, max_prefix = 5
  3. Valid hidden[0] range: [-4 - (-4), 5 - 5] = [-3, 0]

After computing prefix sums correctly, count valid starting numbers = 4

Example 3

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

  1. Prefix sums: 4 → -3 → -1
  2. min_prefix = -3, max_prefix = 4
  3. Valid hidden[0] range: [3 - (-3), 6 - 4] = [6, 2] → invalid range
  4. Count = 0

Complexity Analysis

Measure Complexity Explanation
Time O(n) Iterate through the differences array once
Space O(1) Only a few integer variables for prefix sums

The complexity is optimal because the entire computation depends only on a single pass through differences, without storing any additional arrays or sequences.

Test Cases

# Provided examples
assert Solution().numberOfArrays([1,-3,4], 1, 6) == 2  # Example 1
assert Solution().numberOfArrays([3,-4,5,1,-2], -4, 5) == 4  # Example 2
assert Solution().numberOfArrays([4,-7,2], 3, 6) == 0  # Example 3

# Edge cases
assert Solution().numberOfArrays([0,0,0], 1, 1) == 1  # All zeros, single valid start
assert Solution().numberOfArrays([100000], -100000, 100000) == 1  # Large positive diff
assert Solution().numberOfArrays([-100000], -100000, 100000) == 1  # Large negative diff
assert Solution().numberOfArrays([1,2,3], 10, 15) == 0  # No valid sequence
assert Solution().numberOfArrays([-1,-2,-3], -10, -5) == 0  # No valid sequence negative
Test Why
[1,-3,4], 1,6 Valid sequence count example
[3,-4,5,1,-2], -4,5 Multiple valid sequences
[4,-7,2], 3,6 No valid sequences
[0,0,0],1,1 Sequence with constant values
[100000],-100000,100000 Large positive difference
[-100000],-100000,100000 Large negative difference
[1,2,3],10,15 Sequence exceeds upper bound
[-1,-2,-3],-10,-5 Sequence below lower bound

Edge Cases

The first important edge case is when all differences are zero. The