Problem Description

You have a 0-indexed array nums and an integer target.

The problem asks you to imagine creating an infinite array called infinite_nums by repeatedly appending the entire nums array to itself forever. For example, if nums = [1, 2, 3], then infinite_nums = [1, 2, 3, 1, 2, 3, 1, 2, 3, ...].

Your task is to find the shortest contiguous subarray within this infinite array whose elements sum up to exactly target. Return the length of this shortest subarray. If no such subarray exists, return -1.

The key insight is that since the array repeats infinitely, you might need to use elements that span across multiple copies of the original array. For instance, if nums = [1, 2, 3] and target = 7, you could use the subarray [3, 1, 2, 1] which spans across two copies of the original array (ending elements from one copy and beginning elements from the next).

The solution cleverly handles this by:

1. First calculating how many complete copies of the array might be needed (when target is large)
2. Reducing the problem to finding a subarray with a smaller target value
3. Using prefix sums and a hash table to efficiently find the shortest valid subarray that might wrap around the array boundaries

Intuition

Since we're dealing with an infinite array created by repeating nums, we need to think about patterns. If the sum of the entire nums array is s, then any large target can be broken down into:

• Some number of complete copies of the array (each contributing s to the sum)
• A remaining portion that's less than s

For example, if nums = [1, 2, 3] with sum s = 6, and target = 20, we can think of it as 3 complete arrays (contributing 18) plus a remaining target of 2.

This leads to the first key insight: if target > s, we can use target // s complete copies of the array, which gives us a length of n * (target // s) elements. Then we reduce our problem to finding a subarray with sum equal to target % s.

The second insight involves handling the "wrap-around" case. In an infinite array, a subarray might start in the middle of one copy and end in the middle of the next copy. We can think of this in two ways:

1. A contiguous subarray within a single copy of nums with sum equal to the reduced target
2. A suffix of one copy plus a prefix of the next copy

For case 2, if we take a suffix with sum x and a prefix with sum y, where x + y = target, this is equivalent to saying the middle portion we're NOT taking has sum s - target. So we're looking for the shortest "gap" in the array that sums to s - target.

Using prefix sums and a hash table, we can efficiently check:

• For each position, if there's a previous position where the difference in prefix sums equals target (finding a contiguous subarray)
• For each position, if there's a previous position where the difference in prefix sums equals s - target (finding the "gap" we can skip, which gives us the wrap-around subarray)

The beauty of this approach is that it reduces an infinite array problem to examining just one or two copies of the original array, making it computationally feasible.

Learn more about Prefix Sum and Sliding Window patterns.

Solution Approach

Let's walk through the implementation step by step:

Step 1: Calculate the sum and handle large targets

First, we calculate s = sum(nums) and n = len(nums). We initialize a = 0 to track the length contribution from complete array copies.

If target > s, we know we'll need at least target // s complete copies of the array. So:

