Given an array of integers arr and an integer target, you are asked to find two non-overlapping sub-arrays of arr such that the sum of elements in each sub-array is exactly target. The two sub-arrays must not share any elements (they cannot overlap or touch). Your task is to return the minimum possible sum of the lengths of these two sub-arrays. If no such pair of sub-arrays exists, return -1.
target.-1.
At first glance, it seems natural to try every possible pair of sub-arrays and check if both sum to target and do not overlap. However, this brute-force approach would require checking all possible sub-arrays, leading to a very inefficient solution.
To optimize, we can focus on efficiently finding sub-arrays that sum to target and then, for each such sub-array, look for another non-overlapping sub-array. We need a way to quickly look up the shortest sub-array ending before or starting after a given index. This hints at using prefix sums and dynamic programming to store the shortest sub-array up to each point.
By maintaining information about the shortest valid sub-arrays as we scan the array, we can efficiently pair non-overlapping candidates and keep track of the minimal total length.
Here is a step-by-step breakdown of the optimized algorithm:
target in O(1) time per index.best_left where best_left[i] is the length of the shortest sub-array ending at or before i with sum target.best_right from the right side.-1.By precomputing shortest sub-array lengths for each possible endpoint, we ensure that each combination is checked only once, leading to an efficient solution.
Let's consider arr = [3,2,2,4,3] and target = 3.
[3] at index 0 (length 1)[2,1] doesn't exist; next, [2,2,4] is too big[3] at index 4 (length 1)best_left:
best_right similarly from the right.
Brute-force:
best_left and best_right arrays.The optimization comes from avoiding redundant checks and using efficient data structures for quick lookups.
This problem demonstrates how prefix sums and dynamic programming can be combined to efficiently solve a two-sub-array sum problem. By precomputing the shortest sub-array lengths for each endpoint and leveraging hash maps for O(1) sub-array sum lookups, we reduce the solution from cubic to linear time. The key insight is to decompose the problem into manageable parts and use auxiliary arrays to quickly pair non-overlapping sub-arrays, resulting in a clean and efficient solution.
class Solution:
def minSumOfLengths(self, arr, target):
n = len(arr)
best_left = [float('inf')] * n
prefix_sum = {0: -1}
curr_sum = 0
min_len = float('inf')
# Left to right: shortest subarray ending at or before i
for i in range(n):
curr_sum += arr[i]
if (curr_sum - target) in prefix_sum:
length = i - prefix_sum[curr_sum - target]
min_len = min(min_len, length)
best_left[i] = min_len
else:
best_left[i] = min_len
prefix_sum[curr_sum] = i
# Right to left: shortest subarray starting at or after i
best_right = [float('inf')] * n
prefix_sum = {0: n}
curr_sum = 0
min_len = float('inf')
for i in range(n - 1, -1, -1):
curr_sum += arr[i]
if (curr_sum - target) in prefix_sum:
length = prefix_sum[curr_sum - target] - i
min_len = min(min_len, length)
best_right[i] = min_len
else:
best_right[i] = min_len
prefix_sum[curr_sum] = i
# Combine
result = float('inf')
for i in range(n - 1):
if best_left[i] != float('inf') and best_right[i + 1] != float('inf'):
result = min(result, best_left[i] + best_right[i + 1])
return result if result != float('inf') else -1
class Solution {
public:
int minSumOfLengths(vector<int>& arr, int target) {
int n = arr.size();
vector<int> best_left(n, INT_MAX);
unordered_map<int, int> prefix_sum;
prefix_sum[0] = -1;
int curr_sum = 0, min_len = INT_MAX;
for (int i = 0; i < n; ++i) {
curr_sum += arr[i];
if (prefix_sum.count(curr_sum - target)) {
int length = i - prefix_sum[curr_sum - target];
min_len = min(min_len, length);
best_left[i] = min_len;
} else {
best_left[i] = min_len;
}
prefix_sum[curr_sum] = i;
}
vector<int> best_right(n, INT_MAX);
prefix_sum.clear();
prefix_sum[0] = n;
curr_sum = 0;
min_len = INT_MAX;
for (int i = n - 1; i >= 0; --i) {
curr_sum += arr[i];
if (prefix_sum.count(curr_sum - target)) {
int length = prefix_sum[curr_sum - target] - i;
min_len = min(min_len, length);
best_right[i] = min_len;
} else {
best_right[i] = min_len;
}
prefix_sum[curr_sum] = i;
}
int result = INT_MAX;
for (int i = 0; i < n - 1; ++i) {
if (best_left[i] != INT_MAX && best_right[i + 1] != INT_MAX) {
result = min(result, best_left[i] + best_right[i + 1]);
}
}
return result == INT_MAX ? -1 : result;
}
};
class Solution {
public int minSumOfLengths(int[] arr, int target) {
int n = arr.length;
int[] bestLeft = new int[n];
Arrays.fill(bestLeft, Integer.MAX_VALUE);
Map<Integer, Integer> prefixSum = new HashMap<>();
prefixSum.put(0, -1);
int currSum = 0, minLen = Integer.MAX_VALUE;
for (int i = 0; i < n; ++i) {
currSum += arr[i];
if (prefixSum.containsKey(currSum - target)) {
int length = i - prefixSum.get(currSum - target);
minLen = Math.min(minLen, length);
bestLeft[i] = minLen;
} else {
bestLeft[i] = minLen;
}
prefixSum.put(currSum, i);
}
int[] bestRight = new int[n];
Arrays.fill(bestRight, Integer.MAX_VALUE);
prefixSum.clear();
prefixSum.put(0, n);
currSum = 0;
minLen = Integer.MAX_VALUE;
for (int i = n - 1; i >= 0; --i) {
currSum += arr[i];
if (prefixSum.containsKey(currSum - target)) {
int length = prefixSum.get(currSum - target) - i;
minLen = Math.min(minLen, length);
bestRight[i] = minLen;
} else {
bestRight[i] = minLen;
}
prefixSum.put(currSum, i);
}
int result = Integer.MAX_VALUE;
for (int i = 0; i < n - 1; ++i) {
if (bestLeft[i] != Integer.MAX_VALUE && bestRight[i + 1] != Integer.MAX_VALUE) {
result = Math.min(result, bestLeft[i] + bestRight[i + 1]);
}
}
return result == Integer.MAX_VALUE ? -1 : result;
}
}
var minSumOfLengths = function(arr, target) {
const n = arr.length;
const bestLeft = new Array(n).fill(Infinity);
let prefixSum = new Map();
prefixSum.set(0, -1);
let currSum = 0, minLen = Infinity;
for (let i = 0; i < n; ++i) {
currSum += arr[i];
if (prefixSum.has(currSum - target)) {
const length = i - prefixSum.get(currSum - target);
minLen = Math.min(minLen, length);
bestLeft[i] = minLen;
} else {
bestLeft[i] = minLen;
}
prefixSum.set(currSum, i);
}
const bestRight = new Array(n).fill(Infinity);
prefixSum = new Map();
prefixSum.set(0, n);
currSum = 0;
minLen = Infinity;
for (let i = n - 1; i >= 0; --i) {
currSum += arr[i];
if (prefixSum.has(currSum - target)) {
const length = prefixSum.get(currSum - target) - i;
minLen = Math.min(minLen, length);
bestRight[i] = minLen;
} else {
bestRight[i] = minLen;
}
prefixSum.set(currSum, i);
}
let result = Infinity;
for (let i = 0; i < n - 1; ++i) {
if (bestLeft[i] !== Infinity && bestRight[i + 1] !== Infinity) {
result = Math.min(result, bestLeft[i] + bestRight[i + 1]);
}
}
return result === Infinity ? -1 : result;
};