# Minimum Size Subarray in Infinite Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-size-subarray-in-infinite-array)
Canonical: https://scaleengineer.com/dsa/problems/minimum-size-subarray-in-infinite-array
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, Hash Table
**Companies:** [DE Shaw](https://scaleengineer.com/companies/de-shaw)
---
## Problem
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`.

**Example 1:**

**Input:** nums = [1,2,3], target = 5
**Output:** 2
**Explanation:** In this example infinite_nums = [1,2,3,1,2,3,1,2,...].
The subarray in the range [1,2], has the sum equal to target = 5 and length = 2.
It can be proven that 2 is the shortest length of a subarray with sum equal to target = 5.

**Example 2:**

**Input:** nums = [1,1,1,2,3], target = 4
**Output:** 2
**Explanation:** In this example infinite_nums = [1,1,1,2,3,1,1,1,2,3,1,1,...].
The subarray in the range [4,5], has the sum equal to target = 4 and length = 2.
It can be proven that 2 is the shortest length of a subarray with sum equal to target = 4.

**Example 3:**

**Input:** nums = [2,4,6,8], target = 3
**Output:** -1
**Explanation:** In this example infinite_nums = [2,4,6,8,2,4,6,8,...].
It can be proven that there is no subarray with sum equal to target = 3.

**Constraints:**

* `1 <= nums.length <= 105`
* `1 <= nums[i] <= 105`
* `1 <= target <= 109`

# Approaches
## Brute Force Simulation
This approach simulates the process of finding a subarray sum directly on the conceptual `infinite_nums` array. We test every possible starting point within the first copy of `nums` and, for each, extend the subarray by adding subsequent elements from the infinite sequence until the sum matches the `target`. Since all numbers are positive, we can stop extending a subarray once its sum exceeds the `target`.
**Time:** O(n * target) - The outer loop runs `n` times. The inner loop, in the worst-case scenario (e.g., `nums = [1]`), can run up to `target` times for each starting position. This makes the complexity proportional to `n` times `target`. · **Space:** O(1) - We only use a few variables to store the current sum, length, and minimum length.
**Pros:** Simple to understand and implement.; Correctly solves the problem for small inputs.
**Cons:** Extremely inefficient and will result in a 'Time Limit Exceeded' error for large values of `target`.; The number of iterations can be very large, making it impractical for the given constraints.
### Explanation
The brute-force method involves a nested loop structure. The outer loop iterates through all possible start indices of a subarray, which can be limited to the first `n` indices (`0` to `n-1`), as any starting position further down the infinite array is equivalent to one of these. The inner loop then expands the subarray from that starting point, element by element, keeping track of the running sum and length. The indices for the `infinite_nums` array are mapped back to the original `nums` array using the modulo operator (`j % n`). We keep a variable to store the minimum length found so far. If the current sum equals the target, we update the minimum length. If it exceeds the target, we stop extending the current subarray and move to the next starting position.

```java
class Solution {
    public int minSizeSubarray(int[] nums, int target) {
        int n = nums.length;
        long minLength = Long.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            long currentSum = 0;
            long currentLength = 0;
            // The inner loop can run up to 'target' times in the worst case (e.g., nums=[1])
            // which is too slow.
            for (int j = 0; j < n + target; j++) { // A safe upper bound, but still too large
                currentSum += nums[(i + j) % n];
                currentLength++;
                if (currentSum == target) {
                    minLength = Math.min(minLength, currentLength);
                    break;
                }
                if (currentSum > target) {
                    break;
                }
            }
        }

        return minLength == Long.MAX_VALUE ? -1 : (int) minLength;
    }
}
```
### Algorithm
1. Iterate through each possible starting position `i` from `0` to `n-1`, where `n` is the length of `nums`.
2. For each starting position `i`, simulate building a subarray in the `infinite_nums` array.
3. Initialize `currentSum = 0` and `currentLength = 0`.
4. Start a loop that iterates through the `infinite_nums` array, starting from index `i`. The index in the original `nums` array can be calculated using the modulo operator: `nums[j % n]`.
5. In each step of the inner loop, add the current element to `currentSum` and increment `currentLength`.
6. If `currentSum` equals `target`, we have found a valid subarray. Update the global minimum length with `currentLength` and break the inner loop (since we are looking for the shortest subarray starting at `i`).
7. If `currentSum` exceeds `target`, we can also break the inner loop because all numbers are positive, so the sum will only increase.
8. After checking all starting positions from `0` to `n-1`, if a minimum length was found, return it. Otherwise, return -1.

## Prefix Sum with Modular Arithmetic
This efficient approach is based on a key insight: any subarray in the infinite array is either relatively 'short' or 'long'. A 'short' subarray is one that can be found within `nums` concatenated with itself (`[nums, nums]`). A 'long' subarray is one that spans multiple full copies of `nums`. We can find the length of the shortest 'short' subarray directly. For 'long' subarrays, we use modular arithmetic. The `target` sum can be broken down into a number of full `nums` traversals and a smaller `remainder` target. The length is the sum of lengths for these parts. By checking the most likely decompositions, we can find the overall minimum length in linear time.
**Time:** O(n) - Calculating the total sum takes O(n). Creating the doubled array takes O(n). The helper function `findMinSubArrayLen` runs in O(n) time as it iterates through the array of size `2n` once. We call this function a constant number of times. Thus, the total time complexity is dominated by these linear operations. · **Space:** O(n) - We create a new array `nums2` of size `2n`. The prefix sum map in the helper function can also store up to `2n` entries in the worst case.
**Pros:** Highly efficient with linear time complexity.; Correctly handles all cases, including very large targets.; The logic is generalizable to similar problems involving infinite or circular arrays.
**Cons:** Requires careful handling of edge cases, such as when `target` is a multiple of the array sum.; Uses extra space for the doubled array and the prefix sum map.
### Explanation
The core idea is to handle two main cases for the minimal subarray.

**Case 1: The subarray is contained within `nums` or wraps around it once.**
Any such subarray is a contiguous subarray of `nums` concatenated with itself. We create an array `nums2` of length `2n` and find the minimum length subarray with sum `target` in it. This can be done in O(n) time using a HashMap to store prefix sums and their first occurrences.

**Case 2: The subarray contains one or more full copies of `nums`.**
If the `target` is large, the minimal subarray might be composed of `k` full copies of `nums` plus a 'remainder' subarray. We can express `target` as `q*S + r`, where `S` is the sum of `nums`, `q = target / S`, and `r = target % S`.
This suggests a candidate solution of length `q*n + len(r)`, where `len(r)` is the minimum length of a subarray summing to `r`. Since `r < S`, this remainder subarray must be 'short', so we can find its length by searching in `nums2`.

If `r` is 0, it means `target` is a multiple of `S`. The decomposition can be viewed as `(q-1)*n + len(S)`. We calculate this candidate length as well.

The final answer is the minimum of the lengths found from these cases.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int minSizeSubarray(int[] nums, int target) {
        long totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }

        int n = nums.length;
        int numFullArrays = (int) (target / totalSum);
        int remainderTarget = (int) (target % totalSum);

        long minLen = Long.MAX_VALUE;

        if (remainderTarget == 0) {
            // If target is a multiple of totalSum, the answer is simply numFullArrays * n.
            // This is because any shorter subarray for sum 'totalSum' would have been found
            // when we check for remainderTarget = totalSum below, but with one less full array.
            // The problem can be rephrased as (numFullArrays - 1) full arrays + a subarray for sum S.
            minLen = (long) numFullArrays * n;
        } else {
            // Find min length for remainderTarget in the doubled array
            int[] nums2 = new int[2 * n];
            System.arraycopy(nums, 0, nums2, 0, n);
            System.arraycopy(nums, 0, nums2, n, n);

            int lenForRem = findMinSubArrayLen(nums2, remainderTarget);

            if (lenForRem != -1) {
                minLen = (long) numFullArrays * n + lenForRem;
            }
        }
        
        // We also need to check for a solution that doesn't use the modular arithmetic trick.
        // This covers cases where the optimal subarray is short and doesn't align with the q*S+r structure.
        // For example, target = S+1, but the optimal solution is a short subarray for S+1, not 1 full array + subarray for 1.
        // Searching in nums2 for the original target covers all such cases.
        int[] nums2 = new int[2 * n];
        System.arraycopy(nums, 0, nums2, 0, n);
        System.arraycopy(nums, 0, nums2, n, n);
        int directLen = findMinSubArrayLen(nums2, target);
        if (directLen != -1) {
            minLen = Math.min(minLen, directLen);
        }

        return minLen == Long.MAX_VALUE ? -1 : (int) minLen;
    }

    private int findMinSubArrayLen(int[] arr, int target) {
        if (target <= 0) return -1;
        Map<Long, Integer> prefixSumMap = new HashMap<>();
        prefixSumMap.put(0L, -1);
        long currentSum = 0;
        int minLen = Integer.MAX_VALUE;

        for (int i = 0; i < arr.length; i++) {
            currentSum += arr[i];
            if (prefixSumMap.containsKey(currentSum - target)) {
                minLen = Math.min(minLen, i - prefixSumMap.get(currentSum - target));
            }
            prefixSumMap.put(currentSum, i);
        }

        return minLen == Integer.MAX_VALUE ? -1 : minLen;
    }
}
```
*Note: The provided Java code has a slight simplification. A more robust solution might need to check `(q-1)*n + len(S+r)` as another candidate. However, the logic of checking for `target` directly in `nums2` covers this implicitly.*
### Algorithm
1. Calculate the total sum `S` of the elements in `nums` and its length `n`.
2. Any solution subarray is either short (length <= 2n) or long (contains full copies of `nums`).
3. **Handle short subarrays:** Create a temporary array `nums2` by concatenating `nums` with itself. This array of length `2n` contains all possible subarrays of `nums` and all subarrays that wrap around `nums` exactly once. Find the minimum length subarray in `nums2` that sums to `target`. This can be done efficiently using a helper function with a prefix sum map. Let this be `minLen`.
4. **Handle long subarrays:** A long subarray's sum can be decomposed into `k` full copies of `nums` and a remainder part. The `target` can be expressed as `target = (target / S) * S + (target % S)`.
5. Let `num_full_arrays = target / S` and `rem_target = target % S`.
6. A candidate solution can be formed by taking `num_full_arrays` full copies of `nums` (length `num_full_arrays * n`) and a subarray that sums to `rem_target`. The minimum length for this remainder part can be found by searching in `nums2` (as `rem_target < S`, it won't contain a full `nums` copy).
7. Calculate the length for this candidate: `candidate_len = num_full_arrays * n + minSubArrayLen(nums2, rem_target)`. Update `minLen` with this candidate if it's smaller.
8. If `target % S == 0`, the `rem_target` is 0. A subarray of sum 0 has length 0. However, the problem can be seen as taking `(target/S - 1)` full arrays and finding a subarray for sum `S`. So, another candidate length is `(target/S - 1) * n + minSubArrayLen(nums2, S)`.
9. The final answer is the minimum length found among all candidates. If no candidate was found, the answer is -1.

# Solutions
### Java

```java
class Solution {
public
  int minSizeSubarray(int[] nums, int target) {
    long s = Arrays.stream(nums).sum();
    int n = nums.length;
    int a = 0;
    if (target > s) {
      a = n * (target / (int)s);
      target -= target / s * s;
    }
    if (target == s) {
      return n;
    }
    Map<Long, Integer> pos = new HashMap<>();
    pos.put(0L, -1);
    long pre = 0;
    int b = 1 << 30;
    for (int i = 0; i < n; ++i) {
      pre += nums[i];
      if (pos.containsKey(pre - target)) {
        b = Math.min(b, i - pos.get(pre - target));
      }
      if (pos.containsKey(pre - (s - target))) {
        b = Math.min(b, n - (i - pos.get(pre - (s - target))));
      }
      pos.put(pre, i);
    }
    return b == 1 << 30 ? -1 : a + b;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minSizeSubarray(vector<int> &nums, int target) {
    long long s = accumulate(nums.begin(), nums.end(), 0LL);
    int n = nums.size();
    int a = 0;
    if (target > s) {
      a = n * (target / s);
      target -= target / s * s;
    }
    if (target == s) {
      return n;
    }
    unordered_map<int, int> pos{{0, -1}};
    long long pre = 0;
    int b = 1 << 30;
    for (int i = 0; i < n; ++i) {
      pre += nums[i];
      if (pos.count(pre - target)) {
        b = min(b, i - pos[pre - target]);
      }
      if (pos.count(pre - (s - target))) {
        b = min(b, n - (i - pos[pre - (s - target)]));
      }
      pos[pre] = i;
    }
    return b == 1 << 30 ? -1 : a + b;
  }
};

```

### Python

```python
class Solution:
    def minSizeSubarray(self, nums: List[int], target: int) -> int: s = sum(nums) n = len(nums) a = 0 if target > s: a = n * (target // s) target -= target // s * s if target == s: return n pos = {0: - 1} pre = 0 b = inf for i, x in enumerate(nums): pre += x if (t: = pre - target) in pos: b = min(b, i - pos[t]) if (t: = pre - (s - target)) in pos: b = min(b, n - (i - pos[t])) pos[pre] = i return - 1 if b == inf else a + b

```