Welcome to Subscribe On Youtube

1477. Find Two Non-overlapping Sub-arrays Each With Target Sum

Description

You are given an array of integers arr and an integer target.

You have to find two non-overlapping sub-arrays of arr each with a sum equal target. There can be multiple answers so you have to find an answer where the sum of the lengths of the two sub-arrays is minimum.

Return the minimum sum of the lengths of the two required sub-arrays, or return -1 if you cannot find such two sub-arrays.

 

Example 1:

Input: arr = [3,2,2,4,3], target = 3
Output: 2
Explanation: Only two sub-arrays have sum = 3 ([3] and [3]). The sum of their lengths is 2.

Example 2:

Input: arr = [7,3,4,7], target = 7
Output: 2
Explanation: Although we have three non-overlapping sub-arrays of sum = 7 ([7], [3,4] and [7]), but we will choose the first and third sub-arrays as the sum of their lengths is 2.

Example 3:

Input: arr = [4,3,2,6,2,3,4], target = 6
Output: -1
Explanation: We have only one sub-array of sum = 6.

 

Constraints:

  • 1 <= arr.length <= 105
  • 1 <= arr[i] <= 1000
  • 1 <= target <= 108

Solutions

  • class Solution {
        public int minSumOfLengths(int[] arr, int target) {
            Map<Integer, Integer> d = new HashMap<>();
            d.put(0, 0);
            int n = arr.length;
            int[] f = new int[n + 1];
            final int inf = 1 << 30;
            f[0] = inf;
            int s = 0, ans = inf;
            for (int i = 1; i <= n; ++i) {
                int v = arr[i - 1];
                s += v;
                f[i] = f[i - 1];
                if (d.containsKey(s - target)) {
                    int j = d.get(s - target);
                    f[i] = Math.min(f[i], i - j);
                    ans = Math.min(ans, f[j] + i - j);
                }
                d.put(s, i);
            }
            return ans > n ? -1 : ans;
        }
    }
    
  • class Solution {
    public:
        int minSumOfLengths(vector<int>& arr, int target) {
            unordered_map<int, int> d;
            d[0] = 0;
            int s = 0, n = arr.size();
            int f[n + 1];
            const int inf = 1 << 30;
            f[0] = inf;
            int ans = inf;
            for (int i = 1; i <= n; ++i) {
                int v = arr[i - 1];
                s += v;
                f[i] = f[i - 1];
                if (d.count(s - target)) {
                    int j = d[s - target];
                    f[i] = min(f[i], i - j);
                    ans = min(ans, f[j] + i - j);
                }
                d[s] = i;
            }
            return ans > n ? -1 : ans;
        }
    };
    
  • class Solution:
        def minSumOfLengths(self, arr: List[int], target: int) -> int:
            d = {0: 0}
            s, n = 0, len(arr)
            f = [inf] * (n + 1)
            ans = inf
            for i, v in enumerate(arr, 1):
                s += v
                f[i] = f[i - 1]
                if s - target in d:
                    j = d[s - target]
                    f[i] = min(f[i], i - j)
                    ans = min(ans, f[j] + i - j)
                d[s] = i
            return -1 if ans > n else ans
    
    
  • func minSumOfLengths(arr []int, target int) int {
    	d := map[int]int{0: 0}
    	const inf = 1 << 30
    	s, n := 0, len(arr)
    	f := make([]int, n+1)
    	f[0] = inf
    	ans := inf
    	for i, v := range arr {
    		i++
    		f[i] = f[i-1]
    		s += v
    		if j, ok := d[s-target]; ok {
    			f[i] = min(f[i], i-j)
    			ans = min(ans, f[j]+i-j)
    		}
    		d[s] = i
    	}
    	if ans > n {
    		return -1
    	}
    	return ans
    }
    

All Problems

All Solutions