Difficulty: 🟡 Medium
Topics: Array, Math

Solution

LeetCode 3468 - Find the Number of Copy Arrays

Problem Understanding

We are given an array original and a range constraint for every position in the form of bounds[i] = [ui, vi].

We need to count how many arrays copy satisfy two conditions.

The first condition states that the difference between consecutive elements in copy must be exactly the same as the difference between consecutive elements in original.

For every index i > 0:

copy[i] - copy[i - 1] = original[i] - original[i - 1]

This is a very strong restriction. Once we choose the first element of copy, every other element becomes completely determined.

The second condition requires every element of copy to stay inside its allowed interval:

ui <= copy[i] <= vi

Our task is to count how many different choices of copy satisfy all these constraints.

The input size is large:

n <= 100000

A solution that explicitly tries every possible array is impossible. We need an algorithm that runs in linear time.

An important observation is that the difference constraints force copy to have exactly the same shape as original. The only freedom is shifting the entire array up or down by a constant amount.

Important edge cases include situations where the valid interval becomes empty after combining all constraints, cases where exactly one array is possible, and cases where very large values appear near 10^9.

Approaches

Brute Force

A brute force solution would try every possible value for copy[0].

Once copy[0] is fixed, the difference constraints uniquely determine the rest of the array. We could construct the whole array and check whether every position satisfies its bounds.

The problem is that copy[0] may range over values as large as 10^9. Even if we only considered the interval from the first bound, that range can still contain billions of candidates.

Therefore, brute force is far too slow.

Key Insight

The difference constraints imply that every valid copy array is simply a shifted version of original.

Let:

shift = copy[0] - original[0]

Then:

copy[i] = original[i] + shift

for every index i.

This can be proven by repeatedly applying the equal-difference condition.

Now each bound becomes a constraint on the single variable shift:

ui <= original[i] + shift <= vi

Rearranging:

ui - original[i] <= shift <= vi - original[i]

Each index contributes one interval of valid shifts.

The shift must satisfy all intervals simultaneously, so we only need to compute their intersection.

If the final intersection is:

[L, R]

then every integer shift in that range produces a valid array.

The answer is therefore:

max(0, R - L + 1)

Comparison of Approaches

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × range)	O(1)	Tries every possible starting value
Optimal	O(n)	O(1)	Intersects valid shift intervals

Algorithm Walkthrough

Define a variable lower representing the smallest valid shift seen so far. Initialize it to negative infinity.
Define a variable upper representing the largest valid shift seen so far. Initialize it to positive infinity.
For each index i, derive the shift interval implied by the bounds:

bounds[i][0] - original[i]
<= shift <=
bounds[i][1] - original[i]

Update the global intersection:

lower = max(lower, bounds[i][0] - original[i])
upper = min(upper, bounds[i][1] - original[i])

This keeps only shifts that satisfy every constraint processed so far. 5. After processing all positions, check whether the intersection is empty.

If:

lower > upper

then no valid shift exists, so return 0. 6. Otherwise every integer shift in:

[lower, upper]

produces a valid copy array. 7. Return:

upper - lower + 1

Why it works

The difference constraints force every valid array to be of the form:

copy[i] = original[i] + shift

for a single constant shift. Therefore the entire problem reduces to finding which values of shift satisfy all bound constraints. Each position contributes one interval of allowed shifts, and a shift is valid if and only if it belongs to the intersection of all intervals. Counting the integers inside that final intersection gives exactly the number of valid arrays.

Python Solution

from typing import List

class Solution:
    def countArrays(self, original: List[int], bounds: List[List[int]]) -> int:
        lower = -10**18
        upper = 10**18

        for value, (left, right) in zip(original, bounds):
            lower = max(lower, left - value)
            upper = min(upper, right - value)

        if lower > upper:
            return 0

        return upper - lower + 1

The implementation directly follows the mathematical observation.

The variables lower and upper store the current intersection of valid shifts. For every index, we convert the bound on copy[i] into a bound on the shift. We then update the intersection by taking the maximum lower bound and the minimum upper bound.

After all positions have been processed, either the intersection is empty, in which case we return 0, or it contains a consecutive range of integer shifts. The number of integers in that range is upper - lower + 1.

Because we only maintain two variables throughout the scan, the solution uses constant extra memory.

Go Solution

func countArrays(original []int, bounds [][]int) int {
	lower := int64(-1e18)
	upper := int64(1e18)

	for i, value := range original {
		left := int64(bounds[i][0] - value)
		right := int64(bounds[i][1] - value)

		if left > lower {
			lower = left
		}
		if right < upper {
			upper = right
		}
	}

	if lower > upper {
		return 0