Watch 5 video solutions for Find the Number of Copy Arrays, a medium level problem involving Array, Math. This walkthrough by Aryan Mittal has 1,398 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
(copy[i] - copy[i - 1]) == (original[i] - original[i - 1]) for 1 <= i <= n - 1.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 <= 1051 <= original[i] <= 109bounds.length == nbounds[i].length == 21 <= bounds[i][0] <= bounds[i][1] <= 109Problem Overview: You are given an array nums and a bounds array where bounds[i] = [li, ri]. A copy array arr must preserve the same adjacent differences as nums while ensuring li ≤ arr[i] ≤ ri. The task is to count how many such arrays exist.
Approach 1: Brute Force Start Value Enumeration (O(n * R) time, O(1) space)
The adjacent differences of arr must match nums. Once you pick arr[0], the rest of the array becomes fixed because arr[i] - arr[i-1] = nums[i] - nums[i-1]. You can iterate through every possible value of arr[0] within bounds[0], reconstruct the full array using the difference constraint, and check whether every element stays within its corresponding bound. This approach is easy to reason about and helps verify the constraint structure, but it becomes inefficient when the first range is large since each candidate requires a full array scan.
Approach 2: Range Intersection Using Difference Offsets (O(n) time, O(1) space)
The key observation is that the entire array is determined by the starting value. From the difference constraint, every element can be expressed as arr[i] = arr[0] + (nums[i] - nums[0]). This converts the problem into finding all valid values of arr[0]. For each index i, substitute the expression into the bounds condition li ≤ arr[i] ≤ ri. This produces a range constraint on arr[0]: li - (nums[i] - nums[0]) ≤ arr[0] ≤ ri - (nums[i] - nums[0]). Compute this interval for every index and intersect them. The final intersection gives all valid starting values. The number of integers in that intersection is the number of valid copy arrays.
This method works because preserving adjacent differences effectively locks the shape of the array; only a vertical shift remains free. The algorithm simply determines how much shifting is allowed while still respecting each bound.
Problems like this often appear when dealing with prefix differences or translation-invariant sequences. Understanding how to convert element constraints into a single-variable interval is a common trick in array and math problems.
Recommended for interviews: The range‑intersection approach. Interviewers expect you to notice that the difference constraint fixes the array structure and reduces the problem to counting valid values for arr[0]. Brute force demonstrates understanding, but the O(n) interval intersection solution shows strong problem decomposition skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Start Value Enumeration | O(n * R) | O(1) | Useful for understanding the constraint that the entire array depends on the first element |
| Range Intersection Using Difference Offsets | O(n) | O(1) | Optimal solution for large inputs; converts element bounds into a single valid interval for the starting value |