Ideahive.me

Ideas worth sharing

1477. Find Two Non-overlapping Sub-arrays Each With Target Sum

sudipp

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;
}

7,705 thoughts on “1477. Find Two Non-overlapping Sub-arrays Each With Target Sum”

  154. Pingback: soul – OxTorrent – Ilurium Real Estate

  228. Thanks a lot for sharing this with all people you really realize what you are speaking approximately! Bookmarked. Please also talk over with my website =). We could have a hyperlink trade agreement among us!

    Reply

  334. Hi, Neat post. There’s an issue along with your site in web explorer, could check this… IE nonetheless is the marketplace chief and a big element of people will miss your magnificent writing because of this problem.

    Reply

  341. Fantastic web site. Lots of useful information here. I’m sending it to some buddies ans additionally sharing in delicious. And naturally, thanks to your effort!

    Reply

  396. What i do not realize is actually how you are not actually much more well-liked than you might be now. You are very intelligent. You realize therefore considerably relating to this subject, made me personally consider it from numerous varied angles. Its like men and women aren’t fascinated unless it is one thing to accomplish with Lady gaga! Your own stuffs excellent. Always maintain it up!

    Reply

  397. A very successful work. Congratulations, take care of yourself. https://steroidmagazan.com Geniş kadrosu ile kurulduğu dönemden beri steroid satın al konusunda güvenli bir alışveriş imkânı sunuyor. Hedefimiz, Yurtiçi ve Yurtdışı kaynaklar ile bu sektörde bulunduğumuz liderlik konumumuzu korumak.

    Reply

  448. It is really a great and useful piece of information. I’m glad that you simply shared this useful info with us. Please keep us up to date like this. Thanks for sharing

    Reply

  474. mobil ödeme bozdurma sitesi üzerinden faturalı veya faturasız hattınızı kullanarak kazanç elde etmeniz mümkün. Şöyle ki; bu siteler telefonunuza bir SMS gönderiyor. Gelen SMS’e onay vermeniz hâlinde hattınızdaki TL bakiyesi karşılığı nakit ödeme alıyorsunuz. Yahut, size ödenecek ücret ay sonu faturanıza yansıtılıyor.

    Reply

  476. It is really a great and useful piece of information. I’m glad that you simply shared this useful info with us. Please keep us up to date like this. Thanks for sharing

    Reply

  482. What i do not realize is actually how you are not actually much more well-liked than you might be now. You are very intelligent. You realize therefore considerably relating to this subject, made me personally consider it from numerous varied angles. Its like men and women aren’t fascinated unless it is one thing to accomplish with Lady gaga! Your own stuffs excellent. Always maintain it up!

    Reply

  488. I’ve been exploring for a little for any high quality articles or blog posts on this sort of area . Exploring in Yahoo I at last stumbled upon this web site. Reading this info So i’m happy to convey that I have a very good uncanny feeling I discovered just what I needed. I most certainly will make sure to do not forget this web site and give it a look on a constant basis.

    Reply

  546. Nie musisz wiec wpłacać własnych pieniędzy otrzymasz bonus na poker $50 bez depozytu. Poczuj smak wygranej. Graj na różne stawki, bierz udział w wielkich turniejach. Nie musisz wiec wpłacać własnych pieniędzy otrzymasz bonus na poker $50 bez depozytu. Disclaimer: Pseudonim autora tej strony jest pseudonimem osoby wirtualnej. Jakiekolwiek podobieństwo lub zbieg okoliczności z danymi prawdziwych osób jest jedynie i wyłącznie przypadkowe. Redakcja portalu nie ma na celu naruszać Prywatność realnych osób, ani negatywnie wpływać na honor i godność tych osób. Nie zamierzamy również oszukiwać naszych klientów i nie korzystamy z ich zaufania. Please stand by, while we are checking your browser… Gracze wykonują turę zgodnie z ruchem wskazówek zegara, przy czym każdy gracz stara się albo dopasować poprzedni najwyższy zakład lub pas, przegrać zgromadzoną kwotę zakładu i jakiekolwiek przyszłe zaangażowanie w turnieju. Gracze, którzy pasują do zakładów, mogą również je podbijać. Turniej dobiega końca, gdy wszyscy gracze albo sprawdzą, albo spasują ostatni zakład. Jeśli wszyscy z wyjątkiem jednego gracza pasują podczas rundy, pozostali gracze zbierają pulę bez konieczności ujawniania swojej puli. Gdy dwóch lub więcej graczy pozostanie w turnieju po ostatniej rundzie, następuje zamknięcie, podczas którego każdy gracz ujawnia swoje ręce, a gracz ze zwycięską ręką nosi pulę. https://www.divephotoguide.com/user/h7mmqso484/ Piszę pluginy pod: AMX MOD X oraz SOURCE MOD! Kategoria: Counter-Strike: Global Offensive Lokalizacja: Bydgoszcz Kluczowym aspektem działalności kasyna internetowego jest jego dział z grami losowymi. VulkanBet ma obecnie jedną z największych bibliotek gier wśród polskich kasyn internetowych. Wszystkich gier jest ponad 2000 i liczba ta zmienia się dosłownie z dnia na dzień. Każdy z ponad 20 dostawców gier nieustannie pracuje nad nowymi produkcjami. Najwięksi jak NetEnt, czy Play’n GO potrafią wydawać po kilka gier w miesiącu. Dzięki temu ogólna biblioteka rocznie może powiększyć się nawet o 100 pozycji, czyli gdyby gracz bawił się wyłącznie na premierowych slotach, to prawdopodobnie i tak brakłoby mu czasu, żeby je wszystkie w pełni poznać. Dlaczego CSGOEmpire tak kochany przez graczy CSGO i całą społeczność hazardową? Kilka elementów, które mają znaczenie: niezawodność i uczciwość skórek, etui i gier, prostota, bezpieczeństwo i szybkość zarówno w procesie rejestracji, jak i podczas wpłat i wypłat, kilka wydarzeń i promocji oraz kilka specjalnych funkcji. Szeroka gama akceptowanych metod płatności i świetna obsługa klienta to wisienka na torcie.

    Reply

  573. Sitenizin SEO çalışmaları için özet şeklinde anlattığımız bu başlıkların tamamı ince işçilik ve ayrıntılı bir çalışma sonucunda verimli olacaktır. Bu çalışmaları baştan salma yada özensiz yaparsanız tek kaybedecek olan yine sizler olursunuz. Bu alanda uzmanlardan destek almak ve sitenizin tüm SEO çalışmalarını SEO Uzmanı ile çalışmak sitenizde gerekli olan tüm bu ayarları bir uzmanın ellerine teslim etmek anlamına gelir. Uzmanlar sizin için SEO çalışmalarınızı yapsın sizlerde sitenizdeki trafiğin keyfini çıkarın.

    Reply

  586. If you’ve played Grand Theft Auto online in the past, you’ll know that the accuracy of the reproduction of other players actions often leaves a lot to be desired.

    Reply