Watch 10 video solutions for Minimum Size Subarray in Infinite Array, a medium level problem involving Array, Hash Table, Sliding Window. This walkthrough by Ayush Rao has 2,559 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |