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^5
1 <= arr[i] <= 1000
1 <= target <= 10^8

Solution

Method 1 – Sliding Window + Prefix Min Array

Intuition

We want to find two non-overlapping subarrays each summing to target, with the minimum total length. We can use a sliding window to find all subarrays with sum = target, and for each ending index, keep track of the shortest subarray found so far. Then, for each subarray found, check if there is a non-overlapping subarray before it.

Approach

Use a sliding window to find all subarrays with sum = target.
For each subarray ending at index i, keep track of the minimum length of a subarray ending at or before i.
For each subarray found, if there is a non-overlapping subarray before it, update the answer with the sum of their lengths.
Return the minimum sum found, or -1 if not possible.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int minSumOfLengths(vector<int>& arr, int target) {\n        int n = arr.size(), ans = INT_MAX;\n        vector<int> minLen(n, INT_MAX);\n        int l = 0, sum = 0, best = INT_MAX;\n        for (int r = 0; r < n; ++r) {\n            sum += arr[r];\n            while (sum > target) sum -= arr[l++];\n            if (sum == target) {\n                int currLen = r - l + 1;\n                if (l > 0 && minLen[l-1] != INT_MAX)\n                    ans = min(ans, currLen + minLen[l-1]);\n                best = min(best, currLen);\n            }\n            minLen[r] = best;\n        }\n        return ans == INT_MAX ? -1 : ans;\n    }\n};","lang":"cpp"},{"language":"Go","code":"func minSumOfLengths(arr []int, target int) int {\n    n := len(arr)\n    minLen := make([]int, n)\n    for i := range minLen {\n        minLen[i] = 1 << 30\n    }\n    l, sum, best, ans := 0, 0, 1<<30, 1<<30\n    for r := 0; r < n; r++ {\n        sum += arr[r]\n        for sum > target {\n            sum -= arr[l]\n            l++\n        }\n        if sum == target {\n            currLen := r - l + 1\n            if l > 0 && minLen[l-1] < 1<<30 {\n                if ans > currLen+minLen[l-1] {\n                    ans = currLen + minLen[l-1]\n                }\n            }\n            if best > currLen {\n                best = currLen\n            }\n        }\n        minLen[r] = best\n    }\n    if ans == 1<<30 {\n        return -1\n    }\n    return ans\n}","lang":"go"},{"language":"Java","code":"class Solution {\n    public int minSumOfLengths(int[] arr, int target) {\n        int n = arr.length, ans = Integer.MAX_VALUE;\n        int[] minLen = new int[n];\n        Arrays.fill(minLen, Integer.MAX_VALUE);\n        int l = 0, sum = 0, best = Integer.MAX_VALUE;\n        for (int r = 0; r < n; r++) {\n            sum += arr[r];\n            while (sum > target) sum -= arr[l++];\n            if (sum == target) {\n                int currLen = r - l + 1;\n                if (l > 0 && minLen[l-1] != Integer.MAX_VALUE)\n                    ans = Math.min(ans, currLen + minLen[l-1]);\n                best = Math.min(best, currLen);\n            }\n            minLen[r] = best;\n        }\n        return ans == Integer.MAX_VALUE ? -1 : ans;\n    }\n}","lang":"java"},{"language":"Kotlin","code":"class Solution {\n    fun minSumOfLengths(arr: IntArray, target: Int): Int {\n        val n = arr.size\n        val minLen = IntArray(n) { Int.MAX_VALUE }\n        var l = 0\n        var sum = 0\n        var best = Int.MAX_VALUE\n        var ans = Int.MAX_VALUE\n        for (r in 0 until n) {\n            sum += arr[r]\n            while (sum > targe

Related Tags