<p>You are given an array of integers <code>arr</code> and an integer <code>target</code>.</p>

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

<p>Return <em>the minimum sum of the lengths</em> of the two required sub-arrays, or return <code>-1</code> if you cannot find such two sub-arrays.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

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

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> arr = [7,3,4,7], target = 7
<strong>Output:</strong> 2
<strong>Explanation:</strong> 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.
</pre>

<p><strong class="example">Example 3:</strong></p>

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

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= arr.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= arr[i] &lt;= 1000</code></li>
	<li><code>1 &lt;= target &lt;= 10<sup>8</sup></code></li>
</ul>

from typing import List


class Solution:
    def minSumOfLengths(self, arr: List[int], target: int) -> int:
        if arr is None or len(arr) == 0:
            return -1

        n = len(arr)

        sums = [0] * n
        sums[0] = arr[0]

        for i in range(1, n):
            sums[i] = sums[i - 1] + arr[i]

        start = 0
        end = 0

        sub_arrs = []

        while start < n and end < n:
            sum = sums[end] if start == 0 else sums[end] - sums[start - 1]

            if sum == target:
                sub_arrs.append((start, end))
                start += 1
                end += 1
            elif sum < target:
                end += 1
            else:
                start += 1

        # print(sub_arrs)

        if len(sub_arrs) < 2:
            return -1

        m = len(sub_arrs)

        min_lens = [-1] * n

        min_lens[sub_arrs[m - 1][0]] = sub_arrs[m - 1][1] - sub_arrs[m - 1][0] + 1
        min_len = min_lens[sub_arrs[m - 1][0]]
        current = sub_arrs[m - 1][0]

        for (s, e) in reversed(sub_arrs):
            for i in range(s + 1, current):
                min_lens[i] = min_len

            min_len = min(min_len, e - s + 1)
            min_lens[s] = min_len
            current = s

        min_two_lens = -1

        # print(min_lens)

        for (s, e) in sub_arrs:
            if e < n - 1 and min_lens[e + 1] != -1:
                two_lens = e - s + 1 + min_lens[e + 1]

                min_two_lens = min(min_two_lens, two_lens) if min_two_lens != -1 else two_lens

        return min_two_lens

40300