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

SourceBiweekly Contest 28 Q3DifficultyMediumRating1850

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 <= 10⁵
1 <= arr[i] <= 1000
1 <= target <= 10⁸

Solutions

Solution 1: Hash Table + Prefix Sum + Dynamic Programming

Thinking

The straightforward approach is to enumerate every subarray that sums to \(target\) and pair them while checking overlap. With \(n \le 10^5\), the number of subarrays is quadratic, so this does not fit.

Once the right segment is fixed, the left one must lie entirely in the prefix before it, and only the shortest valid subarray in that prefix matters. We therefore need a running answer to "the shortest valid segment in the prefix so far".

All values are positive, so prefix sums are strictly increasing and unique. A hash map from prefix sum to index then finds, in constant time, the unique segment \([j+1,i]\) that ends at the current position and sums to \(target\).

We scan left to right while maintaining \(f[i]\), the shortest such subarray among the first \(i\) elements. When \([j+1,i]\) appears, add \(f[j]\) to the current length to update the answer, then set \(f[i]=\min(f[i-1], i-j)\). The left piece always comes from before the current segment, so the two never overlap.

We use a hash table \(d\) to record the index of each prefix sum, initially \(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\) and \(ans=\infty\). Indices are \(1\)-based.

Iterate through \(\textit{arr}\). For the current position \(i\), first set \(f[i]=f[i-1]\) and accumulate the prefix sum \(s\). If \(s-\textit{target}\) exists in the hash table, let \(j=d[s-\textit{target}]\). Then the interval \([j+1,i]\) sums to \(target\) and has length \(i-j\). Update \(f[i]=\min(f[i], i-j)\), and update the answer with the best length on the left: \(ans=\min(ans, f[j]+i-j)\). Then store \(d[s]=i\).

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

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

Python3JavaC++GoTypeScriptRust

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

use std::collections::HashMap;

impl Solution {
    pub fn min_sum_of_lengths(arr: Vec<i32>, target: i32) -> i32 {
        let mut d = HashMap::new();
        d.insert(0, 0);
        let n = arr.len();
        let inf = 1 << 30;
        let mut f = vec![0; n + 1];
        f[0] = inf;
        let mut s = 0;
        let mut ans = inf;
        for i in 1..=n {
            s += arr[i - 1];
            f[i] = f[i - 1];
            if let Some(&j) = d.get(&(s - target)) {
                f[i] = f[i].min((i - j) as i32);
                ans = ans.min(f[j] + (i - j) as i32);
            }
            d.insert(s, i);
        }
        if ans > n as i32 {
            -1
        } else {
            ans
        }
    }
}

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

Description

Solutions

Solution 1: Hash Table + Prefix Sum + Dynamic Programming

Comments