Find the number of copy arrays

Array Math

46.8% acceptance

Feb 25, 2026

107

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: (copy[i] - copy[i - 1]) == (original[i] - original[i - 1]) for 1 <= i <= n - 1. ui <= copy[i] <= vi for 0 <= i <= n - 1. Return the number of such arrays.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn count_arrays(original: Vec<i32>, bounds: Vec<Vec<i32>>) -> i64 {
    // copy[i] = copy[0] + (original[i] - original[0])
    // Constraints: bounds[i][0] <= copy[i] <= bounds[i][1]
    // => bounds[i][0] - (original[i]-original[0]) <= copy[0] <= bounds[i][1] - (original[i]-original[0])
    let n = original.len();
    let mut lo = i64::MIN; let mut hi = i64::MAX;
    for i in 0..n {
      let diff = (original[i] - original[0]) as i64;
      let new_lo = bounds[i][0] as i64 - diff;
      let new_hi = bounds[i][1] as i64 - diff;
      lo = lo.max(new_lo); hi = hi.min(new_hi);
    }
    if hi < lo { 0 } else { hi - lo + 1 }
  }
}