#2875

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Minimum Size Subarray in Infinite Array

Find the shortest subarray in an infinite array that sums to a given target using array scanning and hash lookup.

array hash table sliding window prefix sum

Problem Statement

You are given a 0-indexed array nums and an integer target. An infinite array infinite_nums is created by repeatedly appending the elements of nums to itself.

Return the length of the shortest subarray in infinite_nums that sums up to the target. If no such subarray exists, return -1.

Examples

Example 1

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

Output: 2

In this example infinite_nums = [1,2,3,1,2,3,1,2,...]. The subarray in the range [1,2], has the sum equal to target = 5 and length = 2. It can be proven that 2 is the shortest length of a subarray with sum equal to target = 5.

Example 2

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

Output: 2

In this example infinite_nums = [1,1,1,2,3,1,1,1,2,3,1,1,...]. The subarray in the range [4,5], has the sum equal to target = 4 and length = 2. It can be proven that 2 is the shortest length of a subarray with sum equal to target = 4.

Example 3

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

Output: -1

In this example infinite_nums = [2,4,6,8,2,4,6,8,...]. It can be proven that there is no subarray with sum equal to target = 3.

Constraints

1 <= nums.length <= 105
1 <= nums[i] <= 105
1 <= target <= 109

Solution Approach

Sliding Window + Hash Table

Start by tracking the prefix sums of the array and using a sliding window approach. Use a hash table to record the indices of the prefix sums and check if the difference between the current prefix sum and a prior one equals the target.

Array Scanning

By iterating through the array and tracking cumulative sums with the sliding window, you'll be able to find subarrays that satisfy the target sum. The key is leveraging the repeating nature of the infinite array to minimize the subarray length.

Prefix Sum + Mathematical Insight

To handle the infinite array, you can mathematically break the problem into handling subarrays that start within one cycle of nums and extend beyond it. This insight connects the problem to prefix sums and periodic patterns.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the chosen approach. The sliding window and hash table method generally has a time complexity of O(n), while space complexity depends on how the hash table is implemented, usually O(n) for storing prefix sums.

What Interviewers Usually Probe

Look for familiarity with sliding window and hash table patterns.
Assess the candidate's ability to handle large arrays and optimize for time and space.
Check if the candidate can abstract the infinite array structure into a manageable algorithm using prefix sums.

Common Pitfalls or Variants

Common pitfalls

Failing to account for the infinite nature of the array when calculating prefix sums.
Using brute force methods that do not leverage the repeating pattern of nums.
Not handling edge cases, such as when no subarray sums to the target.

Follow-up variants

Modify the problem to ask for the longest subarray with a sum equal to the target.
Extend the problem to handle negative numbers in nums.
Change the target to a range (e.g., subarray sum between min and max) instead of a fixed value.

FAQ

How do I approach the 'Minimum Size Subarray in Infinite Array' problem?

You can solve it by utilizing a sliding window and hash table to efficiently track prefix sums and check for subarrays matching the target sum.

What is the time complexity of solving this problem?

The time complexity is generally O(n), where n is the number of elements in the nums array, depending on how the sliding window and hash table are implemented.

What common mistakes should I avoid in this problem?

Make sure you correctly handle the infinite nature of the array, avoid brute force solutions, and be careful with edge cases where no subarray sums to the target.

Can the 'Minimum Size Subarray in Infinite Array' problem have multiple solutions?

Yes, but you are only asked to return the shortest subarray. The algorithm must minimize the length of the valid subarray that sums to the target.

How does the infinite nature of the array impact the solution?

The infinite nature of the array can be abstracted by recognizing the repetition of nums, allowing you to solve the problem efficiently without generating an actual infinite array.

terminal

Solution

Solution 1: Prefix Sum + Hash Table

First, we calculate the sum of all elements in the array $nums$, denoted as $s$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def minSizeSubarray(self, nums: List[int], target: int) -> int:
        s = sum(nums)
        n = len(nums)
        a = 0
        if target > s:
            a = n * (target // s)
            target -= target // s * s
        if target == s:
            return n
        pos = {0: -1}
        pre = 0
        b = inf
        for i, x in enumerate(nums):
            pre += x
            if (t := pre - target) in pos:
                b = min(b, i - pos[t])
            if (t := pre - (s - target)) in pos:
                b = min(b, n - (i - pos[t]))
            pos[pre] = i
        return -1 if b == inf else a + b

Continue Practicing

#2848 points that intersect with cars #2902 count of sub multisets with bounded sum #2845 count of interesting subarrays