Improve Article
Improve
Save Article
Save
Like Article
Like
Given an array arr[] of size n containing integers. The problem is to find the length of the longest sub-array having sum equal to the given value k.
Examples:
Input: arr[] = { 10, 5, 2, 7, 1, 9 }, k = 15
Output: 4
Explanation: The sub-array is {5, 2, 7, 1}.Input: arr[] = {-5, 8, -14, 2, 4, 12}, k = -5
Output: 5
Recommended Practice
Longest Sub-Array with Sum K
Try It!
Naive Approach: Consider the sum of all the sub-arrays and return the length of the longest sub-array having the sum ‘k’. Time Complexity is of O(n^2).
Implementation:
C++
// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
// function to find the length of longest
// subarray having sum k
int lenOfLongSubarr(int arr[], int N, int K)
{
// Variable to store the answer
int maxlength = 0;
for (int i = 0; i < N; i++) {
// Variable to store sum of subarrays
int Sum = 0;
for (int j = i; j < N; j++) {
// Storing sum of subarrays
Sum += arr[j];
// if Sum equals K
if (Sum == K) {
// Update maxLength
maxlength = max(maxlength, j - i + 1);
}
}
}
// Return the maximum length
return maxlength;
}
// Driver Code
int main()
{
// Given input
int arr[] = { 10, 5, 2, 7, 1, 9 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 15;
// Function Call
cout << "Length = " << lenOfLongSubarr(arr, n, k);
return 0;
}
// This code is contributed by Arpit Jain
Java
// Java implementation to find the length
// of longest subarray having sum k
import java.io.*;
import java.util.*;
class GFG {
// function to find the length of longest
// subarray having sum k
static int lenOfLongSubarr(int[] arr, int n, int k)
{
int maxlength = 0;
for (int i = 0; i < n; i++) {
// Variable to store sum of subarrays
int Sum = 0;
for (int j = i; j < n; j++) {
// Storing sum of subarrays
Sum += arr[j];
// if Sum equals K
if (Sum == k) {
// Update maxLength
maxlength = Math.max(maxlength, j - i + 1);
}
}
}
// Return the maximum length
return maxlength;
}
// Driver code
public static void main(String args[])
{
int[] arr = {10, 5, 2, 7, 1, 9};
int n = arr.length;
int k = 15;
System.out.println("Length = " +
lenOfLongSubarr(arr, n, k));
}
}
// This code is contributed by saurabhdalal0001.
Python3
# Python3 code for the above approach
# function to find the length of longest
# subarray having sum k
def lenOfLongSubarr(arr, N, K):
# Variable to store the answer
maxlength = 0
for i in range(0,N):
# Variable to store sum of subarrays
Sum = 0
for j in range(i,N):
# Storing sum of subarrays
Sum += arr[j]
# if Sum equals K
if (Sum == K):
# Update maxLength
maxlength = max(maxlength, j - i + 1)
# Return the maximum length
return maxlength
# Driver Code
# Given input
arr = [ 10, 5, 2, 7, 1, 9 ]
n = len(arr)
k = 15
# Function Call
print("Length = " , lenOfLongSubarr(arr, n, k))
# This code is contributed by akashish__
C#
// C# implementation to find the length
// of longest subarray having sum k
using System;
public class GFG {
// function to find the length of longest
// subarray having sum k
static int lenOfLongSubarr(int[] arr, int n, int k)
{
int maxlength = 0;
for (int i = 0; i < n; i++) {
// Variable to store sum of subarrays
int Sum = 0;
for (int j = i; j < n; j++) {
// Storing sum of subarrays
Sum += arr[j];
// if Sum equals K
if (Sum == k) {
// Update maxLength
maxlength
= Math.Max(maxlength, j - i + 1);
}
}
}
// Return the maximum length
return maxlength;
}
static public void Main()
{
// Code
int[] arr = { 10, 5, 2, 7, 1, 9 };
int n = arr.Length;
int k = 15;
Console.WriteLine("Length = "
+ lenOfLongSubarr(arr, n, k));
}
}
// This code is contributed by lokeshmvs21.
Javascript
// JS code for the above approach
// function to find the length of longest
// subarray having sum k
function lenOfLongSubarr(arr, N, K)
{
// Variable to store the answer
let maxlength = 0;
for (let i = 0; i < N; i++) {
// Variable to store sum of subarrays
let Sum = 0;
for (let j = i; j < N; j++) {
// Storing sum of subarrays
Sum += arr[j];
// if Sum equals K
if (Sum == K) {
// Update maxLength
maxlength = Math.max(maxlength, j - i + 1);
}
}
}
// Return the maximum length
return maxlength;
}
// Driver Code
// Given input
let arr = [ 10, 5, 2, 7, 1, 9 ];
let n = arr.length;
let k = 15;
// Function Call
console.log( "Length = " , lenOfLongSubarr(arr, n, k));
// This code is contributed by akashish__
Output
Length = 4
Time Complexity: O(N2), for calculating the sum of all subarrays.
Auxiliary Space: O(1), as constant extra space is required.
Efficient Approach:
Following the below steps to solve the problem:
- Initialize sum = 0 and maxLen = 0.
- Create a hash table having (sum, index) tuples.
- For i = 0 to n-1, perform the following steps:
- Accumulate arr[i] to sum.
- If sum == k, update maxLen = i+1.
- Check whether sum is present in the hash table or not. If not present, then add it to the hash table as (sum, i) pair.
- Check if (sum-k) is present in the hash table or not. If present, then obtain index of (sum-k) from the hash table as index. Now check if maxLen < (i-index), then update maxLen = (i-index).
- Return maxLen.
Implementation:
C++
// C++ implementation to find the length
// of longest subarray having sum k
#include <bits/stdc++.h>
using namespace std;
// function to find the length of longest
// subarray having sum k
int lenOfLongSubarr(int arr[],
int n,
int k)
{
// unordered_map 'um' implemented
// as hash table
unordered_map<int, int> um;
int sum = 0, maxLen = 0;
// traverse the given array
for (int i = 0; i < n; i++) {
// accumulate sum
sum += arr[i];
// when subarray starts from index '0'
if (sum == k)
maxLen = i + 1;
// make an entry for 'sum' if it is
// not present in 'um'
if (um.find(sum) == um.end())
um[sum] = i;
// check if 'sum-k' is present in 'um'
// or not
if (um.find(sum - k) != um.end()) {
// update maxLength
if (maxLen < (i - um[sum - k]))
maxLen = i - um[sum - k];
}
}
// required maximum length
return maxLen;
}
// Driver Code
int main()
{
int arr[] = {10, 5, 2, 7, 1, 9};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 15;
cout << "Length = "
<< lenOfLongSubarr(arr, n, k);
return 0;
}
Java
// Java implementation to find the length
// of longest subarray having sum k
import java.io.*;
import java.util.*;
class GFG {
// function to find the length of longest
// subarray having sum k
static int lenOfLongSubarr(int[] arr, int n, int k)
{
// HashMap to store (sum, index) tuples
HashMap<Integer, Integer> map = new HashMap<>();
int sum = 0, maxLen = 0;
// traverse the given array
for (int i = 0; i < n; i++) {
// accumulate sum
sum += arr[i];
// when subarray starts from index '0'
if (sum == k)
maxLen = i + 1;
// make an entry for 'sum' if it is
// not present in 'map'
if (!map.containsKey(sum)) {
map.put(sum, i);
}
// check if 'sum-k' is present in 'map'
// or not
if (map.containsKey(sum - k)) {
// update maxLength
if (maxLen < (i - map.get(sum - k)))
maxLen = i - map.get(sum - k);
}
}
return maxLen;
}
// Driver code
public static void main(String args[])
{
int[] arr = {10, 5, 2, 7, 1, 9};
int n = arr.length;
int k = 15;
System.out.println("Length = " +
lenOfLongSubarr(arr, n, k));
}
}
// This code is contributed by rachana soma
Python3
# Python3 implementation to find the length
# of longest subArray having sum k
# function to find the longest
# subarray having sum k
def lenOfLongSubarr(arr, n, k):
# dictionary mydict implemented
# as hash map
mydict = dict()
# Initialize sum and maxLen with 0
sum = 0
maxLen = 0
# traverse the given array
for i in range(n):
# accumulate the sum
sum += arr[i]
# when subArray starts from index '0'
if (sum == k):
maxLen = i + 1
# check if 'sum-k' is present in
# mydict or not
elif (sum - k) in mydict:
maxLen = max(maxLen, i - mydict[sum - k])
# if sum is not present in dictionary
# push it in the dictionary with its index
if sum not in mydict:
mydict[sum] = i
return maxLen
# Driver Code
if __name__ == '__main__':
arr = [10, 5, 2, 7, 1, 9]
n = len(arr)
k = 15
print("Length =", lenOfLongSubarr(arr, n, k))
# This code is contributed by
# chaudhary_19 (Mayank Chaudhary)
C#
// C# implementation to find the length
// of longest subarray having sum k
using System;
using System.Collections.Generic;
class GFG
{
// function to find the length of longest
// subarray having sum k
static int lenOfLongSubarr(int[] arr,
int n, int k)
{
// HashMap to store (sum, index) tuples
Dictionary<int,
int> map = new Dictionary<int,
int>();
int sum = 0, maxLen = 0;
// traverse the given array
for (int i = 0; i < n; i++)
{
// accumulate sum
sum += arr[i];
// when subarray starts from index '0'
if (sum == k)
maxLen = i + 1;
// make an entry for 'sum' if it is
// not present in 'map'
if (!map.ContainsKey(sum))
{
map.Add(sum, i);
}
// check if 'sum-k' is present in 'map'
// or not
if (map.ContainsKey(sum - k))
{
// update maxLength
if (maxLen < (i - map[sum - k]))
maxLen = i - map[sum - k];
}
}
return maxLen;
}
// Driver code
public static void Main()
{
int[] arr = {10, 5, 2, 7, 1, 9};
int n = arr.Length;
int k = 15;
Console.WriteLine("Length = " +
lenOfLongSubarr(arr, n, k));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript implementation to find the length
// of longest subarray having sum k
// function to find the length of longest
// subarray having sum k
function lenOfLongSubarr(arr, n, k)
{
// unordered_map 'um' implemented
// as hash table
var um = new Map();
var sum = 0, maxLen = 0;
// traverse the given array
for (var i = 0; i < n; i++) {
// accumulate sum
sum += arr[i];
// when subarray starts from index '0'
if (sum == k)
maxLen = i + 1;
// make an entry for 'sum' if it is
// not present in 'um'
if (!um.has(sum))
um.set(sum, i);
// check if 'sum-k' is present in 'um'
// or not
if (um.has(sum - k)) {
// update maxLength
if (maxLen < (i - um.get(sum - k)))
maxLen = i - um.get(sum - k);
}
}
// required maximum length
return maxLen;
}
// Driver Code
var arr = [10, 5, 2, 7, 1, 9];
var n = arr.length;
var k = 15;
document.write( "Length = "
+ lenOfLongSubarr(arr, n, k));
</script>
Output
Length = 4
Time Complexity: O(N), where N is the length of the given array.
Auxiliary Space: O(N), for storing the maxLength in the HashMap.
Another Approach
This approach won’t work for negative numbers
In the variable-size sliding window, we do three things.
1. calculation, in this case doing the sum.
2. drawing results out of calculations. in this case, extracting the size of the window if the sum reaches K (target).
3. adjusting the window. in this case, increasing the size of the window if the sum is less than K(target) or decreasing the size if the sum is greater than K(target).
The approach is to use the concept of the variable-size sliding window using 2 pointers
Initialize i, j, and sum = 0. If the sum is less than k just increment j, if the sum is equal to k compute the max and if the sum is greater than k subtract the ith element while the sum is greater than k.
Implementation:
C++
// C++ implementation to find the length
// of longest subarray having sum k
#include <bits/stdc++.h>
using namespace std;
// function to find the length of longest
// subarray having sum k
int lenOfLongSubarr(int A[], int N, int K)
{
int i = 0, j = 0, sum = 0;
int maxLen = INT_MIN;
while (j < N) {
sum += A[j]; //calculation
if (sum == K) {
maxLen = max(maxLen, j-i+1); //taking results
j++;
}
else if (sum < K) { //adjusting window
j++;
}
else if (sum > K) { //adjusting window
while (sum > K) {
sum -= A[i];
i++;
}
if(sum == K){
maxLen = max(maxLen, j-i+1);
}
j++;
}
}
return maxLen;
}
// Driver Code
int main()
{
int arr[] = { 10, 5, 2, 7, 1, 9 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 15;
cout << "Length = " << lenOfLongSubarr(arr, n, k);
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
class GFG {
// Java implementation to find the length
// of longest subarray having sum k
// function to find the length of longest
// subarray having sum k
static int lenOfLongSubarr(int A[], int N, int K)
{
int i = 0, j = 0, sum = 0;
int maxLen = Integer.MIN_VALUE;
while (j < N) {
sum += A[j];
if (sum < K) {
j++;
}
else if (sum == K) {
maxLen = Math.max(maxLen, j-i+1);
j++;
}
else if (sum > K) {
while (sum > K) {
sum -= A[i];
i++;
}
if(sum == K){
maxLen = Math.max(maxLen, j-i+1);
}
j++;
}
}
return maxLen;
}
// Driver code
public static void main(String args[])
{
int arr[] = { 10, 5, 2, 7, 1, 9 };
int n = arr.length;
int k = 15;
System.out.printf("Length = %d",lenOfLongSubarr(arr, n, k));
}
}
// This code is contributed by shinjanpatra.
Python3
# Python implementation to find the length
# of longest subarray having sum k
# function to find the length of longest
# subarray having sum k
import sys
def lenOfLongSubarr(A, N, K):
i, j, sum = 0, 0, 0
maxLen = -sys.maxsize -1
while (j < N):
sum += A[j]
if (sum < K):
j += 1
elif (sum == K):
maxLen = max(maxLen, j - i + 1)
j += 1
elif (sum > K):
while (sum > K):
sum -= A[i]
i += 1
if (sum == K):
maxLen = max(maxLen, j - i + 1)
j += 1
return maxLen
# Driver Code
arr = [ 10, 5, 2, 7, 1, 9 ]
n = len(arr)
k = 15
print("Length = "+ str(lenOfLongSubarr(arr, n, k)))
# This code is contributed by shinjanpatra
C#
// C# code for the above approach
using System;
public class GFG {
// function to find the length of longest subarray
// having sum k
static int lenOfLongSubarr(int[] A, int N, int K)
{
int i = 0, j = 0, sum = 0;
int maxLen = Int32.MinValue;
while (j < N) {
sum += A[j];
if (sum < K) {
j++;
}
else if (sum == K) {
maxLen = Math.Max(maxLen, j - i + 1);
j++;
}
else if (sum > K) {
while (sum > K) {
sum -= A[i];
i++;
}
if (sum == K) {
maxLen = Math.Max(maxLen, j - i + 1);
}
j++;
}
}
return maxLen;
}
static public void Main()
{
// Code
int[] arr = { 10, 5, 2, 7, 1, 9 };
int n = arr.Length;
int k = 15;
Console.Write("Length = "
+ lenOfLongSubarr(arr, n, k));
}
}
// This code is contributed by lokesh (lokeshmvs21).
Javascript
<script>
// JavaScript implementation to find the length
// of longest subarray having sum k
// function to find the length of longest
// subarray having sum k
function lenOfLongSubarr(A, N, K)
{
let i = 0, j = 0, sum = 0;
let maxLen = Number.MIN_VALUE;
while (j < N) {
sum += A[j];
if (sum < K) {
j++;
}
else if (sum == K) {
maxLen = Math.max(maxLen, j-i+1);
j++;
}
else if (sum > K) {
while (sum > K) {
sum -= A[i];
i++;
}
if(sum == K){
maxLen = Math.max(maxLen, j-i+1);
}
j++;
}
}
return maxLen;
}
// Driver Code
let arr = [ 10, 5, 2, 7, 1, 9 ]
let n = arr.length
let k = 15
document.write("Length = ",lenOfLongSubarr(arr, n, k))
// This code is contributed by shinjanpatra
</script>
Output
Length = 4
Time Complexity: O(N), where N is the length of the given array.
Auxiliary Space: O(1), as constant extra space is required.
Last Updated :02 Jan, 2023
Like Article
Save Article