Find the Number of Copy Arrays

Find the Number of Copy Arrays

What is this problem about?

The Find the Number of Copy Arrays interview question gives you an array original and a 2D array bounds where bounds[i] = [lower_i, upper_i]. You need to find how many arrays copy exist such that:

1. copy[i] is within bounds[i].
2. The difference between adjacent elements is the same as in the original: copy[i] - copy[i-1] == original[i] - original[i-1].

Why is this asked in interviews?

Google uses this problem to test your ability to handle range intersections. The second condition implies that the entire copy array is determined once you pick the first element copy[0]. The problem then becomes: "What is the range of valid values for copy[0] such that all subsequent elements stay within their bounds?"

Algorithmic pattern used

This is a Range Intersection problem.

1. Let the range of possible values for the first element be [min_0, max_0], initially bounds[0].
2. For each subsequent index $i$:
   • Calculate the required difference diff = original[i] - original[0].
   • The value copy[i] will be copy[0] + diff.
   • This means bounds[i].lower <= copy[0] + diff <= bounds[i].upper.
   • Solving for copy[0]: bounds[i].lower - diff <= copy[0] <= bounds[i].upper - diff.
3. Intersect this new range with your current [min_0, max_0].
4. The final count is max(0, max_0 - min_0 + 1).

Example explanation

original = [1, 2, 3], bounds = [[1, 5], [1, 5], [1, 5]].

1. $i=0$: copy[0] in [1, 5].
2. $i=1$: diff = 2 - 1 = 1. copy[1] = copy[0] + 1.
   • $1 \le copy[0] + 1 \le 5 \implies 0 \le copy[0] \le 4$.
   • Intersect [1, 5] and [0, 4] $o$ [1, 4].
3. $i=2$: diff = 3 - 1 = 2. copy[2] = copy[0] + 2.
   • $1 \le copy[0] + 2 \le 5 \implies -1 \le copy[0] \le 3$.
   • Intersect [1, 4] and [-1, 3] $o$ [1, 3]. Valid copy[0] values: 1, 2, 3. Count = 3.

Common mistakes candidates make

• Simulation: Trying to count arrays by iterating through values, which is $O(N imes Range)$ and too slow.
• Difference error: Using the difference between i and i-1 instead of the cumulative difference from the start.
• Intersection logic: Forgetting to handle the case where the range becomes empty (count should be 0, not negative).

Interview preparation tip

When a sequence is constrained by fixed deltas, the entire sequence is a "shifted" version of the first element. This reduces a multi-variable problem to a single-variable range intersection problem. This is a very common Array interview pattern.