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

Constraints:

  • 1 <= arr.length <= 10^5
  • 1 <= arr[i] <= 1000
  • 1 <= target <= 10^8

Step 1: Here the idea is to use the sliding window, which moves from left to right, and keep track of the maximum sliding window size, whose element sum is = K, If the sum goes beyond K, shrink the window from left. If the Sum is less than k, then we use the previous window size, whose sum was k. At every index, we will store the maximum window size, whose element sum = k, into a prefix[] array

Step 2: We run another sliding window from right to left direction, keeping track of maximum sliding window size, whose elements sum is k. If the sum goes beyond K, shrink the window from the right. At every index, we will store the maximum window size, whose element sum = k, into a suffix[] array

Step 3: We traverse both prefix and suffix arrays together to find the maximum sum of elements in 2 arrays.

Runtime : O(N), Space O(N)

public int MinSumOfLengths(int[] arr, int target) {
	//O(N), Space O(N)

	int[] prefix = new int[arr.Length + 1]; //prefix[i] is the minimum length of sub-array ends before i and has sum = k,
	int[] suffix = new int[arr.Length + 1]; //suffix[i] is the minimum length of sub-array starting at or after i and has sum = k.

	//Base case - 
	prefix[0] = 0;
	suffix[suffix.Length - 1] = 0;

	int start = 1;
	int currSum = 0;
	for (int i = start; i < arr.Length; i++)
	{
		currSum += arr[i - 1];

		//sliding widnow - shrinks from left side, if currSum > target
		while (currSum > target)
		{
			currSum -= arr[start - 1];
			start += 1;
		}

		if (currSum == target)
		{
			//i - start + 1 --> this is the range that makes sum = target
			prefix[i] = (prefix[i - 1] > 0) ? Math.Min(i - start + 1, prefix[i - 1]) : i - start + 1;
		}
		else
		{
			//Pick the previous Min value
			prefix[i] = prefix[i - 1];
		}
	}

	//sliding widnow - shrinks from right side, if currSum > target
	currSum = 0;
	start = suffix.Length - 2;
	for (int i = start; i >= 0 ; i--)
	{   
		while (currSum > target)
		{
			currSum -= arr[start];
			start -= 1;
		}

		if (currSum == target)
		{
			//start - i --> this is the range that makes sum = target
			suffix[i] = (suffix[i + 1] > 0) ? Math.Min(start - i, suffix[i + 1]) : start - i;
		}
		else
		{
			//Pick the previous Min value, But as we are sliding width from right to left... our previous value exist on right side
			suffix[i] = suffix[i + 1]; 
		}

		//This is the suffix sum... So We are not including the current element first... 
		currSum += arr[i];
	}

	//Working with the idea that a non overlapping subarray lies to right and left of an index, 
	//so we select minimum subarray from the two halves of the array.  
	int minComb = int.MaxValue;
	for (int i = 1; i < suffix.Length; i++)
	{
		if (prefix[i] == 0 || suffix[i - 1] == 0)
			continue;

		minComb = Math.Min(minComb, prefix[i] + suffix[i - 1]);
	}
	return (minComb == int.MaxValue) ? -1 : minComb;
}

Leave a Reply

Your email address will not be published. Required fields are marked *