Skip to main content
Talentd

Find the Number of Copy Arrays - Solution & Explanation

MediumArrayMath3 min readAsked at: Google, Traveloka
Practice this problem

Problem Statement

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

Approach Overview

Problem 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.

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Start Value EnumerationO(n * R)O(1)Useful for understanding the constraint that the entire array depends on the first element
Range Intersection Using Difference OffsetsO(n)O(1)Optimal solution for large inputs; converts element bounds into a single valid interval for the starting value

Video Solution

3468. Find the Number of Copy Arrays | Array | Math • Aryan Mittal • 1,440 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Find the Number of Copy Arrays easy or hard?
Find the Number of Copy Arrays is typically classified as a Medium problem. The implementation is short, but the challenge is recognizing that the entire array depends on a single starting value and converting element bounds into a single intersection range.
Find the Number of Copy Arrays Python/Java solution
The implementation iterates through nums, computes the offset nums[i] - nums[0], and updates the valid interval for arr[0] using li - offset and ri - offset. Maintain the intersection of all intervals and return max(0, right - left + 1). The same logic works in Python, Java, C++, and Go.
How to solve Find the Number of Copy Arrays in O(n)?
First express every element as arr[i] = arr[0] + (nums[i] - nums[0]) because the adjacent differences must match. Convert each bound li ≤ arr[i] ≤ ri into a constraint on arr[0]. Intersect all such ranges while scanning the array once. The number of integers remaining in the final interval equals the number of valid copy arrays.
What is the best approach for Find the Number of Copy Arrays?
The optimal approach converts the problem into finding valid values for arr[0]. Because all adjacent differences must match nums, every element can be written as arr[i] = arr[0] + (nums[i] - nums[0]). Each bound then creates a constraint interval for arr[0]. Intersect all intervals and count the integers in the final range, which runs in O(n) time and O(1) space.
Is Find the Number of Copy Arrays asked at Google/Amazon/Meta?
Problems involving difference constraints and range intersection frequently appear in interviews at companies like Google, Amazon, and Meta. Variants often test whether you can transform element constraints into a single variable range and compute the intersection efficiently.
What data structure is used in Find the Number of Copy Arrays?
The solution mainly relies on arrays and simple arithmetic. No advanced data structures are required; the core technique is maintaining two integers representing the current lower and upper bounds of the valid range.
What is the time complexity of Find the Number of Copy Arrays?
The optimal solution runs in O(n) time and O(1) extra space. The algorithm scans the array once, computing the allowed interval for the starting value arr[0] and continuously intersecting ranges.

Ready to solve this problem?

Practice Find the Number of Copy Arrays with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count of Range Sum