# Find the Number of Copy Arrays
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-the-number-of-copy-arrays)
Canonical: https://scaleengineer.com/dsa/problems/find-the-number-of-copy-arrays
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Array
---
## Problem
You are given an array `original` of length `n` and a 2D array `bounds` of length `n x 2`, where `bounds[i] = [ui, vi]`.

You need to find the number of **possible** arrays `copy` of length `n` such that:

1. `(copy[i] - copy[i - 1]) == (original[i] - original[i - 1])` for `1 <= i <= n - 1`.
2. `ui <= copy[i] <= vi` for `0 <= i <= n - 1`.

Return the number of such arrays.

**Example 1:**

**Input:** original = \[1,2,3,4\], bounds = \[\[1,2\],\[2,3\],\[3,4\],\[4,5\]\]

**Output:** 2

**Explanation:**

The possible arrays are:

* `[1, 2, 3, 4]`
* `[2, 3, 4, 5]`

**Example 2:**

**Input:** original = \[1,2,3,4\], bounds = \[\[1,10\],\[2,9\],\[3,8\],\[4,7\]\]

**Output:** 4

**Explanation:**

The possible arrays are:

* `[1, 2, 3, 4]`
* `[2, 3, 4, 5]`
* `[3, 4, 5, 6]`
* `[4, 5, 6, 7]`

**Example 3:**

**Input:** original = \[1,2,1,2\], bounds = \[\[1,1\],\[2,3\],\[3,3\],\[2,3\]\]

**Output:** 0

**Explanation:**

No array is possible.

**Constraints:**

* `2 <= n == original.length <= 105`
* `1 <= original[i] <= 109`
* `bounds.length == n`
* `bounds[i].length == 2`
* `1 <= bounds[i][0] <= bounds[i][1] <= 109`

# Approaches
## Brute Force by Iterating Differences
This approach is a straightforward brute-force method. It first recognizes the key property that the `copy` array is a shifted version of the `original` array, i.e., `copy[i] = original[i] + d` for some constant `d`. It then determines an initial search range for `d` based on the constraints of the first element. Finally, it iterates through every possible integer value of `d` in this range and, for each one, verifies if it satisfies the constraints for all other elements in the array. The number of `d` values that pass this check is the answer.
**Time:** O((V₀ - U₀) * n) - where `n` is the length of the array, and `V₀` and `U₀` are the upper and lower bounds for the first element. The outer loop runs `V₀ - U₀ + 1` times, and the inner loop runs `n-1` times. This is highly inefficient if the range `V₀ - U₀` is large. · **Space:** O(1) - We only use a few variables to store the loop counter and state, regardless of the input size.
**Pros:** Conceptually simple and easy to implement.; Correctly models the problem's constraints.
**Cons:** The time complexity is dependent on the range of values in `bounds[0]`, which can be very large (up to 10^9).; This approach will result in a 'Time Limit Exceeded' error for most test cases due to its inefficiency.
### Explanation
The algorithm proceeds as follows:
1.  Calculate the initial range for the difference `d` using the bounds for `original[0]`. Let this range be `[d_min, d_max]`, where `d_min = bounds[0][0] - original[0]` and `d_max = bounds[0][1] - original[0]`.
2.  Initialize a counter for valid arrays to zero.
3.  Loop through each integer `d` from `d_min` to `d_max`.
4.  Inside the loop, for each `d`, assume it's valid and check against the constraints for `i = 1` to `n-1`.
5.  A nested loop checks if `original[i] + d` is within `[bounds[i][0], bounds[i][1]]`.
6.  If `d` is valid for all `i`, increment the counter.
7.  After the outer loop finishes, the counter holds the total number of possible `copy` arrays.

```java
class Solution {
    public long numberOfCopyArrays(int[] original, int[][] bounds) {
        long count = 0;
        // Using long for d to be safe, though the initial range might be small.
        long d_min = (long)bounds[0][0] - original[0];
        long d_max = (long)bounds[0][1] - original[0];

        for (long d = d_min; d <= d_max; d++) {
            boolean isValid = true;
            // Check this d for all other elements
            for (int i = 1; i < original.length; i++) {
                long copy_i = (long)original[i] + d;
                if (copy_i < bounds[i][0] || copy_i > bounds[i][1]) {
                    isValid = false;
                    break;
                }
            }
            if (isValid) {
                count++;
            }
        }
        return count;
    }
}
```
### Algorithm
- The first condition `copy[i] - copy[i - 1] == original[i] - original[i - 1]` implies that `copy[i] - original[i]` is a constant for all `i`. Let this constant be `d`. Thus, `copy[i] = original[i] + d` for all `i`.
- The problem is now to find the number of valid integer values for `d`.
- A brute-force approach can be to determine a possible range for `d` and then test each value.
- We can use the bounds for the first element (`i=0`) to establish an initial range for `d`. From `bounds[0][0] <= copy[0] <= bounds[0][1]`, we get `bounds[0][0] <= original[0] + d <= bounds[0][1]`, which means `d` must be in the range `[bounds[0][0] - original[0], bounds[0][1] - original[0]]`.
- We can iterate through every integer `d` in this initial range.
- For each `d`, we check if it's valid for all other elements from `i = 1` to `n-1`. A value `d` is valid if `bounds[i][0] <= original[i] + d <= bounds[i][1]` holds for all `i`.
- We count the number of such valid `d` values.

