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:

  1. Find the shortest subarray that sums up exactly to target.
  2. If it's not possible (because target is now less than s after subtraction), find two subarrays where one is at the start and one is at the end of nums such that their total sum equals s - target. This effectively simulates wrapping around due to the infinite nature of infinite_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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

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:

  1. Compute the sum s of the entire nums array. Then check if target is greater than s. If yes, you can cover a significant portion of the target by using whole arrays of nums. Calculate a = n * (target // s), which denotes the array length contributed by the complete nums blocks. After this, subtract (target // s * s) from target, reducing the problem to finding a shorter subarray that sums up to the new target. If the new target matches s, return n since it is the shortest subarray that can be formed by the whole array.

  2. 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 of nums.

  3. Initialize a variable pre to hold the ongoing prefix sum as we iterate through the array and a variable b as inf (infinity) which will later hold the length of the shortest qualifying subarray found.

  4. Iterate through the nums array, updating the pre (prefix sum) by adding each element x from nums to it.

  5. Two main checks are performed for each iteration:

    • If the difference t = pre - target exists in pos, it means a subarray sums up to target. Update b to be the minimum of its current value or the distance from the current index to the index stored in pos[t].
    • If the difference t = pre - (s - target) exists in pos, it implies that there's a contiguous subarray from the start and end of nums which together add up to target. Again, update b to be the minimum of its current value or n - (i - pos[t]).
  6. After the loop, check if b has changed from inf. If it has, this means a valid subarray was found, and the solution returns a + 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?

Example 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:

  1. First, we compute the sum s of the entire nums array, which in this case is 3 + 1 + 2 = 6. Since target is equal to s, we can directly return the length of nums, which is 3, as the shortest subarray because using the whole nums 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 the target might not exactly match s.

  2. Initialize a hash table pos with -1 as the prefix sum for an empty array, and a variable pre for ongoing prefix sums starting at 0. Also, initialize b as inf which indicates the shortest found subarray (to be minimized).

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

  4. We start iterating nums:

    • At index 0, pre becomes 3. pos does not have pre - target = 3 - 6 = -3, so we continue.
    • At index 1, pre becomes 4. pos does not have pre - target = 4 - 6 = -2, so we continue.
    • At index 2, pre becomes 6. pos does have pre - target = 6 - 6 = 0, which is the prefix sum for an empty array, so we find that subarray [3, 1, 2] sums to target. We update b to current index (2) plus one minus -1 (position of 0 in pos), which equals 3.
  5. After the iteration, b is no longer inf; it's 3. So, we can directly return the length 3, indicating that [3, 1, 2] is the shortest subarray that sums up to the target.

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
Not Sure What to Study? Take the 2-min Quiz:

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