Welcome to Subscribe On Youtube

2875. Minimum Size Subarray in Infinite Array

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

First, we calculate the sum of all elements in the array $nums$, denoted as $s$.

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

Next, we need to find the shortest subarray in $nums$ whose sum equals $target$, or the shortest subarray whose prefix sum plus suffix sum equals $s - 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 $nums$.

  • class Solution {
        public int minSizeSubarray(int[] nums, int target) {
            long s = Arrays.stream(nums).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;
        }
    }
    
  • 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<int, 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;
        }
    };
    
  • 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
    
    
  • 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
    }
    
    func min(a, b int) int {
    	if a < b {
    		return a
    	}
    	return b
    }
    
  • 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;
    }
    
    

All Problems

All Solutions