MediumNo. 2875
Minimum Size Subarray in Infinite Array — LeetCode 2875 Python Solution
- Pattern
- Sliding Window
- Topics
- Array, Hash Table, Prefix Sum, 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
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 + bComplexity
- Time
- O(n)
- Space · auxiliary
- O(n)where n is the length of the array nums
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.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0930 | Binary Subarrays With Sum | Medium |
| 1248 | Count Number of Nice Subarrays | Medium |
| 1658 | Minimum Operations to Reduce X to Zero | Medium |
| 0219 | Contains Duplicate II | Easy |
| 0480 | Sliding Window Median | Hard |
| 0523 | Continuous Subarray Sum | Medium |
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.