Minimum size subarray in infinite array

Array Hash Table Sliding Window Prefix Sum

32.0% acceptance

Feb 25, 2026

416

You are given a 0-indexed array nums and an integer target. A 0-indexed array infinite_nums is generated by infinitely appending the elements of nums to itself. Return the length of the shortest subarray of the array infinite_nums with a sum equal to target. If there is no such subarray return -1.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_size_subarray(nums: Vec<i32>, target: i32) -> i32 {
    let n = nums.len();
    let total: i64 = nums.iter().map(|&v| v as i64).sum();
    let target = target as i64;
    // How many full copies needed
    let full_copies = target / total;
    let rem = target % total;
    let base = full_copies * n as i64;
    // Find shortest subarray in nums+nums with sum == rem (if rem > 0)
    if rem == 0 {
      return base as i32;
    }
    // Sliding window on nums doubled
    let doubled: Vec<i64> = nums.iter().chain(nums.iter()).map(|&v| v as i64).collect();
    let mut best = i64::MAX;
    let mut sum = 0i64;
    let mut left = 0;
    for right in 0..doubled.len() {
      sum += doubled[right];
      while sum > rem {
        sum -= doubled[left];
        left += 1;
      }
      if sum == rem {
        best = best.min((right - left + 1) as i64);
      }
    }
    if best == i64::MAX { return -1; }
    (base + best) as i32
  }
}