SSWEETS - Editorial

editorial
,
1

PROBLEM LINK:

Contest

Author: Rahul Sharma

Tester: Sumukh Bhardwaj

Editorialist: Rahul Sharma

DIFFICULTY:

Easy

PREREQUISITES:

Two pointers, loops

PROBLEM:

Given an array of size N and an integer K. Find the start and end of maximum size subarray such that sum of subarray is atmost K. If there are multiple subarray print the first one. If no such subrray exist print -1.

QUICK EXPLANATION:

Make use of two pointer approach to find start and end of subarray.

EXPLANATION:

Subtask #1:
Check all the possible values of start and end using nested loops and store the result with maximum size and within the sum limit of K. This approach will have time complexity of O(N^2) and will only pass this subtask

Subtask #2:
Efficient way to solve this problem is make use of two pointer approach. We maintain a currSum sum between the start and end as follows:

if(currSum <= K )
    currSum+= arr[end]
    end+=1
else
    if((end-start) > max_len_so_far)
            left = start;
			right = end-1;
			max_len_so_far = end-start;
    currSum-= arr[start]
    start+=1

If currSum < K then we can continue increasing end. Else if it becomes greater that means we cannot add any more element beyond the current end we need to delete from start and increment it till currSum again become less than K. And fill currSum is valid we update the variables left and right that marks the maximum sub array we found so far that satisfies the condition.
We continue till end reaches N. After which left and right will have the answer.

COMPLEXITIES:

Time Complexity: O(N) for each test case
Space Complexity: O(1) for each test case

SOLUTIONS:

Setter's Solution 
#include<bits/stdc++.h>
using namespace std;

long long int arr[1000006];
int main()
{
	long long int n,k;
	cin >> n >> k;

	for (int i = 0; i < n; i++)
		cin >> arr[i];

	long long int i = 0, j = 0;
	long long int left = -1, right = -1, sum = 0,  maxLen = 0;

	while(1)
	{
		// cout << i << ' ' << j;
		if (sum > k)
		{
			sum = sum - arr[i];
			i++;

			if (sum <= k && i < j && j - i > maxLen)
			{
				left = i + 1;
				right = j;
				maxLen = j - i;
			}
		}

		if (sum <= k && j < n)
		{
			sum = sum + arr[j];
			j++;

			if (sum <= k && j - i > maxLen)
			{
				left = i + 1;
				right = j;
				maxLen = j - i;
			}
		}

		else if (j >= n)
			break; 
	}

	if (left == -1 && right == -1)
		cout << -1;
	else
		cout << left << ' ' << right;
}
1 Like