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

Solution 1: Hash Table + Prefix Sum + Dynamic Programming

We can use a hash table \(d\) to record the most recent position where each prefix sum appears, with the initial value \(d[0]=0\).

Define \(f[i]\) as the minimum length of a subarray with sum equal to \(target\) among the first \(i\) elements. Initially, \(f[0]=\infty\).

Iterate through the array \(\textit{arr}\). For the current position \(i\), calculate the prefix sum \(s\). If \(s - \textit{target}\) exists in the hash table, let \(j = d[s - \textit{target}]\), then \(f[i] = \min(f[i], i - j)\), and the answer is \(ans = \min(ans, f[j] + i - j)\). Continue to the next position.

Finally, if the answer is greater than the array length, return \(-1\); otherwise, return the answer.

The complexity is \(O(n)\), and the space complexity is \(O(n)\), where \(n\) is the length of the array.

Python3JavaC++GoTypeScript

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

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;
    }
};

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
}

function minSumOfLengths(arr: number[], target: number): number {
    const d = new Map<number, number>();
    d.set(0, 0);
    let s = 0;
    const n = arr.length;
    const f: number[] = Array(n + 1);
    const inf = 1 << 30;
    f[0] = inf;
    let ans = inf;
    for (let i = 1; i <= n; ++i) {
        const v = arr[i - 1];
        s += v;
        f[i] = f[i - 1];
        if (d.has(s - target)) {
            const j = d.get(s - target)!;
            f[i] = Math.min(f[i], i - j);
            ans = Math.min(ans, f[j] + i - j);
        }
        d.set(s, i);
    }
    return ans > n ? -1 : ans;
}

Comments