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
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 kint 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 Codeint 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 kimport 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 kdef 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 inputarr = [ 10, 5, 2, 7, 1, 9 ]n = len(arr)k = 15# Function Callprint("Length = " , lenOfLongSubarr(arr, n, k))# This code is contributed by akashish__ |
C#
// C# implementation to find the length// of longest subarray having sum kusing 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 kfunction 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 inputlet arr = [ 10, 5, 2, 7, 1, 9 ];let n = arr.length;let k = 15;// Function Callconsole.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 kint 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 Codeint 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 kimport 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 kdef 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 Codeif __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 kfunction 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 Codevar 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 kint 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 Codeint 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 kimport sysdef 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 Codearr = [ 10, 5, 2, 7, 1, 9 ]n = len(arr)k = 15print("Length = "+ str(lenOfLongSubarr(arr, n, k)))# This code is contributed by shinjanpatra |
C#
// C# code for the above approachusing 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 kfunction 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 Codelet arr = [ 10, 5, 2, 7, 1, 9 ]let n = arr.lengthlet k = 15document.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.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
