C++: Optimized DP & Binary Search for Minimum Sum of Two Non-Overlapping Subarrays
IntuitionMy first thought was to find all subarrays whose sum equals the target and then determine the two non-overlapping subarrays with the minimum combined l
# Intuition
My first thought was to find all subarrays whose sum equals the target and then determine the two non-overlapping subarrays with the minimum combined length. Since all numbers in the array are positive, prefix sums can be used to quickly compute subarray sums.

# Approach
Finding Subarrays with a Given Sum:
Since all numbers in the array are positive, we can use a prefix sum (a running total of the numbers). This makes it easy to quickly check the sum of any subarray. For each starting position, we use binary search to find where the subarray should end so that the sum matches the target. This helps us efficiently find all valid subarrays.

Choosing Two Non-Overlapping Subarrays with the Smallest Total Length:
Once we have all the valid subarrays (each represented by a start and end index), we sort them by their end index. Then, we use a DP (Dynamic Programming) array to track the smallest subarray length up to each index.

Pairing Non-Overlapping Subarrays:
As we go through the sorted subarrays, we look for a previous subarray that ends before the current one starts. If we find one, we check if combining the two gives a smaller total length than what we’ve seen before. This way, we efficiently find the best two non-overlapping subarrays with the smallest combined length.

This method ensures we solve the problem optimally and efficiently! 🚀

# Complexity
- Time complexity:
O(nlogn)

- Space complexity:
O(n)

# Code
```cpp []
class Solution {
public:
    int minSumOfLengths(vector<int>& arr, int k) {
        //part1
        //precompute
        int n = arr.size();
        vector<int> preSum(n,0);
        preSum[0] = arr[0];
        for(int i=1; i<n; i++) preSum[i] = preSum[i-1] + arr[i];
        //algorithm
        vector<pair<int,int>> nums;
        for(int i=0; i<n; i++){
            if(arr[i] == k){
                nums.push_back({i,i});
                continue;
            }
            if(arr[i] > k) continue;
            //algo for storing intervals
            int lf = i+1, rt = n-1;
            while(lf <= rt){
                int mid = lf + (rt - lf)/2;
                int sum = preSum[mid];
                if(i > 0) sum -= preSum[i-1];
                if(sum == k){
                    nums.push_back({i, mid});
                    break;
                }
                else if(sum > k) rt = mid - 1;
                else lf = mid + 1;
            }
        }

        //algorithm
        int minLen = 1e9, sz = nums.size(), bestTill = 1e9, j = 0;
        sort(nums.begin(), nums.end(), [](auto &a, auto &b){
            return a.second < b.second;
        });
        vector<int> dp(n, 1e9);
        for(int i=0; i<n; i++){
            while(j < sz && nums[j].second == i){
                int lf = nums[j].first, rt = nums[j].second;
                int len = rt - lf + 1;
                if(lf > 0 && dp[lf-1] != 1e9){
                    minLen = min(minLen, len + dp[lf-1]);
                }
                bestTill = min(bestTill, len);
                j++;
            }
            dp[i] = bestTill;
        }

        if(minLen == 1e9) return -1;
        else return minLen;
    }
};
```
['Binary Search', 'Dynamic Programming', 'Greedy', 'Sorting', 'C++']