## Optimal Approach using Range Intersection
This optimal approach is based on a key mathematical insight. By rearranging the first condition, we can deduce that any valid `copy` array must be a simple translation of the `original` array, i.e., `copy[i] = original[i] + d` for some constant difference `d`. The problem then becomes finding the number of possible integer values for `d`.

Each element's bounds `[u_i, v_i]` impose a constraint on `d` of the form `u_i - original[i] <= d <= v_i - original[i]`. To satisfy all constraints simultaneously, `d` must fall within the intersection of all these individual ranges. By finding the maximum of all lower bounds and the minimum of all upper bounds for `d`, we can determine the final valid range for `d` in a single pass through the input arrays. The size of this final range gives the answer.
**Time:** O(n) - The algorithm involves a single pass through the input arrays of length `n` to find the intersection of the ranges. · **Space:** O(1) - The algorithm only requires a few variables to store the maximum lower bound and minimum upper bound, independent of the input size.
**Pros:** Extremely efficient with linear time complexity.; Handles all constraints, including large values and ranges.; Uses constant extra space.
**Cons:** Requires a mathematical insight to transform the problem into a range intersection problem, which might not be immediately obvious.
### Explanation
The algorithm is as follows:
1.  Establish that `copy[i] = original[i] + d` for a constant `d`.
2.  For each `i`, this implies `bounds[i][0] - original[i] <= d <= bounds[i][1] - original[i]`.
3.  We need to find the intersection of these `n` ranges for `d`. The intersection will be a single range `[max_lower, min_upper]`.
4.  Initialize `maxLowerBound = Long.MIN_VALUE` and `minUpperBound = Long.MAX_VALUE`.
5.  Iterate through the arrays from `i = 0` to `n-1`.
6.  In each iteration, calculate the lower and upper bound for `d` for the current `i`: `lower_d = bounds[i][0] - original[i]` and `upper_d = bounds[i][1] - original[i]`.
7.  Update the overall tightest bounds: `maxLowerBound = Math.max(maxLowerBound, lower_d)` and `minUpperBound = Math.min(minUpperBound, upper_d)`.
8.  After the loop, check if a valid range exists. If `maxLowerBound > minUpperBound`, no integer `d` can satisfy all conditions, so return 0.
9.  Otherwise, the number of valid integers for `d` is the length of the range, which is `minUpperBound - maxLowerBound + 1`.

```java
class Solution {
    public long numberOfCopyArrays(int[] original, int[][] bounds) {
        long maxLowerBound = Long.MIN_VALUE;
        long minUpperBound = Long.MAX_VALUE;

        for (int i = 0; i < original.length; i++) {
            // Calculate the allowed range for the difference 'd' for the current element
            long lower_d = (long)bounds[i][0] - original[i];
            long upper_d = (long)bounds[i][1] - original[i];
            
            // Narrow down the global valid range for 'd' by intersecting with the current range
            maxLowerBound = Math.max(maxLowerBound, lower_d);
            minUpperBound = Math.min(minUpperBound, upper_d);
        }

        // If the max lower bound is greater than the min upper bound, the intersection is empty
        if (maxLowerBound > minUpperBound) {
            return 0;
        }

        // The number of possible integer values for 'd' is the size of the final range
        return minUpperBound - maxLowerBound + 1;
    }
}
```
### Algorithm
- The first condition `copy[i] - copy[i - 1] == original[i] - original[i - 1]` can be rewritten as `copy[i] - original[i] == copy[i - 1] - original[i - 1]`. This shows that the difference `copy[i] - original[i]` is a constant for all `i`. Let's call this constant difference `d`.
- Therefore, `copy[i] = original[i] + d` for all `i` from `0` to `n-1`.
- The problem reduces to finding the number of possible integer values for `d`.
- The second condition is `bounds[i][0] <= copy[i] <= bounds[i][1]`. Substituting `copy[i]`, we get `bounds[i][0] <= original[i] + d <= bounds[i][1]`.
- Rearranging for `d`, we get an inequality for each `i`: `bounds[i][0] - original[i] <= d <= bounds[i][1] - original[i]`.
- To satisfy all `n` conditions simultaneously, `d` must lie in the intersection of all these `n` ranges.
- The intersection of a set of intervals `[l_i, r_i]` is given by `[max(l_i), min(r_i)]`.
- We can find the overall tightest lower bound (`maxLowerBound`) and upper bound (`minUpperBound`) for `d` by iterating through the arrays once.
- Initialize `maxLowerBound` to a very small number (e.g., `Long.MIN_VALUE`) and `minUpperBound` to a very large number (e.g., `Long.MAX_VALUE`).
- Iterate from `i = 0` to `n-1`, updating `maxLowerBound = max(maxLowerBound, bounds[i][0] - original[i])` and `minUpperBound = min(minUpperBound, bounds[i][1] - original[i])`.
- After the loop, if `maxLowerBound > minUpperBound`, there is no valid `d`, so the number of arrays is 0.
- Otherwise, the number of possible integer values for `d` is `minUpperBound - maxLowerBound + 1`.