Find the Number of Copy Arrays - Practice Coding Problems

Find the Number of Copy Arrays - Problem

Array Math Medium

You are given an array original of length n and a 2D array bounds of length n × 2, where bounds[i] = [u_i, v_i].

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
u_i <= copy[i] <= v_i for 0 <= i <= n - 1

Return the number of such arrays.

Input & Output

Example 1 — Basic Case

$ Input: original = [1,3,2], bounds = [[1,1],[1,3],[2,4]]

› Output: 1

💡 Note: Only one valid copy array [1,3,2]. Starting with copy[0]=1, we get copy[1]=1+(3-1)=3, copy[2]=3+(2-3)=2. All elements satisfy their bounds.

Example 2 — No Valid Arrays

$ Input: original = [1,2,3], bounds = [[1,1],[2,2],[5,5]]

› Output: 0

💡 Note: If copy[0]=1, then copy[1]=1+(2-1)=2, copy[2]=2+(3-2)=3. But copy[2]=3 doesn't satisfy bounds[2]=[5,5], so no valid arrays exist.

Example 3 — Multiple Valid Arrays

$ Input: original = [1,1,1], bounds = [[1,3],[1,3],[1,3]]

› Output: 3

💡 Note: Since all differences are 0, copy array will be [x,x,x] for any starting value x. Valid starting values are 1,2,3, giving 3 possible arrays.

Constraints

1 ≤ n ≤ 10⁵
-10⁹ ≤ original[i] ≤ 10⁹
-10⁹ ≤ u_i ≤ v_i ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Original array and bounds for each position

Constraint

Copy must have same differences but fit in bounds

Count

Number of valid starting values

Key Takeaway

🎯 Key Insight: Once the first element is determined, the entire copy sequence follows from the original's differences

Asked in

G Google 15 M Microsoft 12

The key insight is that once the first element is chosen, the entire copy array is determined by the differences in the original array. The optimal range intersection approach calculates the valid starting range in O(n) time by propagating constraints from each position back to the first element. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Enumeration	O(n × R)	O(1)	Try every possible value for the first element and check if the resulting sequence is valid
Range Intersection Approach	O(n)	O(1)	Calculate the valid range for the first element by propagating constraints backwards

Brute Force Enumeration — Algorithm Steps

Step 1: Iterate through all possible values for copy[0] within [u_0, v_0]
Step 2: For each starting value, construct copy[i] = copy[i-1] + (original[i] - original[i-1])
Step 3: Check if all copy[i] satisfy their bounds constraints

Visualization

Tap to expand

Step-by-Step Walkthrough

Try Start=1

Test if sequence [1,3,2] fits bounds

Check Constraints

Verify each element is within its bounds

Count Valid

Increment counter if all constraints satisfied

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* original, int originalSize, int** bounds, int boundsSize) {
    int count = 0;
    
    // Try each possible starting value
    for (int start = bounds[0][0]; start <= bounds[0][1]; start++) {
        int valid = 1;
        int copyVal = start;
        
        // Check if this starting value leads to a valid sequence
        for (int i = 0; i < originalSize; i++) {
            if (i > 0) {
                copyVal = copyVal + (original[i] - original[i - 1]);
            }
            
            // Check bounds constraint
            if (copyVal < bounds[i][0] || copyVal > bounds[i][1]) {
                valid = 0;
                break;
            }
        }
        
        if (valid) {
            count++;
        }
    }
    
    return count;
}

int main() {
    // Simplified parsing for basic case
    int original[] = {1, 3, 2};
    int bounds0[] = {1, 1};
    int bounds1[] = {1, 3};
    int bounds2[] = {2, 4};
    int* bounds[] = {bounds0, bounds1, bounds2};
    
    int result = solution(original, 3, bounds, 3);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × R)

R is the range size of bounds[0], and for each starting value we check n elements

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra space for variables

✓ Linear Space

8.5K Views

Medium Frequency

~25 min Avg. Time

350 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Enumeration — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler