> For the complete documentation index, see [llms.txt](https://soumyajit4419.gitbook.io/ds-algo/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://soumyajit4419.gitbook.io/ds-algo/sub-array-problems/15.-find-two-non-overlapping-sub-arrays-each-with-target-sum.md).

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

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.
```

**Example 4:**

```
Input: arr = [5,5,4,4,5], target = 3
Output: -1
Explanation: We cannot find a sub-array of sum = 3.
```

**Example 5:**

```
Input: arr = [3,1,1,1,5,1,2,1], target = 3
Output: 3
Explanation: Note that sub-arrays [1,2] and [2,1] cannot be an answer because they overlap.
```

## Solution: (Prefix and Suffix sum)

**Approach:**\
**Finding Prefix sum and getting min length of all possible subarrays at every index**\
**Finding Suffix sum and getting min length of all possible subarrays at every index**\
**Finding min length of two subarray** \
     **at index  :**\
        **len = ps\[0 - i-1] + ss\[i - n]** 

```cpp
class Solution
{
public:
    int minSumOfLengths(vector<int> &arr, int target)
    {

        int n = arr.size();

        vector<int> ps(n);
        unordered_map<int, int> pidx;
        pidx[0] = -1;
        int s = 0;
        int minArr = INT_MAX;

        for (int i = 0; i < arr.size(); i++)
        {
            s += arr[i];

            if (pidx.find(s - target) != pidx.end())
            {
                int dist = i - pidx[s - target];
                minArr = min(minArr, dist);
            }

            ps[i] = minArr;
            pidx[s] = i;
        }

        vector<int> ss(n);
        unordered_map<int, int> sidx;
        minArr = INT_MAX;
        s = 0;
        sidx[0] = arr.size();

        for (int i = arr.size() - 1; i >= 0; i--)
        {
            s += arr[i];

            if (sidx.find(s - target) != sidx.end())
            {
                int dist = sidx[s - target] - i;
                minArr = min(minArr, dist);
            }

            ss[i] = minArr;
            sidx[s] = i;
        }

        int res = INT_MAX;

        for (int i = 1; i < n; i++)
        {

            if (ps[i - 1] != INT_MAX && ss[i] != INT_MAX)
            {
                res = min(res, ps[i - 1] + ss[i]);
            }
        }

        if (res == INT_MAX)
        {
            return -1;
        }

        return res;
    }
};
```

**Time Complexity: O(n)**