Minimum Size Subarray in Infinite Array
MedPrompt
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 <= 1051 <= nums[i] <= 1051 <= target <= 109
Approaches
2 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Iterate through each possible starting position
ifrom0ton-1, wherenis the length ofnums. - For each starting position
i, simulate building a subarray in theinfinite_numsarray. - Initialize
currentSum = 0andcurrentLength = 0. - Start a loop that iterates through the
infinite_numsarray, starting from indexi. The index in the originalnumsarray can be calculated using the modulo operator:nums[j % n]. - In each step of the inner loop, add the current element to
currentSumand incrementcurrentLength. - If
currentSumequalstarget, we have found a valid subarray. Update the global minimum length withcurrentLengthand break the inner loop (since we are looking for the shortest subarray starting ati). - If
currentSumexceedstarget, we can also break the inner loop because all numbers are positive, so the sum will only increase. - After checking all starting positions from
0ton-1, if a minimum length was found, return it. Otherwise, return -1.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Calculate the total sum
Sof the elements innumsand its lengthn. - Any solution subarray is either short (length <= 2n) or long (contains full copies of
nums). - Handle short subarrays: Create a temporary array
nums2by concatenatingnumswith itself. This array of length2ncontains all possible subarrays ofnumsand all subarrays that wrap aroundnumsexactly once. Find the minimum length subarray innums2that sums totarget. This can be done efficiently using a helper function with a prefix sum map. Let this beminLen. - Handle long subarrays: A long subarray's sum can be decomposed into
kfull copies ofnumsand a remainder part. Thetargetcan be expressed astarget = (target / S) * S + (target % S). - Let
num_full_arrays = target / Sandrem_target = target % S. - A candidate solution can be formed by taking
num_full_arraysfull copies ofnums(lengthnum_full_arrays * n) and a subarray that sums torem_target. The minimum length for this remainder part can be found by searching innums2(asrem_target < S, it won't contain a fullnumscopy). - Calculate the length for this candidate:
candidate_len = num_full_arrays * n + minSubArrayLen(nums2, rem_target). UpdateminLenwith this candidate if it's smaller. - If
target % S == 0, therem_targetis 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 sumS. So, another candidate length is(target/S - 1) * n + minSubArrayLen(nums2, S). - The final answer is the minimum length found among all candidates. If no candidate was found, the answer is -1.
Walkthrough
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.
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.
Complexity
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.
Trade-offs
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
targetis a multiple of the array sum.Uses extra space for the doubled array and the prefix sum map.
Solutions
Solution
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; }}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; }};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 + bVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.