Is Minimum Size Subarray in Infinite Array easy or hard?

Minimum Size Subarray in Infinite Array is rated Medium difficulty on LeetCode with an acceptance rate around 32%. The difficulty comes from recognizing that the infinite array can be handled by counting full cycles and then applying a sliding window to a limited range.

Minimum Size Subarray in Infinite Array Python/Java solution

Python, Java, and C++ implementations typically follow the same structure: compute the array sum, reduce the target by full cycles, then run a sliding window across two concatenated copies of the array. This keeps the implementation linear and avoids building an infinite structure.

How to solve Minimum Size Subarray in Infinite Array in O(n)?

Compute the total sum of the array and remove as many full cycles from the target as possible. After that, run a sliding window across a doubled version of the array to detect the smallest subarray that sums to the remaining value. Because each pointer only moves forward, the scan completes in linear time.

What is the best approach for Minimum Size Subarray in Infinite Array?

The sliding window approach combined with cycle reduction is the most efficient solution. First compute how many full repetitions of the array fit into the target using the total array sum. Then apply a sliding window over at most two copies of the array to find the smallest subarray for the remaining value. This runs in O(n) time with O(1) extra space.

Is Minimum Size Subarray in Infinite Array asked at Google/Amazon/Meta?

Problems combining sliding window and prefix sum patterns frequently appear in interviews at companies like Google, Amazon, and Meta. Variants involving minimum subarray length, repeated arrays, or circular arrays are common because they test pointer techniques and reasoning about prefix sums.

What data structure is used in Minimum Size Subarray in Infinite Array?

The most common solution uses a sliding window with two pointers and a running sum. An alternative method uses a prefix sum array with a hash map to store previously seen sums and detect target differences efficiently.

What is the time complexity of Minimum Size Subarray in Infinite Array?

The optimal solution runs in O(n) time, where n is the length of the input array. Each element is processed at most twice during the sliding window scan of the doubled array. Space complexity is O(1) for the sliding window approach or O(n) if using a prefix sum hash map.

Description Hints 2 Solution Video 9:35

2875. Minimum Size Subarray in Infinite Array

Medium32.1% acceptance1 company

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 <= 10⁵
1 <= nums[i] <= 10⁵
1 <= target <= 10⁹

Asked at 1 company

D. E. Shaw

Topics

Hints open one at a time

Hint 1

Notice that, target is either: A subarray of nums, or prefix_sum[i] + k * sum(nums) + suffix_sum[j] for some i, j, k.

Hint 2

You can solve the problem for those two separate cases using hash map and prefix sums.

9:35

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def minSizeSubarray(self, nums: List[int], target: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[1,2,3]
5

Input

[1,1,1,2,3]
4

Input

[2,4,6,8]
3

Your code is saved on this device.Solution