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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Size Subarray in Infinite Array

Number: 3141

Difficulty: Medium

Paid? No

Companies: DE Shaw

Problem Description

Given an array nums and an integer target, an infinite array is generated by repeating nums indefinitely. Find the length of the shortest contiguous subarray (which might span several copies of nums) that sums exactly to target. Return -1 if no such subarray exists.

Key Insights

  • The infinite array is simply repeated cycles of nums.
  • Since nums contains only positive integers, sums in any contiguous range are strictly increasing as more elements are added.
  • Any valid subarray can either lie completely within one or two cycles, or span multiple cycles.
  • A window that “wraps around” (ends in a later copy than it started) can be decomposed into a suffix from one cycle, a number of full cycles, and a prefix from the next cycle.
  • Precomputing prefix sums for one cycle allows us to use binary search (since the prefix sums are strictly increasing) to check if a given partial sum exists.

Space and Time Complexity

Time Complexity: O(n log n), where n is the length of nums (we iterate over each starting index and do a binary search over the prefix array). Space Complexity: O(n) for storing the prefix sums.

Solution

We can solve the problem by first precomputing the prefix sums for one cycle of nums. For a given start index i in [0,n-1], we consider two cases:

  1. The desired subarray lies within the same cycle.

    • Compute the sum from index i to some index j in the same cycle.
    • Since the prefix sums are strictly increasing, we can binary search for j such that (pre[j] - pre[i]) equals target.

  2. The desired subarray spans multiple cycles.

    • Compute the sum from i to the end of the cycle (suffix).
    • Let rem = target - (sum of suffix). Since the numbers are positive, rem > 0.
    • Notice that additional whole cycles sum to totalSum. Write rem = m*totalSum + x, where 0 <= x <= totalSum.
    • For the subarray to sum exactly to target, x must equal the sum of a prefix of nums (that is, it must appear in the precomputed prefix array). If x is found, the total length is (n - i) + m*n + (prefix length corresponding to x).
    • Specially, if x is zero (i.e. rem is exactly m*totalSum), no extra part is needed.

We iterate over all starting positions and keep track of the minimum candidate length. If no candidate is found, return -1.

Code Solutions

# Python solution with detailed inline comments
def min_subarray_length(nums, target):
    n = len(nums)
    # Build prefix sum array for one cycle: pre[0] = 0, pre[i] = nums[0] + ... + nums[i-1]
    pre = [0] * (n+1)
    for i in range(1, n+1):
        pre[i] = pre[i-1] + nums[i-1]
    totalSum = pre[n]
    
    # Helper: binary search in the prefix list to find an index where value equals target_value.
    def binary_search(target_value):
        lo, hi = 0, len(pre) - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if pre[mid] == target_value:
                return mid
            elif pre[mid] < target_value:
                lo = mid + 1
            else:
                hi = mid - 1
        return -1

    ans = float('inf')
    
    # Iterate over every possible starting index in the cycle.
    for i in range(n):
        # Case 1: subarray entirely in one cycle.
        # The subarray sum from i to j is pre[j] - pre[i]. We need it to equal target.
        required = target + pre[i]
        if required <= pre[n]:
            idx = binary_search(required)
            if idx != -1:
                # Length of the subarray is idx - i.
                ans = min(ans, idx - i)
        
        # Case 2: subarray that spans into later cycles.
        # Sum from i to end of this cycle.
        suffix_sum = pre[n] - pre[i]
        # Only consider if the suffix sum is less than target.
        if suffix_sum < target:
            rem = target - suffix_sum
            # Determine how many complete cycles are needed.
            m = rem // totalSum  # number of full cycles
            # Determine the leftover sum needed from the next cycle.
            leftover = rem - m * totalSum
            # If leftover is 0, it means the chosen cycles exactly meet the target.
            if leftover == 0:
                candidate_length = (n - i) + m * n
                ans = min(ans, candidate_length)
            else:
                # Use binary search to check if leftover exists as prefix sum in a single cycle.
                idx = binary_search(leftover)
                if idx != -1:
                    candidate_length = (n - i) + m * n + idx
                    ans = min(ans, candidate_length)
    
    return ans if ans != float('inf') else -1

# Example usage:
print(min_subarray_length([1,2,3], 5))      # Expected output: 2
print(min_subarray_length([1,1,1,2,3], 4))    # Expected output: 2
print(min_subarray_length([2,4,6,8], 3))      # Expected output: -1
← Back to All Questions