How hard is LeetCode 2875. Minimum Size Subarray in Infinite Array?

LeetCode 2875. Minimum Size Subarray in Infinite Array is rated Medium on LeetCode.

What is the time complexity of LeetCode 2875. Minimum Size Subarray in Infinite Array?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 2875. Minimum Size Subarray in Infinite Array?

The Python solution on this page uses O(n), where n is the length of the array nums auxiliary space.

Minimum Size Subarray in Infinite Array — LeetCode 2875 Python Solution

MediumArrayHash TablePrefix SumSliding Window

Problem: #2875
Pattern: Sliding Window
Reading time: 4 min
Source: leetcode.com

The 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.

Example

Input: nums = [1,2,3], target = 5
Output: 2
Explanation: In this example infinite_nums = [1,2,3,1,2,3,1,2,...].

Python solution

Python

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

Complexity

Measure	Complexity
Time	O(n)
Space	O(n), where n is the length of the array nums auxiliary

Pattern: Sliding Window

Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 2875. Minimum Size Subarray in Infinite Array is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.

The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2875. Minimum Size Subarray in Infinite Array?: LeetCode 2875. Minimum Size Subarray in Infinite Array is rated Medium on LeetCode.
What is the time complexity of LeetCode 2875. Minimum Size Subarray in Infinite Array?: The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 2875. Minimum Size Subarray in Infinite Array?: The Python solution on this page uses O(n), where n is the length of the array nums auxiliary space.
What topics does LeetCode 2875. Minimum Size Subarray in Infinite Array cover?: LeetCode 2875. Minimum Size Subarray in Infinite Array is tagged Array, Hash Table, Prefix Sum and Sliding Window on LeetCode.