• a = n * (target // s) - this is the length from complete copies
• target = target % s - reduce target to the remainder

If target == s after reduction, we just need exactly one more complete copy, so we return n.

Step 2: Set up prefix sum tracking

We use a hash table pos = {0: -1} to store prefix sums and their positions. The key is the prefix sum value, and the value is the index where this sum occurs. We initialize with 0: -1 to handle cases where the subarray starts from index 0.

We also initialize:

• pre = 0 to track the running prefix sum
• b = inf to track the minimum length of the subarray we're looking for

Step 3: Process each element

For each element x at index i:

1. Update the prefix sum: pre += x

2. Check for direct subarray: If pre - target exists in pos, it means there's a previous position j where the sum from position j+1 to i equals target. The length of this subarray is i - pos[pre - target].

3. Check for wrap-around subarray: If pre - (s - target) exists in pos, it means we can "skip" a middle portion that sums to s - target. This gives us a suffix (from some position to the end) plus a prefix (from start to current position). The length is n - (i - pos[pre - (s - target)]), which simplifies to the total array length minus the length of the skipped portion.

4. Update the hash table: pos[pre] = i

Step 4: Return the result

If b remains inf, no valid subarray was found, so return -1. Otherwise, return a + b, where:

• a is the length from complete array copies
• b is the length of the shortest subarray found in our search

The algorithm efficiently handles both regular subarrays and wrap-around cases in a single pass through the array, using O(n) time and O(n) space complexity.

Example Walkthrough

Let's walk through a concrete example with nums = [1, 2, 3] and target = 7.

Initial Setup:

• Array: nums = [1, 2, 3]
• Sum of array: s = 6
• Length: n = 3
• Target: 7

Step 1: Handle large target

• Since target = 7 > s = 6, we need at least one complete copy
• Complete copies needed: 7 // 6 = 1
• Length from complete copies: a = 3 * 1 = 3
• Reduced target: target = 7 % 6 = 1

Now we need to find a subarray with sum = 1 (considering wrap-around).

Step 2: Initialize tracking

• pos = {0: -1} (maps prefix sum → index)
• pre = 0 (running prefix sum)
• b = inf (minimum subarray length)

Step 3: Process each element

Index 0: nums[0] = 1

• Update prefix sum: pre = 0 + 1 = 1
• Check direct subarray: pre - target = 1 - 1 = 0 ✓ exists in pos!
  • Length = 0 - (-1) = 1
  • Update b = min(inf, 1) = 1
• Check wrap-around: pre - (s - target) = 1 - 5 = -4 ✗ not in pos
• Update pos: pos = {0: -1, 1: 0}

Index 1: nums[1] = 2

• Update prefix sum: pre = 1 + 2 = 3
• Check direct subarray: pre - target = 3 - 1 = 2 ✗ not in pos
• Check wrap-around: pre - (s - target) = 3 - 5 = -2 ✗ not in pos
• Update pos: pos = {0: -1, 1: 0, 3: 1}

Index 2: nums[2] = 3

• Update prefix sum: pre = 3 + 3 = 6
• Check direct subarray: pre - target = 6 - 1 = 5 ✗ not in pos
• Check wrap-around: pre - (s - target) = 6 - 5 = 1 ✓ exists in pos!
  • This means we can skip elements from index 1 to 2 (sum = 5)
  • Take suffix [from index 2] + prefix [up to index 0]
  • Length = 3 - (2 - 0) = 1
  • Update b = min(1, 1) = 1

Step 4: Return result

• Total length = a + b = 3 + 1 = 4

Verification: In the infinite array [1, 2, 3, 1, 2, 3, ...], the subarray of length 4 starting at index 2 is [3, 1, 2, 3] with sum = 7 ✓

But wait! We found b = 1, which corresponds to just taking element [1] with sum = 1. Combined with one complete copy (sum = 6), we get 6 + 1 = 7. This gives us the subarray [1, 2, 3, 1] with length 4, which is indeed the shortest subarray summing to 7.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. The algorithm performs a single pass through the array with a for loop that iterates through each element exactly once. Within each iteration, all operations are constant time: computing the prefix sum, checking dictionary membership, updating the minimum value, and inserting into the dictionary are all O(1) operations.

The space complexity is O(n), where n is the length of the array nums. The primary space consumer is the pos dictionary which stores prefix sums as keys and their corresponding indices as values. In the worst case, all prefix sums are unique, resulting in the dictionary storing up to n+1 entries (including the initial entry {0: -1}). All other variables (s, n, a, target, pre, b) use constant space.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Handle the Wraparound Case

Pitfall: Many solutions only consider contiguous subarrays within a single copy of the array and forget that the infinite array allows subarrays to wrap around from the end of one copy to the beginning of the next.

Example:

• nums = [1, 2, 3], target = 5
• A solution might only find [2, 3] with length 2
• But miss the wraparound option [3, 1, 1] which would give us [3] + [1, 1] from the next copy

Solution: Always check both cases:

1. Regular subarray: Look for current_prefix_sum - target
2. Wraparound subarray: Look for current_prefix_sum - (total_sum - target)

2. Incorrect Handling of the Modulo Operation

Pitfall: After reducing target using modulo (target % total_sum), forgetting to check if the result is 0, which means we need exactly complete arrays.

Example:

• nums = [1, 2, 3], target = 12 (sum = 6)
• After modulo: target = 12 % 6 = 0
• This doesn't mean no elements are needed; it means we need exactly 2 complete arrays

Solution: Add a special check after the modulo operation:

if target == 0:
    return complete_cycles_length  # Return the length from complete cycles only

3. Not Initializing the Prefix Sum Dictionary Correctly

Pitfall: Forgetting to initialize prefix_sum_to_index with {0: -1}. This initialization is crucial for handling subarrays that start from index 0.

Example:

• nums = [2, 3, 5], target = 5
• The subarray [2, 3] starts at index 0
• Without {0: -1}, when we reach index 1 with prefix_sum = 5, we can't find prefix_sum - target = 0 in our dictionary

Solution: Always initialize with:

prefix_sum_to_index = {0: -1}

4. Integer Overflow with Large Targets

Pitfall: When target is very large and we calculate complete_cycles_length = array_length * complete_cycles, this multiplication might cause integer overflow in some languages (though Python handles big integers automatically).

Solution: In languages with fixed integer sizes, use appropriate data types or check for overflow:

# In Python this is handled automatically, but in other languages:
# Use long long in C++ or check for overflow before multiplication
if complete_cycles > MAX_INT // array_length:
    # Handle overflow case

5. Updating Dictionary Before Checking Both Cases

Pitfall: Updating prefix_sum_to_index[current_prefix_sum] = index before checking both the regular and wraparound cases. This could overwrite a previous occurrence of the same prefix sum that might give a shorter subarray.

Example:

• If we update immediately after calculating current_prefix_sum, we might miss using an earlier occurrence of the same sum

Solution: Always perform both checks first, then update the dictionary:

# First: Check both cases
if required_prefix in prefix_sum_to_index:
    # Handle regular case
if wrap_required_prefix in prefix_sum_to_index:
    # Handle wraparound case

# Then: Update the dictionary
prefix_sum_to_index[current_prefix_sum] = index