2875. Minimum Size Subarray in Infinite Array LeetCode Solution
In this guide, you will get 2875. Minimum Size Subarray in Infinite Array LeetCode Solution with the best time and space complexity. The solution to Minimum Size Subarray in Infinite Array problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Size Subarray in Infinite Array
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.
Example 1:
Input: nums = [1,2,3], target = 5
Output: 2
Explanation: 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
Explanation: 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.
Input: nums = [2,4,6,8], target = 3
Output: -1
Explanation: 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.
2875. Minimum Size Subarray in Infinite Array LeetCode Solution in C++
class Solution {
public:
int minSizeSubarray(vector<int>& nums, int target) {
const long sum = accumulate(nums.begin(), nums.end(), 0L);
const int n = nums.size();
const int remainingTarget = target % sum;
const int repeatLength = (target / sum) * n;
if (remainingTarget == 0)
return repeatLength;
int suffixPlusPrefixLength = n;
long prefix = 0;
unordered_map<long, int> prefixToIndex{{0, -1}};
for (int i = 0; i < 2 * n; ++i) {
prefix += nums[i % n];
if (const auto it = prefixToIndex.find(prefix - remainingTarget);
it != prefixToIndex.cend())
suffixPlusPrefixLength = min(suffixPlusPrefixLength, i - it->second);
prefixToIndex[prefix] = i;
}
return suffixPlusPrefixLength == n ? -1
: suffixPlusPrefixLength + repeatLength;
}
}; /* code provided by PROGIEZ */
2875. Minimum Size Subarray in Infinite Array LeetCode Solution in Java
class Solution {
public int minSizeSubarray(int[] nums, int target) {
final long sum = Arrays.stream(nums).asLongStream().sum();
final int n = nums.length;
final int remainingTarget = (int) (target % sum);
final int repeatLength = (int) (target / sum) * n;
if (remainingTarget == 0)
return repeatLength;
int suffixPlusPrefixLength = n;
long prefix = 0;
HashMap<Long, Integer> prefixToIndex = new HashMap<>();
prefixToIndex.put(0L, -1);
for (int i = 0; i < 2 * n; ++i) {
prefix += nums[i % n];
if (prefixToIndex.containsKey(prefix - remainingTarget))
suffixPlusPrefixLength =
Math.min(suffixPlusPrefixLength, i - prefixToIndex.get(prefix - remainingTarget));
prefixToIndex.put(prefix, i);
}
return suffixPlusPrefixLength == n ? -1 : repeatLength + suffixPlusPrefixLength;
}
} // code provided by PROGIEZ
2875. Minimum Size Subarray in Infinite Array LeetCode Solution in Python
class Solution:
def minSizeSubarray(self, nums: list[int], target: int) -> int:
summ = sum(nums)
n = len(nums)
remainingTarget = target % summ
repeatLength = (target // summ) * n
if remainingTarget == 0:
return repeatLength
suffixPlusPrefixLength = n
prefix = 0
prefixToIndex = {0: -1}
for i in range(2 * n):
prefix += nums[i % n]
if prefix - remainingTarget in prefixToIndex:
suffixPlusPrefixLength = min(
suffixPlusPrefixLength,
i - prefixToIndex[prefix - remainingTarget])
prefixToIndex[prefix] = i
return -1 if suffixPlusPrefixLength == n else suffixPlusPrefixLength + repeatLength # code by PROGIEZ
