3785. Find The Number Of Copy Arrays¶

3785. Find the Number of Copy Arrays

Medium

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:

Example 2:

Example 3:

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

Solution¶

class Solution {
static public int countArrays(int[] original, int[][] bounds) {
        int n = original.length, x = bounds[0][0], y = bounds[0][1];
        for (int i = 1; i < n; i++) {
            int a = bounds[i][0], b = bounds[i][1], diff = original[i] - original[i - 1];
            x += diff; 
            y += diff;
            x = Math.max(x, a);
            y = Math.min(y, b);
        }
        return Math.max(y - x + 1, 0);
    }
}

Complexity Analysis¶

• Time Complexity: O(?)
• Space Complexity: O(?)

Explanation¶

[Add detailed explanation here]