Problem

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

1
2
3
4
5
6

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

1
2
3
4
5
6
7
8

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

1
2
3
4

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 <= 10^5
  • 1 <= original[i] <= 10^9
  • bounds.length == n
  • bounds[i].length == 2
  • 1 <= bounds[i][0] <= bounds[i][1] <= 10^9

Examples

Solution

Method 1 – Difference Array and Range Intersection

Intuition

The key is that the difference between consecutive elements in the copy array must match the difference in the original array. This means the entire copy array is determined by its first element. We need to find all possible values for copy[0] such that, after propagating the differences, every copy[i] stays within its bounds.

Approach

  1. Let d[i] = original[i] - original[i-1] for i >= 1.
  2. For any valid copy[0], the rest of the array is: copy[i] = copy[0] + (original[i] - original[0]).
  3. For each i, the bounds for copy[0] are:
    • bounds[i][0] - (original[i] - original[0]) <= copy[0] <= bounds[i][1] - (original[i] - original[0])
  4. The valid range for copy[0] is the intersection of all these intervals.
  5. The answer is the number of integers in this intersection (if any).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    int numberOfArrays(vector<int>& original, vector<vector<int>>& bounds) {
        int n = original.size();
        long long l = bounds[0][0], r = bounds[0][1];
        for (int i = 0; i < n; ++i) {
            long long diff = original[i] - original[0];
            l = max(l, (long long)bounds[i][0] - diff);
            r = min(r, (long long)bounds[i][1] - diff);
        }
        return max(0LL, r - l + 1);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func numberOfArrays(original []int, bounds [][]int) int {
    n := len(original)
    l, r := bounds[0][0], bounds[0][1]
    for i := 0; i < n; i++ {
        diff := original[i] - original[0]
        l = max(l, bounds[i][0]-diff)
        r = min(r, bounds[i][1]-diff)
    }
    if r < l {
        return 0
    }
    return r - l + 1
}
func max(a, b int) int { if a > b { return a }; return b }
func min(a, b int) int { if a < b { return a }; return b }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public int numberOfArrays(int[] original, int[][] bounds) {
        int n = original.length;
        long l = bounds[0][0], r = bounds[0][1];
        for (int i = 0; i < n; i++) {
            long diff = original[i] - original[0];
            l = Math.max(l, bounds[i][0] - diff);
            r = Math.min(r, bounds[i][1] - diff);
        }
        return (int)Math.max(0, r - l + 1);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun numberOfArrays(original: IntArray, bounds: Array<IntArray>): Int {
        val n = original.size
        var l = bounds[0][0].toLong()
        var r = bounds[0][1].toLong()
        for (i in 0 until n) {
            val diff = original[i] - original[0]
            l = maxOf(l, bounds[i][0] - diff.toLong())
            r = minOf(r, bounds[i][1] - diff.toLong())
        }
        return if (r < l) 0 else (r - l + 1).toInt()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def numberOfArrays(self, original: list[int], bounds: list[list[int]]) -> int:
        n = len(original)
        l = bounds[0][0]
        r = bounds[0][1]
        for i in range(n):
            diff = original[i] - original[0]
            l = max(l, bounds[i][0] - diff)
            r = min(r, bounds[i][1] - diff)
        return max(0, r - l + 1)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

impl Solution {
    pub fn number_of_arrays(original: Vec<i32>, bounds: Vec<Vec<i32>>) -> i32 {
        let n = original.len();
        let mut l = bounds[0][0] as i64;
        let mut r = bounds[0][1] as i64;
        for i in 0..n {
            let diff = (original[i] - original[0]) as i64;
            l = l.max(bounds[i][0] as i64 - diff);
            r = r.min(bounds[i][1] as i64 - diff);
        }
        if r < l { 0 } else { (r - l + 1) as i32 }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    numberOfArrays(original: number[], bounds: number[][]): number {
        let n = original.length;
        let l = bounds[0][0], r = bounds[0][1];
        for (let i = 0; i < n; ++i) {
            let diff = original[i] - original[0];
            l = Math.max(l, bounds[i][0] - diff);
            r = Math.min(r, bounds[i][1] - diff);
        }
        return Math.max(0, r - l + 1);
    }
}

Complexity

  • ⏰ Time complexity: O(n), since we process each element once to compute the intersection.
  • 🧺 Space complexity: O(1), as only a few variables are used regardless of input size.