Count the Hidden Sequences

Medium
1857.

Count the Hidden Sequences

Count the Hidden Sequences is a medium coding problem on arrays and prefix sum, asked in Amazon and Google interviews.

A hidden sequence of n + 1 integers was recorded only by its consecutive differences: differences[i] = hidden[i + 1] - hidden[i]. You also know every value of the hidden sequence lies in the inclusive range [lower, upper].

Return how many hidden sequences are possible. If none is, return 0.

Example 1

Input
differences = [1,-3,4], lower = 1, upper = 6
Output
2
Explanation
[3,4,1,5] and [4,5,2,6] both fit in [1, 6].

Example 2

Input
differences = [3,-4,5,1,-2], lower = -4, upper = 5
Output
4
Explanation
Starting values -3, -2, -1 and 0 all keep the sequence within [-4, 5].

Example 3

Input
differences = [4,-7,2], lower = 3, upper = 6
Output
0
Explanation
The sequence swings across 7 values, but the range only holds 4.

Constraints

  • n == differences.length
  • 1 <= n <= 10^5
  • -10^5 <= differences[i] <= 10^5
  • -10^5 <= lower <= upper <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} differences
 * @param {number} lower
 * @param {number} upper
 * @return {number}
 */
var numberOfArrays = function(differences, lower, upper) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count the Hidden Sequences — Solution in Python, Java & C++

Count the Hidden Sequences solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Count the Hidden Sequences is a medium coding problem on arrays and prefix sum, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Prefix Sum
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A hidden sequence of n + 1 integers was recorded only by its consecutive differences: differences[i] = hidden[i + 1] - hidden[i]. You also know every value of the hidden sequence lies in the inclusive range [lower, upper].

Return how many hidden sequences are possible. If none is, return 0.

Example 1

Input: differences = [1,-3,4], lower = 1, upper = 6
Output: 2
Explanation: [3,4,1,5] and [4,5,2,6] both fit in [1, 6].

Example 2

Input: differences = [3,-4,5,1,-2], lower = -4, upper = 5
Output: 4
Explanation: Starting values -3, -2, -1 and 0 all keep the sequence within [-4, 5].

Example 3

Input: differences = [4,-7,2], lower = 3, upper = 6
Output: 0
Explanation: The sequence swings across 7 values, but the range only holds 4.

Constraints

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

Hints for Count the Hidden Sequences

  1. Hint 1

    Once the first value is fixed, the whole sequence is fixed. So count the valid first values.

  2. Hint 2

    Shift the sequence to start at 0 and track its minimum lo and maximum hi along the way (including the starting 0).

  3. Hint 3

    The sequence starting at x spans [x + lo, x + hi]; it fits iff lower - lo <= x <= upper - hi. Count the integers in that range.

How to solve Count the Hidden Sequences

The differences fix the shape of the sequence; only the starting value is free. The shape occupies a band of width hi - lo, and the number of positions of that band inside [lower, upper] is (upper - lower) - (hi - lo) + 1, or zero if it does not fit.

Approach

  1. Walk the prefix sums starting from 0, tracking the minimum lo and maximum hi (both start at 0).
  2. Return max(0, (upper - lower) - (hi - lo) + 1).
  3. (Optional) stop early once hi - lo > upper - lower — the answer is already 0.

Why it works

With start x the sequence's values are x + s for each prefix sum s, so its minimum is x + lo and maximum x + hi. All values lie in [lower, upper] iff x + lo >= lower and x + hi <= upper, i.e. x in [lower - lo, upper - hi], which contains (upper - hi) - (lower - lo) + 1 integers when non-negative.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Prefix sums reach 10^10 in magnitude — use 64-bit integers (or stop early once the band is wider than the range).
  • Include the starting value 0 in lo and hi.

Reference solution

Python

from typing import List

def numberOfArrays(differences: List[int], lower: int, upper: int) -> int:
    cur = lo = hi = 0
    for d in differences:
        cur += d
        lo = min(lo, cur)
        hi = max(hi, cur)
    return max(0, (upper - lower) - (hi - lo) + 1)

Java

public static int numberOfArrays(int[] differences, int lower, int upper) {
    long cur = 0, lo = 0, hi = 0;
    for (int d : differences) {
        cur += d;
        lo = Math.min(lo, cur);
        hi = Math.max(hi, cur);
    }
    return (int) Math.max(0L, (long) (upper - lower) - (hi - lo) + 1);
}

C++

int numberOfArrays(vector<int>& differences, int lower, int upper) {
    long long cur = 0, lo = 0, hi = 0;
    for (int d : differences) {
        cur += d;
        lo = min(lo, cur);
        hi = max(hi, cur);
    }
    return (int) max(0LL, (long long) (upper - lower) - (hi - lo) + 1);
}

JavaScript

var numberOfArrays = function(differences, lower, upper) {
    var cur = 0, lo = 0, hi = 0;
    for (var i = 0; i < differences.length; i++) {
        cur += differences[i];
        if (cur < lo) lo = cur;
        if (cur > hi) hi = cur;
    }
    return Math.max(0, (upper - lower) - (hi - lo) + 1);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Prefix Sum