Scale Engineer

Find the Number of Copy Arrays

Med
#3083Time: 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.
Patterns
Math
Data structures
Array

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.
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;    }}

Complexity

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.

Trade-offs

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.

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem