Skip to content

2875. Minimum Size Subarray in Infinite Array

SourceWeekly Contest 365 Q3DifficultyMediumRating1913

Description

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.

Example 3:

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.

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105
  • 1 <= target <= 109

Solutions

Solution 1: Prefix Sum + Hash Table

Thinking

The array repeats forever, so \(\textit{target}\) is some number of full cycles plus a shortest leftover (or a shortest wrap that complements a cycle). Strip as many full sums as possible, then on one prefix-sum pass a hash map finds the shortest segment equal to the remainder or to \(s\) minus the remainder. A prefix of values up to \(10^5\) can exceed \(2^{31}-1\), so the map key is a 64-bit integer. A 32-bit key matches sums \(2^{32}\) apart and reports a subarray that is not there.

First, we calculate the sum of all elements in the array \(\textit{nums}\), denoted as \(s\).

If \(\textit{target} \gt s\), we can reduce \(\textit{target}\) to the range \([0, s)\) by subtracting \(\lfloor \frac{\textit{target}}{s} \rfloor \times s\) from it. Then, the length of the subarray is \(a = \lfloor \frac{\textit{target}}{s} \rfloor \times n\), where \(n\) is the length of the array \(\textit{nums}\).

Next, we need to find the shortest subarray in \(\textit{nums}\) whose sum equals \(\textit{target}\), or the shortest subarray whose prefix sum plus suffix sum equals \(s - \textit{target}\). We can use prefix sum and a hash table to find such subarrays.

If we find such a subarray, the final answer is \(a + b\). Otherwise, the answer is \(-1\).

The time complexity is \(O(n)\), and the space complexity is \(O(n)\), where n is the length of the array \(\textit{nums}\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int minSizeSubarray(int[] nums, int target) {
        long s = Arrays.stream(nums).asLongStream().sum();
        int n = nums.length;
        int a = 0;
        if (target > s) {
            a = n * (target / (int) s);
            target -= target / s * s;
        }
        if (target == s) {
            return n;
        }
        Map<Long, Integer> pos = new HashMap<>();
        pos.put(0L, -1);
        long pre = 0;
        int b = 1 << 30;
        for (int i = 0; i < n; ++i) {
            pre += nums[i];
            if (pos.containsKey(pre - target)) {
                b = Math.min(b, i - pos.get(pre - target));
            }
            if (pos.containsKey(pre - (s - target))) {
                b = Math.min(b, n - (i - pos.get(pre - (s - target))));
            }
            pos.put(pre, i);
        }
        return b == 1 << 30 ? -1 : a + b;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int minSizeSubarray(vector<int>& nums, int target) {
        long long s = accumulate(nums.begin(), nums.end(), 0LL);
        int n = nums.size();
        int a = 0;
        if (target > s) {
            a = n * (target / s);
            target -= target / s * s;
        }
        if (target == s) {
            return n;
        }
        unordered_map<long long, int> pos{{0, -1}};
        long long pre = 0;
        int b = 1 << 30;
        for (int i = 0; i < n; ++i) {
            pre += nums[i];
            if (pos.count(pre - target)) {
                b = min(b, i - pos[pre - target]);
            }
            if (pos.count(pre - (s - target))) {
                b = min(b, n - (i - pos[pre - (s - target)]));
            }
            pos[pre] = i;
        }
        return b == 1 << 30 ? -1 : a + b;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
func minSizeSubarray(nums []int, target int) int {
    s := 0
    for _, x := range nums {
        s += x
    }
    n := len(nums)
    a := 0
    if target > s {
        a = n * (target / s)
        target -= target / s * s
    }
    if target == s {
        return n
    }
    pos := map[int]int{0: -1}
    pre := 0
    b := 1 << 30
    for i, x := range nums {
        pre += x
        if j, ok := pos[pre-target]; ok {
            b = min(b, i-j)
        }
        if j, ok := pos[pre-(s-target)]; ok {
            b = min(b, n-(i-j))
        }
        pos[pre] = i
    }
    if b == 1<<30 {
        return -1
    }
    return a + b
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function minSizeSubarray(nums: number[], target: number): number {
    const s = nums.reduce((a, b) => a + b);
    const n = nums.length;
    let a = 0;
    if (target > s) {
        a = n * ((target / s) | 0);
        target -= ((target / s) | 0) * s;
    }
    if (target === s) {
        return n;
    }
    const pos: Map<number, number> = new Map();
    let pre = 0;
    pos.set(0, -1);
    let b = Infinity;
    for (let i = 0; i < n; ++i) {
        pre += nums[i];
        if (pos.has(pre - target)) {
            b = Math.min(b, i - pos.get(pre - target)!);
        }
        if (pos.has(pre - (s - target))) {
            b = Math.min(b, n - (i - pos.get(pre - (s - target))!));
        }
        pos.set(pre, i);
    }
    return b === Infinity ? -1 : a + b;
}

Comments