Problem Summary

You are given an integer array differences and two integers lower and upper.

There exists a hidden array nums of length n = differences.length + 1 such that:

nums[i] - nums[i - 1] = differences[i - 1]

Your task is to return how many possible hidden arrays nums exist such that every element in nums is within the inclusive range:

lower ≤ nums[i] ≤ upper

If no such array exists, return 0.

Example
Input:

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

Hidden sequence must satisfy:

nums[1] = nums[0] + 1
nums[2] = nums[1] - 3
nums[3] = nums[2] + 4

We must count how many nums[0] values lead to a valid full sequence.

---

Approach (Simple English)

Let the hidden array be:

nums[0], nums[1], nums[2], ..., nums[n]

We do not know nums[0].
But we know all differences:

nums[1] = nums[0] + differences[0]
nums[2] = nums[1] + differences[1]
...

So every value in nums depends linearly on nums[0].

Key Idea

Compute all cumulative sums relative to nums[0]:

Let:

prefix[0] = 0
prefix[i] = differences[0] + differences[1] + ... + differences[i-1]

Then:

nums[i] = nums[0] + prefix[i]

To keep all nums[i] within [lower, upper]:

lower ≤ nums[0] + prefix[i] ≤ upper

Rearrange:

lower - prefix[i] ≤ nums[0] ≤ upper - prefix[i]

All these constraints together define a range of valid nums[0] values.

Intersect all ranges to find the allowed interval for nums[0].

Why This Works

All values depend only on nums[0], so this is effectively a single-variable inequality problem.
Count the number of integers in the intersection range.

---

Steps

1. Compute prefix array (cumulative sum of differences).
2. For each index i, compute:
   • minimum allowed nums[0] = lower - prefix[i]
   • maximum allowed nums[0] = upper - prefix[i]
3. Track:
   • globalLow = max(all lower bounds)
   • globalHigh = min(all upper bounds)
4. If globalLow > globalHigh, no valid nums array exists → return 0.
5. Otherwise the answer is:

globalHigh - globalLow + 1

---

Java Code (Optimal O(n) Solution)

class Solution {
    public int numberOfArrays(int[] differences, int lower, int upper) {
        long prefix = 0;

        long globalLow = lower; 
        long globalHigh = upper;

        for (int diff : differences) {
            prefix += diff;

            long minValue = lower - prefix;
            long maxValue = upper - prefix;

            globalLow = Math.max(globalLow, minValue);
            globalHigh = Math.min(globalHigh, maxValue);
        }

        if (globalLow > globalHigh) return 0;

        return (int)(globalHigh - globalLow + 1);
    }
}

---

Dry Run

Input:

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

Compute prefix values:

i=0: prefix = 1
range for nums[0]: [lower - prefix, upper - prefix] = [1 - 1, 6 - 1] = [0, 5]

i=1: prefix = -2
range: [1 - (-2), 6 - (-2)] = [3, 8]

i=2: prefix = 2
range: [1 - 2, 6 - 2] = [-1, 4]

Intersect the ranges:

• Start with [1, 6]
• Intersect with [0, 5] → [1, 5]
• Intersect with [3, 8] → [3, 5]
• Intersect with [-1, 4] → [3, 4]

Final allowed nums[0] range = [3, 4]

Number of valid nums arrays = 4 - 3 + 1 = 2

---

Complexity Analysis

Time Complexity:
O(n)

Space Complexity:
O(1)

Efficient and handles large bounds safely using long arithmetic.

---

Edge Cases

• differences = []
  Then nums has size 1 → answer = (upper − lower + 1)
• Very large prefix values
  Must use long to avoid overflow.
• No overlap in constraints → return 0
• All differences zero
  Sequence is constant → only valid if lower ≤ nums[0] ≤ upper