We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Size Subarray in Infinite Array

Difficulty: Medium

Problem Description

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.

Key Insights

  • The array infinite_nums can be viewed as a repetitive sequence of nums.
  • We can utilize prefix sums to efficiently calculate subarray sums.
  • The problem can be approached with a sliding window technique to find the shortest subarray matching the target sum.
  • Since infinite_nums is infinite, we only need to consider a finite number of elements from nums due to its periodic nature.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we can use a combination of prefix sums and a sliding window approach. By calculating the prefix sums of the nums array, we can determine the sums of subarrays efficiently. The key insight is that since infinite_nums is a repeating sequence, we can simulate this by considering the prefix sums up to twice the length of nums. We maintain a hash map to store the indices of previous prefix sums, allowing us to find the length of valid subarrays whose sums equal the target.

Code Solutions

def min_subarray_len(nums, target):
    n = len(nums)
    prefix_sum = [0] * (n * 2 + 1)
    
    # Calculate prefix sums for two cycles of nums
    for i in range(n):
        prefix_sum[i + 1] = prefix_sum[i] + nums[i]
    
    min_length = float('inf')
    prefix_indices = {}
    
    # Store prefix sums and their indices
    for i in range(2 * n + 1):
        prefix_indices[prefix_sum[i] % target] = i

        # Check for valid subarray
        if prefix_sum[i] >= target:
            for j in range(i):
                if prefix_sum[i] - prefix_sum[j] == target:
                    min_length = min(min_length, i - j)
    
    return min_length if min_length != float('inf') else -1
← Back to All Questions