LeetCode Problem 2875

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Sliding Window, Prefix Sum

Solution

LeetCode 2875 - Minimum Size Subarray in Infinite Array

Problem Understanding

This problem gives us a finite array nums, but asks us to imagine an infinite array called infinite_nums created by repeating nums forever.

For example:

nums = [1, 2, 3]

infinite_nums =
[1,2,3,1,2,3,1,2,3,1,2,3,...]

We must find the shortest contiguous subarray in this infinite sequence whose sum is exactly equal to target.

The key challenge is that the array is conceptually infinite. We obviously cannot build or iterate through an infinite structure. Instead, we must exploit the repeating nature of the array.

The input consists of:

• nums, a positive integer array.
• target, the desired subarray sum.

The output is:

• The minimum possible length of a contiguous subarray whose sum equals target.
• -1 if no such subarray exists.

The constraints are important:

• nums.length can be as large as 100,000.
• Each element can be as large as 100,000.
• target can be as large as 1,000,000,000.

These constraints immediately rule out any quadratic or brute force exploration of subarrays.

An important observation is that every element is positive. This property makes sliding window techniques possible because window sums increase when extending the right side and decrease when moving the left side.

Several edge cases deserve attention:

• The target may be much larger than the sum of one copy of nums.
• The answer may span multiple repetitions of the array.
• The answer may wrap around the end of one copy and continue into the next.
• There may be no valid subarray at all.
• The shortest answer might consist of many complete copies of nums plus a small remainder.

Approaches

Brute Force

A straightforward approach is to explicitly simulate several repetitions of the array and examine every possible subarray.

For every starting position, we could keep extending the subarray until the sum reaches or exceeds the target. If the sum becomes exactly equal to the target, we update the minimum length.

This approach is correct because it checks all possible subarrays.

However, it is far too slow. Even examining all subarrays of a doubled or tripled array already requires quadratic work. With n = 100,000, this becomes completely infeasible.

Key Insight

The crucial observation is that the array repeats infinitely and all values are positive.

Let:

total = sum(nums)

Suppose:

target = k * total + remainder

where:

k = target // total
remainder = target % total

If we use k complete copies of the array, we already contribute:

k * total

to the sum while adding:

k * n

elements to the length.

The remaining task is to find the shortest subarray whose sum equals remainder.

There is one subtle case:

If remainder = 0, then exactly k complete copies of the array achieve the target, and the answer is simply:

k * n

Otherwise, we need a shortest subarray with sum remainder.

Since the array is circular because of repetition, any such subarray can be found inside at most two consecutive copies of nums.

Therefore:

1. Build nums + nums.
2. Use a sliding window to find the shortest subarray whose sum equals remainder.
3. Add its length to k * n.

There is one more possibility. Sometimes using one fewer full copy can produce a shorter answer.

Specifically, if:

target = k * total + remainder

then we may also consider:

total - remainder

inside the doubled array.

A subarray summing to total - remainder corresponds to removing a segment from one complete cycle, potentially reducing the overall length.

The final answer is the minimum among these possibilities.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²) or worse	O(1)	Examines many subarrays explicitly
Optimal	O(n)	O(n)	Uses arithmetic decomposition and sliding window on two copies

Algorithm Walkthrough

1. Compute the length of the array n and the total sum total.
2. Compute:

fullCycles = target // total
remainder = target % total

3. If remainder == 0, then exactly fullCycles complete copies of the array produce the target sum. Return:

fullCycles * n

4. Create:

doubled = nums + nums

Any shortest circular subarray must appear within these two consecutive copies. 5. Define a helper function that finds the shortest subarray in doubled whose sum equals a given value want. 6. Because all numbers are positive, use a sliding window:

• Expand the right pointer.
• While the sum exceeds want, move the left pointer.
• Whenever the sum equals want, update the minimum length.

7. Find the shortest subarray whose sum equals:

remainder

If one exists, a candidate answer is:

fullCycles * n + length

8. Also search for:

total - remainder

If such a subarray exists, we can use:

(fullCycles + 1) * n - length

This corresponds to taking one additional full cycle and removing a segment. 9. Return the minimum valid candidate. 10. If neither candidate exists, return -1.

Why it works

Every valid subarray in the infinite array can be represented as some number of complete array cycles plus a partial segment crossing at most one boundary between consecutive copies. Since all elements are positive, any shortest segment representing a particular remainder can be found using a sliding window over two copies of the array. Considering both remainder and total - remainder covers the two possible ways a shortest solution can be formed, guaranteeing that the minimum valid length is found.

Python Solution

from typing import List

class Solution:
    def minSizeSubarray(self, nums: List[int], target: int) -> int:
        n = len(nums)
        total = sum(nums)

        full_cycles = target // total
        remainder = target % total

        if remainder == 0:
            return full_cycles * n

        doubled = nums + nums

        def shortest_subarray(want: int) -> int:
            left = 0
            curr_sum = 0
            best = float("inf")

            for right, value in enumerate(doubled):
                curr_sum += value

                while curr_sum > want:
                    curr_sum -= doubled[left]
                    left += 1

                if curr_sum == want:
                    best = min(best, right - left + 1)

            return best

        answer = float("inf")

        length1 = shortest_subarray(remainder)
        if length1 != float("inf"):
            answer = min(answer, full_cycles * n + length1)

        length2 = shortest_subarray(total - remainder)
        if length2 != float("inf"):
            answer = min(
                answer,
                (full_cycles + 1) * n - length2
            )

        return -1 if answer == float("inf") else answer

The implementation begins by computing the sum of one cycle of the array. This allows the target to be decomposed into complete cycles and a remaining amount.

If the target is exactly divisible by the cycle sum, no partial segment is needed and the answer is immediately known.

Otherwise, the array is duplicated. Any subarray that wraps around the end of one cycle and into the next must appear as a normal contiguous subarray inside this doubled array.

The helper function performs a standard sliding window search. Because all elements are positive, once the current sum exceeds the desired value, moving the left pointer is always safe and eventually reduces the sum.

Two searches are performed, one for remainder and one for total - remainder. Each produces a candidate answer, and the smallest valid candidate is returned.

Go Solution

func minSizeSubarray(nums []int, target int) int {
	n := len(nums)

	total := 0
	for _, v := range nums {
		total += v
	}

	fullCycles := target / total
	remainder := target % total

	if remainder == 0 {
		return fullCycles * n
	}

	doubled := make([]int, 0, 2*n)
	doubled = append(doubled, nums...)
	doubled = append(doubled, nums...)

	const INF = int(1e9)

	shortestSubarray := func(want int) int {
		left := 0
		currSum := 0
		best := INF

		for right, value := range doubled {
			currSum += value

			for currSum > want {
				currSum -= doubled[left]
				left++
			}

			if currSum == want {
				length := right - left + 1
				if length < best {
					best = length
				}
			}
		}

		return best
	}

	answer := INF

	length1 := shortestSubarray(remainder)
	if length1 != INF {
		candidate := fullCycles*n + length1
		if candidate < answer {
			answer = candidate
		}
	}

	length2 := shortestSubarray(total - remainder)
	if length2 != INF {
		candidate := (fullCycles+1)*n - length2
		if candidate < answer {
			answer = candidate
		}
	}

	if answer == INF {
		return -1
	}

	return answer
}

The Go implementation follows exactly the same logic as the Python version. Integer arithmetic is safe because the largest possible answer is on the order of the target divided by the minimum element, which remains well within Go's int range on LeetCode. Slices are used to construct the doubled array efficiently, and a closure implements the sliding window helper.

Worked Examples

Example 1

nums = [1,2,3]
target = 5

Compute:

Variable	Value
total	6
fullCycles	0
remainder	5

Search for sum = 5 in:

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

Right	Window	Sum	Best
0	[1]	1	inf
1	[1,2]	3	inf
2	[2,3]	5	2
3	[2,3,1]	6	2
4	[3,1,2]	6	2
5	[2,3]	5	2

