Minimum Size Subarray in Infinite Array - Practice Coding Problems

Minimum Size Subarray in Infinite Array - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,2,3], target = 5

› Output: 2

💡 Note: In the infinite array [1,2,3,1,2,3,1,2,3,...], the subarray [2,3] has sum 5 and length 2, which is the minimum possible.

Example 2 — Wraparound

$ Input: nums = [1,4,4], target = 5

› Output: 2

💡 Note: The infinite array is [1,4,4,1,4,4,...]. The subarray [4,1] (wrapping around) has sum 5 and length 2.

Example 3 — No Solution

$ Input: nums = [2,4,6,8], target = 3

› Output: -1

💡 Note: All elements are even, so no combination can sum to the odd target 3.

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁶
1 ≤ target ≤ 10⁸

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,2,3] repeated infinitely, target = 5

Process

Find shortest contiguous subarray summing to target

Output

Return length 2 (subarray [2,3])

Key Takeaway

🎯 Key Insight: The minimum subarray length in an infinite array is bounded by 2×n, making the problem tractable with finite array extensions

Asked in

G Google 45 a Amazon 38 M Microsoft 32 f Meta 28

The key insight is that the minimum subarray length cannot exceed 2×n, so we only need to consider a finite portion of the infinite array. The optimal approach uses prefix sums with hash map to find subarray sums efficiently. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Generate Infinite Array	O(n³)	O(n)	Generate multiple copies of the array and check all possible subarrays
Sliding Window with Prefix Sum	O(n²)	O(n)	Use sliding window technique with array repetition and prefix sum optimization
Prefix Sum with Hash Map	O(n)	O(n)	Use prefix sums and hash map to find subarray with target sum efficiently

Brute Force - Generate Infinite Array — Algorithm Steps

Generate 3 copies of the original array
For each starting position, calculate subarray sums
Track the minimum length that equals target

Visualization

Tap to expand

Step-by-Step Walkthrough

Extend Array

Create multiple copies: [1,2,3] → [1,2,3,1,2,3,1,2,3]

Check Subarrays

Try all starting positions and lengths

Find Minimum

Return shortest subarray with target sum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(int* nums, int numsSize, int target) {
    // Create extended array with 3 copies
    int* extended = (int*)malloc(numsSize * 3 * sizeof(int));
    for (int i = 0; i < 3; i++) {
        memcpy(extended + i * numsSize, nums, numsSize * sizeof(int));
    }
    
    int minLength = INT_MAX;
    
    // Try all possible starting positions
    for (int start = 0; start < numsSize * 2; start++) {
        int currentSum = 0;
        // Try all possible lengths
        for (int length = 1; length <= numsSize * 2; length++) {
            if (start + length > numsSize * 3) break;
            currentSum += extended[start + length - 1];
            if (currentSum == target) {
                if (length < minLength) {
                    minLength = length;
                }
                break;
            } else if (currentSum > target) {
                break;
            }
        }
    }
    
    free(extended);
    return minLength == INT_MAX ? -1 : minLength;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n') {
            nums[numsSize++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int target;
    scanf("%d", &target);
    
    int result = solution(nums, numsSize, target);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Triple nested loops: O(n) start positions × O(n) lengths × O(n) sum calculation

⚠ Quadratic Growth

Space Complexity

O(n)

Extra space to store multiple copies of the array

⚡ Linearithmic Space

28.5K Views

Medium-High Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Generate Infinite Array — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler