Count Analogous Arrays

Reported in interviews at Two Sigma

Problem statement

A secret integer array of length $n$ is hidden, but you know two things about it: every element of the secret array lies in $[\text{lowerBound}, \text{upperBound}]$, and you are given its array of consecutive differences consecutiveDifference, where consecutiveDifference[i] $= s[i] - s[i+1]$ (note the order: earlier minus later).

An array $a$ is analogous to the secret array if it has the same length, every element is in $[\text{lowerBound}, \text{upperBound}]$, and it has the exact same consecutive differences: $a[i] - a[i+1] = s[i] - s[i+1]$ for all $i$.

Count how many analogous arrays exist. Return 0 if none.

countAnalogousArrays(consecutiveDifference: List[int], lowerBound: int, upperBound: int) -> int

Constraints

  • Bounds and differences are integers.

Example

consecutiveDifference = [-2, -1, -2, 5]
lowerBound = 3, upperBound = 10

Fixing $a_0$ determines the whole array. The valid starts give $[3,5,6,8,3]$, $[4,6,7,9,4]$, $[5,7,8,10,5]$. Answer: 3.

Show hint

How many values do you actually need to choose before the entire array is determined?

Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.

Related free problems