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 <= 109Problem Overview: You are given an array nums that repeats infinitely. The goal is to find the minimum length subarray whose sum equals target. Because the array is conceptually infinite, the key challenge is handling repeated cycles efficiently without actually constructing an infinite structure.
Approach 1: Sliding Window with Cycle Reduction (O(n) time, O(1) space)
The optimal observation is that the array repeats, so you can consume full cycles first. Compute the total sum of nums. If target is larger than this sum, determine how many complete repetitions of the array fit into the target using integer division. This contributes a fixed length equal to k * n. After removing these full cycles, the remaining target can be found using a classic sliding window on a doubled version of the array. The window expands with a right pointer and shrinks from the left whenever the running sum exceeds the remainder. This works because all numbers are positive, guaranteeing that the window sum grows monotonically when expanding.
The sliding window only needs to scan at most 2n elements to capture wrap‑around subarrays. Each element is processed at most twice, giving O(n) time and constant extra memory. This approach is usually the fastest in practice because it avoids additional hash structures and relies only on two pointers and a running sum.
Approach 2: Prefix Sum + Hash Map (O(n) time, O(n) space)
A more general technique uses prefix sums combined with a hash table. Compute prefix sums while iterating over a duplicated array to simulate wrap‑around. For each position, check whether current_prefix - target exists in the map. If it does, the subarray between those indices sums to the required value. Store the earliest index for each prefix value so the resulting subarray length stays minimal.
This method works for a wider range of problems, including cases where sliding window cannot be used (for example when negative numbers appear). Each prefix lookup is an O(1) hash operation, so the overall complexity remains O(n) time with O(n) additional space.
Recommended for interviews: The sliding window solution is typically expected because the array contains positive integers and the problem naturally reduces to a two‑pointer scan after accounting for full cycles. Mentioning the prefix sum + hash map approach shows broader algorithm knowledge, but the sliding window version demonstrates stronger optimization and pattern recognition.
The Sliding Window approach is useful here. Since infinite_nums is an extension of nums repeated, the key is to determine how many repetitions are necessary to ensure handling subarray sums. You'd expand the array to a length that covers potential sums greater than or equal to the target.
This solution extends the nums array as many times as necessary to find subarray sums large enough to meet or exceed the target. It uses a sliding window approach to efficiently find the minimum-length subarray.
We utilize the logic that if we need a specific sum, at most a few complete repetitions of the array need to be considered.
Time Complexity: O(n), where n is the number of repeated nums elements needed.
Space Complexity: O(n), due to additional space for storing the extended version of nums.
Using Prefix Sum and HashMap is an alternative approach to solve this problem, where we calculate prefix sums and use a hashmap to keep track of sums encountered and their earliest indices.
This approach works on the assumption of also extending nums pseudo-infinitely for analysis but uses prefix sums to avoid recalculations.
In this code, the prefix sums are calculated as we traverse through a virtually extended version of nums. The hashmap keeps track of the earliest occurrence of each prefix sum, and this information helps decide where balanced subarrays are available.
Python
C#
JavaScript
Time Complexity: O(n), effectively it traverses each subarray once per needed repetitions.
Space Complexity: O(n), space is preserved by storing only prefix sums necessary.
First, we calculate the sum of all elements in the array nums, denoted as s.
If target \gt s, we can reduce target to the range [0, s) by subtracting \lfloor \frac{target}{s} \rfloor times s from it. Then, the length of the subarray is a = \lfloor \frac{target}{s} \rfloor times n, where n is the length of the array nums.
Next, we need to find the shortest subarray in nums whose sum equals target, or the shortest subarray whose prefix sum plus suffix sum equals s - target. We can use prefix sum and a hash table to find such subarrays.
If we find such a subarray, the final answer is a + b. Otherwise, the answer is -1.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the array nums.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Sliding Window Approach | Time Complexity: O(n), where n is the number of repeated nums elements needed. |
| Prefix Sum and HashMap | Time Complexity: O(n), effectively it traverses each subarray once per needed repetitions. |
| Prefix Sum + Hash Table | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window with Cycle Reduction | O(n) | O(1) | Best choice when array elements are positive and window sums grow monotonically |
| Prefix Sum + Hash Map | O(n) | O(n) | Useful when sliding window conditions fail or when demonstrating a general subarray sum technique |
2875. Minimum Size Subarray in Infinite Array || Sliding Window 🔥 || Maths 🔥 • Ayush Rao • 2,559 views views
Watch 9 more video solutions →Practice Minimum Size Subarray in Infinite Array with our built-in code editor and test cases.
Practice on FleetCode