2875. Minimum Size Subarray in Infinite Array
Problem Description
You are given an array called nums
, which starts from the index 0
. There is also an integer called target
. There's a hypothetical array called infinite_nums
, which is made by continuously repeating the nums
array infinitely. Your task is to find the shortest contiguous subarray within infinite_nums
that adds up to the target
value. The length of this subarray (the number of elements it includes) is what you need to return. If such a subarray can't be found, you must return -1
.
For example, if nums
is [1,2,3]
and the target
is 5
, you can use the subarray [2,3]
from nums
or [3,1,1]
from infinite_nums
, both sum up to 5
but the shortest length is 2
from the [2,3]
subarray in nums
.
Intuition
The intuition behind the solution is to use mathematical properties and an efficient data structure to avoid direct iteration through the infinite array, which would be impractical.
First, calculate the sum of all elements in nums
, which is referred to as s
. Compare s
with the target
. If the target
is larger than s
, then you can construct part of the required subarray using whole chunks of nums
, each of which contributes s
to the overall sum. This means you can repeatedly subtract s
from target
until target
is less than s
, and count how many times you've done this as part of the subarray length.
Then, the problem is reduced to two cases within the original nums
array:
- Find the shortest subarray that sums up exactly to
target
. - If it's not possible (because
target
is now less thans
after subtraction), find two subarrays where one is at the start and one is at the end ofnums
such that their total sum equalss - target
. This effectively simulates wrapping around due to the infinite nature ofinfinite_nums
.
To achieve this efficiently, we use a prefix sum array and a hash table. The prefix sum array allows us to calculate the sum of any subarray quickly, and the hash table lets us lookup whether a needed sum to reach the target
has been seen before as we iterate through nums
. When we find such sums, we can calculate the length of the subarray that reaches the target
.
With the above strategy, we ensure that we can get our answer without explicitly dealing with the infinite array, all while maintaining good time complexity.
Learn more about Prefix Sum and Sliding Window patterns.
Solution Approach
The given solution approach leverages a combination of prefix sums and hash tables to solve the problem with efficiency.
Here's a step-by-step breakdown of the implementation:
-
Compute the sum
s
of the entirenums
array. Then check iftarget
is greater thans
. If yes, you can cover a significant portion of thetarget
by using whole arrays ofnums
. Calculatea = n * (target // s)
, which denotes the array length contributed by the completenums
blocks. After this, subtract(target // s * s)
fromtarget
, reducing the problem to finding a shorter subarray that sums up to the newtarget
. If the newtarget
matchess
, returnn
since it is the shortest subarray that can be formed by the whole array. -
Initialize a hash table
pos
to keep track of the last position of every prefix sum encountered. Set the prefix sum for an empty array to-1
to handle cases where the subarray starts at the beginning ofnums
. -
Initialize a variable
pre
to hold the ongoing prefix sum as we iterate through the array and a variableb
asinf
(infinity) which will later hold the length of the shortest qualifying subarray found. -
Iterate through the
nums
array, updating thepre
(prefix sum) by adding each elementx
fromnums
to it. -
Two main checks are performed for each iteration:
- If the difference
t = pre - target
exists inpos
, it means a subarray sums up totarget
. Updateb
to be the minimum of its current value or the distance from the current index to the index stored inpos[t]
. - If the difference
t = pre - (s - target)
exists inpos
, it implies that there's a contiguous subarray from the start and end ofnums
which together add up totarget
. Again, updateb
to be the minimum of its current value orn - (i - pos[t])
.
- If the difference
-
After the loop, check if
b
has changed frominf
. If it has, this means a valid subarray was found, and the solution returnsa + b
. Otherwise, return-1
indicating that a subarray satisfying the conditions does not exist.
This approach uses a hash table to store prefix sums and their corresponding last index. This data structure combined with the prefix sum concept allows us to find contiguous subarrays that add up to a target effectively. By doing this in a single pass, the algorithm avoids the need for nested loops, resulting in an efficient solution.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach using a small example. Suppose the given nums
array is [3, 1, 2]
, and the target
is 6
. We want to find the shortest contiguous subarray within infinite_nums
that sums up to 6
.
Following the solution approach:
-
First, we compute the sum
s
of the entirenums
array, which in this case is3 + 1 + 2 = 6
. Sincetarget
is equal tos
, we can directly return the length ofnums
, which is3
, as the shortest subarray because using the wholenums
array once sums to the target. However, for sake of walkthrough, let's proceed as if we were to look for a subarray since often thetarget
might not exactly matchs
. -
Initialize a hash table
pos
with-1
as the prefix sum for an empty array, and a variablepre
for ongoing prefix sums starting at0
. Also, initializeb
asinf
which indicates the shortest found subarray (to be minimized). -
As we iterate, we build our prefix sum array on the fly, and update
pos
with the last position we encountered a specific prefix sum. -
We start iterating
nums
:- At index
0
,pre
becomes3
.pos
does not havepre - target = 3 - 6 = -3
, so we continue. - At index
1
,pre
becomes4
.pos
does not havepre - target = 4 - 6 = -2
, so we continue. - At index
2
,pre
becomes6
.pos
does havepre - target = 6 - 6 = 0
, which is the prefix sum for an empty array, so we find that subarray[3, 1, 2]
sums totarget
. We updateb
to current index (2
) plus one minus-1
(position of 0 inpos
), which equals3
.
- At index
-
After the iteration,
b
is no longerinf
; it's3
. So, we can directly return the length3
, indicating that[3, 1, 2]
is the shortest subarray that sums up to thetarget
.
In this case, iteration reveals that using the entire array nums
itself is the shortest subarray to reach the target
of 6
. In scenarios where target
is not equal to s
, the method would identify the shortest contiguous subarray as per the steps described in the solution approach. If no such subarray exists, -1
would be returned.
Solution Implementation
1from math import inf
2
3class Solution:
4 def minSizeSubarray(self, nums: List[int], target: int) -> int:
5 total_sum = sum(nums) # Calculate the total sum of all numbers in the array
6 num_count = len(nums) # Get the length of the array
7
8 # Initialize an 'a' which is the number of complete array rotations required
9 num_full_rotations = 0
10 if target > total_sum:
11 num_full_rotations = (target // total_sum) * num_count
12 target -= (target // total_sum) * total_sum # Update the target after the full rotations
13
14 # If target equals total_sum, return the array length
15 if target == total_sum:
16 return num_count
17
18 pos = {0: -1} # Create a dictionary to store the prefix sum indices
19 prefix_sum = 0 # Initialize the prefix sum
20 min_length = inf # Set initial min length to infinity
21
22 # Traverse through the array
23 for i, num in enumerate(nums):
24 prefix_sum += num # Update prefix sum
25
26 # Check if there's a subarray that ends at index i with sum equals target
27 if (t := prefix_sum - target) in pos:
28 min_length = min(min_length, i - pos[t])
29
30 # Check if there is a circular subarray that sums to target
31 if (t := prefix_sum - (total_sum - target)) in pos:
32 min_length = min(min_length, num_count - (i - pos[t]))
33
34 # Store the latest index of this prefix sum
35 pos[prefix_sum] = i
36
37 # If min_length is still infinity, no subarray was found. Return -1.
38 # Otherwise, return the answer which includes the rotations 'a' + the found subarray length 'b'
39 return -1 if min_length == inf else num_full_rotations + min_length
40
1import java.util.Arrays;
2import java.util.HashMap;
3import java.util.Map;
4
5class Solution {
6
7 // Function to find the smallest subarray sum greater than or equal to the target
8 public int minSizeSubarray(int[] nums, int target) {
9 // Compute the sum of all elements in the array
10 long totalSum = Arrays.stream(nums).sum();
11 int length = nums.length;
12 int additionalElements = 0;
13
14 // If target is greater than the total sum, scale the number of times the whole array is needed
15 if (target > totalSum) {
16 additionalElements = length * (target / (int) totalSum);
17 target -= target / totalSum * totalSum;
18 }
19
20 // If the target is now equal to the total sum, simply return the length of the array
21 if (target == totalSum) {
22 return length;
23 }
24
25 // Create a map to store the prefix sum and its corresponding index
26 Map<Long, Integer> prefixSumToIndex = new HashMap<>();
27 prefixSumToIndex.put(0L, -1); // Initialize with 0 sum at index -1
28 long currentPrefixSum = 0;
29 int minSize = Integer.MAX_VALUE; // Start with the maximum possible value
30
31 // Iterate through the array to find the minimum size subarray
32 for (int i = 0; i < length; i++) {
33 currentPrefixSum += nums[i];
34
35 // If the prefix sum indicating the end of subarray achieving the target is seen before
36 if (prefixSumToIndex.containsKey(currentPrefixSum - target)) {
37 minSize = Math.min(minSize, i - prefixSumToIndex.get(currentPrefixSum - target));
38 }
39
40 // Check if there's a complement subarray sum that together with the currentPrefixSum gives totalSum
41 if (prefixSumToIndex.containsKey(currentPrefixSum - (totalSum - target))) {
42 minSize = Math.min(minSize, length - (i - prefixSumToIndex.get(currentPrefixSum - (totalSum - target))));
43 }
44
45 // Update the map with the current prefix sum and index
46 prefixSumToIndex.put(currentPrefixSum, i);
47 }
48
49 // If minSize is unchanged, no such subarray exists; return -1.
50 // Otherwise, return the minimum size added by the number of additional elements needed
51 return minSize == Integer.MAX_VALUE ? -1 : additionalElements + minSize;
52 }
53}
54
1#include <vector>
2#include <numeric>
3#include <unordered_map>
4#include <algorithm>
5
6class Solution {
7public:
8 int minSizeSubarray(vector<int>& nums, int target) {
9 // Calculate the total sum of the array
10 long long totalSum = accumulate(nums.begin(), nums.end(), 0LL);
11 int n = nums.size();
12
13 // Calculate how many complete arrays are needed to reach close to the target
14 int completeArraysCount = 0;
15 if (target > totalSum) {
16 completeArraysCount = n * (target / totalSum);
17 target -= (target / totalSum) * totalSum;
18 }
19
20 // If target equals totalSum, a complete array is needed
21 if (target == totalSum) {
22 return n;
23 }
24
25 // Hash map to keep track of the prefix sum and its corresponding index
26 unordered_map<int, int> prefixSumIndex{{0, -1}};
27
28 long long prefixSum = 0; // Initialize prefix sum
29 int minLength = 1 << 30; // Initialize the minimum length to a very large number
30
31 // Iterate over the array to find the minimum subarray
32 for (int i = 0; i < n; ++i) {
33 prefixSum += nums[i]; // Update the prefix sum
34
35 // Check if there is a subarray with sum equal to (prefixSum - target)
36 if (prefixSumIndex.count(prefixSum - target)) {
37 minLength = min(minLength, i - prefixSumIndex[prefixSum - target]);
38 }
39
40 // Check if there is a subarray that, when added to the current subarray, gives the complement to the target
41 if (prefixSumIndex.count(prefixSum - (totalSum - target))) {
42 minLength = min(minLength, n - (i - prefixSumIndex[prefixSum - (totalSum - target)]));
43 }
44
45 // Update the index for the current prefix sum
46 prefixSumIndex[prefixSum] = i;
47 }
48
49 // If minLength has not been updated, return -1, as no valid subarray exists.
50 // Otherwise, return the minimum length found plus the count of complete arrays needed.
51 return minLength == 1 << 30 ? -1 : completeArraysCount + minLength;
52 }
53};
54
1// This function finds the minimal length of a contiguous subarray of which the sum is at least the target value.
2// If there is no such subarray, the function returns -1.
3function minSizeSubarray(nums: number[], target: number): number {
4 // Calculate the sum of the entire array.
5 const totalSum = nums.reduce((acc, num) => acc + num);
6
7 // Initial preparations: calculation of repetitions of the full array sum to reach the target.
8 let repeatedFullArrayCount = 0;
9 if (target > totalSum) {
10 // Calculate how many times we can fit the total sum into the target sum.
11 repeatedFullArrayCount = Math.floor(target / totalSum);
12 // Decrease the target by the amount already covered by the full array repetitions.
13 target -= repeatedFullArrayCount * totalSum;
14 }
15 // If after the subtraction the target equals the total sum, we can return the array length.
16 if (target === totalSum) {
17 return nums.length;
18 }
19
20 // Map to store the prefix sum and its corresponding index.
21 const prefixSums = new Map<number, number>();
22 prefixSums.set(0, -1); // Initialize with prefix sum of 0 and index -1.
23
24 // Variables for running prefix sum and the minimum size of the subarray found.
25 let runningSum = 0;
26 let minSubarraySize = Infinity;
27
28 // Iterate over the array to find the minimum length subarray.
29 for (let i = 0; i < nums.length; ++i) {
30 runningSum += nums[i];
31
32 // Check if the current prefix sum, minus the target, already exists.
33 // If it does, we possibly found a smaller subarray.
34 if (prefixSums.has(runningSum - target)) {
35 const prevIndex = prefixSums.get(runningSum - target)!;
36 minSubarraySize = Math.min(minSubarraySize, i - prevIndex);
37 }
38
39 // Similar check as above, accounting for the case where sum of nums minus target exists as a prefix sum.
40 // This helps in covering scenarios where the sum cycles through the array.
41 if (prefixSums.has(runningSum - (totalSum - target))) {
42 const prevIndex = prefixSums.get(runningSum - (totalSum - target))!;
43 minSubarraySize = Math.min(minSubarraySize, nums.length - (i - prevIndex));
44 }
45
46 // Update the prefix sum map with the current running sum and index.
47 prefixSums.set(runningSum, i);
48 }
49
50 // If no subarray was found that adds up to the target, return -1.
51 // Otherwise, return the count of full array repetitions plus the found subarray size.
52 return minSubarraySize === Infinity ? -1 : repeatedFullArrayCount + minSubarraySize;
53}
54
Time and Space Complexity
Time Complexity
The time complexity of the function is O(n)
where n
is the length of the array nums
. This is because there is a single loop that goes through each element of nums
exactly once. The operations within the loop have constant time complexity, such as the calculation of the running sum (pre
), checking for the existence of a value in the hash table (pos
), and updating the hash table. As a result, these constant-time operations do not change the overall linear time complexity.
Space Complexity
The space complexity of the function is also O(n)
, which comes from the use of a hash table pos
that keeps track of the indices of the prefix sums. In the worst case, if all prefix sums are unique, the hash table will have as many entries as there are elements in nums
. Therefore, the space used by the hash table is directly proportional to the size of the input array, leading to linear space complexity.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of these pictures shows the visit order of a depth-first search?
Recommended Readings
Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By
https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we