You are given an array 'a' of size 'n' and an integer 'k'.
Find the length of the longest subarray of 'a' whose sum is equal to 'k'.
Input: ‘n’ = 7 ‘k’ = 3
‘a’ = [1, 2, 3, 1, 1, 1, 1]
Output: 3
Explanation: Subarrays whose sum = ‘3’ are:
[1, 2], [3], [1, 1, 1] and [1, 1, 1]
Here, the length of the longest subarray is 3, which is our final answer.
The first line contains two integers, ‘n’ and ‘k’, denoting the size of array ‘a’ and the integer ‘k’.
The following line contains ‘n’ integers, denoting the array ‘a’.
Print the length of the longest subarray whose sum is equal to ‘k’.
You do not need to print anything; it has already been taken care of. Just implement the given function.
7 3
1 2 3 1 1 1 1
3
Subarrays whose sum = ‘3’ are:
[1, 2], [3], [1, 1, 1] and [1, 1, 1]
Here, the length of the longest subarray is 3, which is our final answer.
4 2
1 2 1 3
1
5 2
2 2 4 1 2
1
The expected time complexity is O(n).
1 <= 'n' <= 5 * 10 ^ 6
1 <= 'k' <= 10^18
0 <= 'a[i]' <= 10 ^ 9
Time Limit: 1-second
Generate all subarrays and check their sum.
Use two nested loops to generate all subarrays. The first loop will decide the starting index of the subarray. The second loop will start from the starting index and generate all possible subarrays from the ‘starting index’.
At each point, check whether the sum of the current subarray is equal to the required sum.
If the current sum = ‘k’, check whether the length of the current subarray is greater than the maximum value we have found. If this is true, the length of the current subarray is now the maximum length (we have found so far). Else, we continue.
The steps are as follows:-
// Function to find the longest subarray with sum ‘k’
function longestSubarrayWithSumK(int[] a, int n, int k):
O(n ^ 2), where 'n' is the size of array ‘a’.
Since we are using two nested loops here,
Hence the time complexity is O(n ^ 2).
O(1).
Since we are only using variables to store maximum and currentMaximum,
Hence the space complexity is O(1).
All tags
Sort by
Interview problems
c++ solution
int longestSubarrayWithSumK(vector<int> a, long long k) {
int maxlen = 0 ;
long long sum = 0 ;
int j = 0;
for (int i = 0; i < a.size();) {
if (sum <= k) {
sum = sum + a[i];
}
if (sum > k) {
sum = sum - a[j];
j++;
}
if (sum == k && i < a.size()) {
maxlen = max(maxlen , i - j + 1);
i++;
}
if (sum < k && i < a.size() ) {
i++;
}
}
return maxlen ;
}
Interview problems
LONGEST Subarray with Sum K (java Optimal sollution)
public class Solution {
public static int longestSubarrayWithSumK(int []a, long k) {
// Write your code here
int n = a.length;
int left = 0 , right = 0;
long sum = a[0];
int maxlen = 0;
while(right < n){
while(left <= right && sum > k ){
sum -= a[left];
left++;
}
if(sum == k){
maxlen = Math.max(maxlen, right-left+1);
}
right++;
if(right < n){
sum += a[right];
}
}
return maxlen;
}
}
Interview problems
easy code
#include<bits/stdc++.h>
int longestSubarrayWithSumK(vector<int> a, long long k) {
// Write your code here
int right=0,left=0;
long long sum=a[0];
int maxlen=0;
int n=a.size();
while(right<n)
{
while(left<=right && sum>k)
{
sum-=a[left];
left++;
}
if(sum==k)
{
maxlen=max(maxlen,right-left+1);
}
right++;
if(right<n)
{
sum+=a[right];
}
}
return maxlen;
}
Interview problems
what is output of this code
n=5 k=17
Longest Subarray With Sum K
8 15 17 0 11
Interview problems
Sliding Window Solution, beats 100%
int longestSubarrayWithSumK(vector<int> a, long long k) {
// Write your code here
int length=0;
int answer=0;
long long curr=0;
int left=0;
int right=0;
int n= a.size();
for(right=0; right<n; right++){
curr+= a[right];
while(curr>k && left <= right){
curr -= a[left];
left++;
}
if(curr == k){
answer= max(answer,right-left+1);
}
}
return answer;
}
Interview problems
2 pointer, optimal with different types of representations.
public class Solution {
public static int longestSubarrayWithSumK(int []a, long k) {
// Write your code here
// 1. og
int size = 0;
int i=0;
int j=0;
int count=0;
while(j<a.length) {
count = a[j] + count;
if (k-count > 0) {
j++;
}else if (k-count == 0) {
if (j<a.length-1 && a[j+1] == 0) {
j++;
}else {
size = Math.max(j-i+1, size);
count = 0;
i++;
j = i;
}
}else {
count = 0;
i++;
j = i;
}
}
return size;
// 2. modified
int size = 0;
int i=0;
int j=-1;
int count=0;
while(j<a.length) {
if (k-count > 0) {
j++;
if (j>=a.length) break;
count = a[j] + count;
}else if (k-count == 0) {
if (j<a.length-1 && a[j+1] == 0) {
j++;
if (j>=a.length) break;
count = a[j] + count;
}else {
size = Math.max(j-i+1, size);
count = count - a[i];
i++;
}
}else {
count = count - a[i];
i++;
}
}
return size;
// 3. better in iterration and writing(copied).
int i=0;
int j=0;
int count=a[0];
int size=0;
while(j<a.length) {
while (i<=j && k-count < 0) {
count = count - a[i];
i++;
}
if (k-count == 0) {
size = Math.max(j-i+1, size);
}
j++;
if (j<a.length) {
count = count + a[j];
}
}
return size;
}
}
Interview problems
Optimal Solution in Java
import java.util.HashMap;
public class Solution {
public static int longestSubarrayWithSumK(int []arr, long k) {
int left=0,right=0,maxLength=0;
long sum=arr[0];
int n=arr.length;
while(right<n){
while(left<=right && sum>k){
sum=sum-arr[left];
left++;
}
if(sum==k){
maxLength=Math.max(maxLength, right-left+1);
}
right++;
if(right<n){
sum=sum+arr[right];
}
}
return maxLength;
}
}
Interview problems
simple C++ solution with end cases of Zero's
int longestSubarrayWithSumK(vector<int> a, long long k) {
// Write your code here
int s=0,e=0;
long long sum=a[s];
int count,maxcount=0;
while(s<a.size() && e<a.size())
{
count=0;
if(sum<k)
{
e++;
sum+=a[e];
}
else if(sum>k)
{
sum-=a[s];
s++;
}
else{
for(int i=s;i<=e;i++)
{
count++;
}
while(e+1<a.size() && a[e + 1] == 0 )
{
count+=1;
e++;
}
e++;
sum=sum+a[e]-a[s];
s++;
}
maxcount=max(count,maxcount);
}
return maxcount;
}
Interview problems
Very Easy Solution | 2 Approaches-> Two Pointers & Hashmap| C++
int usingTwoPointersApproach(vector<int> &a, long long k)
{
int i = 0, j = 0;
long long int maxLength = 0, sum = 0;
while(j < a.size())
{
sum += a[j];
while(sum > k)
{
sum -= a[i];
i++;
}
if(sum == k)
{
if(maxLength < j-i+1)
maxLength = j-i+1;
}
j++;
}
return maxLength;
}
int usingHashMap(vector<int> &a, long long k)
{
unordered_map<int, int> mp;
int i = 0, size = a.size();
long long int prefixSum = 0, maxLength = 0;
while(i < size)
{
prefixSum += a[i];
if(mp.find(prefixSum-k) != mp.end())
{
int length = i-mp[prefixSum-k];
if(maxLength < i-mp[prefixSum-k])
maxLength = i-mp[prefixSum-k];
}
// TO handle zeroes, we insert that condition.
if(mp.find(prefixSum) == mp.end())
mp[prefixSum] = i;
i++;
}
return maxLength;
}
int longestSubarrayWithSumK(vector<int> a, long long k) {
return usingTwoPointersApproach(a, k);
// return usingHashMap(a, k);
}
Interview problems
Check out this
public class Solution {
public static int longestSubarrayWithSumK(int []arr, long k) {
// Write your code here
int n=arr.length;
int sum=0;
int right=0;
int left=0;
int maxlength=0;
while(right < n){
sum += arr[right];
while( left <= right && sum > k){
sum -= arr[left];
left++;
}
if( sum == k){
maxlength = Math.max(maxlength, right - left+1);
}
right ++;
}
return maxlength;
}
}