Candidate:

0 * 3 + 2 = 2

Answer:

2

Example 2

nums = [1,1,1,2,3]
target = 4

Compute:

Variable	Value
total	8
fullCycles	0
remainder	4

Doubled array:

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

Shortest subarray with sum 4:

[3,1]

Length:

2

Answer:

2

Example 3

nums = [2,4,6,8]
target = 3

Compute:

Variable	Value
total	20
fullCycles	0
remainder	3

No subarray in the doubled array can sum to 3 because every element is even and at least 2.

Both searches fail.

Answer:

-1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each sliding window pass processes every element at most once
Space	O(n)	The doubled array contains 2n elements

The doubled array requires linear extra memory. The sliding window itself uses constant additional space. Since each pointer only moves forward, each helper call is linear. Two helper calls still result in overall O(n) time complexity.

Test Cases

sol = Solution()

assert sol.minSizeSubarray([1, 2, 3], 5) == 2          # example 1
assert sol.minSizeSubarray([1, 1, 1, 2, 3], 4) == 2   # example 2
assert sol.minSizeSubarray([2, 4, 6, 8], 3) == -1     # example 3

assert sol.minSizeSubarray([5], 5) == 1               # single element exact match
assert sol.minSizeSubarray([5], 10) == 2              # multiple full cycles
assert sol.minSizeSubarray([5], 3) == -1              # impossible target

assert sol.minSizeSubarray([1, 2, 3], 6) == 3         # exactly one full cycle
assert sol.minSizeSubarray([1, 2, 3], 12) == 6        # exactly two full cycles

assert sol.minSizeSubarray([1, 2, 3], 7) == 4         # cycle plus remainder
assert sol.minSizeSubarray([3, 2, 1], 4) == 2         # wrapped subarray

assert sol.minSizeSubarray([2, 2, 2], 8) == 4         # multiple cycles needed
assert sol.minSizeSubarray([1, 1, 1], 100) == 100     # large target

assert sol.minSizeSubarray([4, 1, 2], 3) == 2         # wrap-around segment
assert sol.minSizeSubarray([8, 5, 3], 11) == -1       # impossible remainder

Test Summary

Test	Why
[1,2,3], 5	Basic example
[1,1,1,2,3], 4	Shortest segment across repetitions
[2,4,6,8], 3	No solution exists
[5], 5	Single-element exact match
[5], 10	Multiple complete cycles
[5], 3	Single-element impossible target
[1,2,3], 6	Exact cycle sum
[1,2,3], 12	Multiple exact cycles
[1,2,3], 7	Full cycle plus remainder
[3,2,1], 4	Wrapped segment
[2,2,2], 8	Requires crossing cycles
[1,1,1], 100	Very large target
[4,1,2], 3	Circular remainder segment
[8,5,3], 11	Impossible combination

Edge Cases

Target Is Exactly a Multiple of the Array Sum

Consider:

nums = [1,2,3]
target = 12

The target equals two complete copies of the array. A common mistake is to continue searching for partial segments even though none are needed. The implementation immediately returns fullCycles * n whenever the remainder is zero, producing the optimal answer efficiently.

Solution Wraps Around the End of the Array

Consider:

nums = [1,1,1,2,3]
target = 4

The shortest valid segment may begin near the end of one copy and continue into the next. A solution that only examines a single copy of the array would miss these cases. By searching within nums + nums, every wrapped segment becomes an ordinary contiguous subarray.

Very Large Targets

Consider:

nums = [1,1,1]
target = 1_000_000_000

Constructing an infinite array or repeatedly extending windows across millions of cycles would be impossible. The implementation first extracts the contribution of complete cycles using division, reducing the problem to finding a remainder inside at most two copies of the array. This keeps the runtime linear regardless of how large target becomes.

No Valid Subarray Exists

Consider:

nums = [2,4,6,8]
target = 3

Neither the remainder search nor the complementary search finds a valid segment. The implementation tracks whether any candidate answer was discovered and correctly returns -1 when none exist.