We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Number of Copy Arrays

Number: 3785

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given an array original of length n and a 2D array bounds of size n x 2 (where bounds[i] = [uᵢ, vᵢ]), count the number of arrays copy of length n that satisfy:

  1. For every index i (1 <= i < n), (copy[i] - copy[i-1]) equals (original[i] - original[i-1]).
  2. For every index i (0 <= i < n), copy[i] is within the bounds: uᵢ <= copy[i] <= vᵢ.

In other words, the copy array must have the same successive differences as original, and each element must lie within its corresponding bounds.

Key Insights

  • The condition (copy[i] - copy[i-1]) == (original[i] - original[i-1]) means that the copy array is determined entirely by its first element.
  • Let d[i] = original[i] - original[0]. Then copy[i] can be expressed as copy[0] + d[i].
  • For every index i, the constraint becomes: uᵢ <= copy[0] + d[i] <= vᵢ.
  • Rearrange each inequality to get: copy[0] >= (uᵢ - d[i]) and copy[0] <= (vᵢ - d[i]).
  • The valid range for copy[0] must be the intersection of these n ranges.
  • The answer is the number of integers in the intersection. If lowerBound and upperBound are the intersection bounds, then answer = max(0, upperBound - lowerBound + 1).

Space and Time Complexity

Time Complexity: O(n), where n is the length of the array. Space Complexity: O(1), using a constant amount of extra space.

Solution

The algorithm first computes the offset d[i] = original[i] - original[0] and then transforms the original bounds into bounds for copy[0] by subtracting d[i] from each bound. It calculates:

  • lowerBound = max(for each i: bounds[i][0] - d[i])
  • upperBound = min(for each i: bounds[i][1] - d[i])

If lowerBound exceeds upperBound, no valid copy array exists and we return 0. Otherwise, the answer is (upperBound - lowerBound + 1).

Key techniques include:

  • Reducing the problem from creating an entire array to finding a valid starting value.
  • Using running maximum and minimum to find the intersection of ranges.

Code Solutions

def count_copy_arrays(original, bounds):
    # Use the first element of original as the base.
    base = original[0]
    
    # Initialize the valid range for copy[0].
    lower_bound = float('-inf')
    upper_bound = float('inf')
    
    # For each element, update the possible range for copy[0].
    for i in range(len(original)):
        # Calculate the change from the first element.
        diff = original[i] - base
        # Update lower bound: copy[0] + diff must be at least bounds[i][0]
        lower_bound = max(lower_bound, bounds[i][0] - diff)
        # Update upper bound: copy[0] + diff must be at most bounds[i][1]
        upper_bound = min(upper_bound, bounds[i][1] - diff)
    
    # If the intersection is invalid, return 0; otherwise, count the number of valid integers.
    return max(0, upper_bound - lower_bound + 1)

# Example Test Cases
print(count_copy_arrays([1,2,3,4], [[1,2],[2,3],[3,4],[4,5]]))  # Expected output: 2
print(count_copy_arrays([1,2,3,4], [[1,10],[2,9],[3,8],[4,7]]))  # Expected output: 4
print(count_copy_arrays([1,2,1,2], [[1,1],[2,3],[3,3],[2,3]]))   # Expected output: 0
← Back to All Questions