Skip to main content
Talentd

Minimum Size Subarray in Infinite Array - Solution & Explanation

MediumArrayHash TableSliding WindowPrefix Sum16 min readAsked at: De Shaw
Practice this problem

Problem Statement

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

Approach Overview

Problem 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 1: Sliding Window Approach

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.

Code

PythonJavaC++

Python

Java

C++

Complexity

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.

Try this approach in the editor →

Approach 2: Prefix Sum and HashMap

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.

Code

PythonC#JavaScript

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: Prefix Sum + Hash Table

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sliding Window Approach

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.

Prefix Sum and HashMap

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.

Prefix Sum + Hash Table—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sliding Window with Cycle ReductionO(n)O(1)Best choice when array elements are positive and window sums grow monotonically
Prefix Sum + Hash MapO(n)O(n)Useful when sliding window conditions fail or when demonstrating a general subarray sum technique

Video Solution

2875. Minimum Size Subarray in Infinite Array || Sliding Window 🔥 || Maths 🔥 • Ayush Rao • 2,634 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Minimum Size Subarray in Infinite Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays