Longest sub-array having sum k
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++ 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;
// if maximum possible subarray length from i is equal to maxLength
if( maxlength == N - i )
break;
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 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;
// if maximum possible subarray length from i is equal to maxLength
if( maxlength == N - i )
break;
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 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
# if maximum possible subarray length from i is equal to maxLength
if (maxlength == N - i):
break
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# 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;
// if maximum possible subarray length from i is equal to maxLength
if( maxlength == n- i )
break;
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.
// 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;
// if maximum possible subarray length from i is equal to maxLength
if( maxlength == N - i )
break;
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 prefix_sum = 0 and maxLen = 0.
- Create a hash table having (prefix_sum, index) tuples.
- For i = 0 to n-1, perform the following steps:
- Accumulate arr[i] to prefix_sum.
- If prefix_sum == k, update maxLen = i+1.
- Check whether prefix_sum is present in the hash table or not. If not present, then add it to the hash table as (prefix_sum, i) pair.
- Check if (prefix_sum-k) is present in the hash table or not. If present, then obtain index of (prefix_sum-k) from the hash table as index. Now check if maxLen < (i-index), then update maxLen = (i-index).
- Return maxLen.
Implementation:
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
int lenOfLongSubarr(vector<int>& A, int N, int K)
{
unordered_map<int, int> sum_index_map;
int maxLen = 0;
int prefix_sum = 0;
for (int i = 0; i < N; ++i) {
prefix_sum += A[i];
if (prefix_sum == K) {
maxLen = i + 1;
}
else if (sum_index_map.find(prefix_sum - K) != sum_index_map.end()) {
maxLen = max(maxLen, i - sum_index_map[prefix_sum - K]);
}
if (sum_index_map.find(prefix_sum) == sum_index_map.end()) {
sum_index_map[prefix_sum] = i;
}
}
return maxLen;
}
int main()
{
vector<int> arr = { 10, 5, 2, 7, 1, 9 };
int n = arr.size();
int k = 15;
cout << "Length = " << lenOfLongSubarr(arr, n, k)
<< endl;
return 0;
}
import java.util.HashMap;
public class Main {
public static int lenOfLongSubarr(int[] A, int N, int K)
{
HashMap<Integer, Integer> sum_index_map
= new HashMap<>();
int maxLen = 0;
int prefix_sum = 0;
for (int i = 0; i < N; i++) {
prefix_sum += A[i];
if (prefix_sum == K) {
maxLen = i + 1;
}
else if (sum_index_map.containsKey(prefix_sum - K)) {
maxLen = Math.max(
maxLen,
i - sum_index_map.get(prefix_sum - K));
}
if (!sum_index_map.containsKey(prefix_sum)) {
sum_index_map.put(prefix_sum, i);
}
}
return maxLen;
}
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));
}
}
import sys
def lenOfLongSubarr(A, N, K):
sum_index_map = {0: -1} # Dictionary to store cumulative sum and its index
maxLen = 0
prefix_sum = 0
for i in range(N):
prefix_sum += A[i]
#no need to this case bease we are stroing the sum 0 with index -1 initially
#if prefix_sum==k:
# maxLen=i+1
# If prefix_sum-K is found in the map, update maxLen
if prefix_sum - K in sum_index_map:
length = i - sum_index_map[prefix_sum - K]
maxLen = max(maxLen, length)
# Store the index of the cumulative sum if it's not already in the map
if prefix_sum not in sum_index_map:
sum_index_map[prefix_sum] = i
return maxLen
# Driver Code
arr = [10, 5, 2, 7, 1, 9]
n = len(arr)
k = 15
print("Length = " + str(lenOfLongSubarr(arr, n, k)))
using System;
using System.Collections.Generic;
class MainClass {
public static int LenOfLongSubarr(int[] A, int N, int K)
{
Dictionary<int, int> sum_index_map
= new Dictionary<int, int>();
int maxLen = 0;
int prefix_sum = 0;
for (int i = 0; i < N; i++) {
prefix_sum += A[i];
if (prefix_sum == K) {
maxLen = i + 1;
}
else if (sum_index_map.ContainsKey(prefix_sum - K)) {
maxLen = Math.Max(
maxLen,
i - sum_index_map[prefix_sum - K]);
}
if (!sum_index_map.ContainsKey(prefix_sum)) {
sum_index_map.Add(prefix_sum, i);
}
}
return maxLen;
}
public static void Main(string[] args)
{
int[] arr = { 10, 5, 2, 7, 1, 9 };
int n = arr.Length;
int k = 15;
Console.WriteLine("Length = "
+ LenOfLongSubarr(arr, n, k));
}
}
function lenOfLongSubarr(A, N, K) {
const sum_index_map = {};
let maxLen = 0;
let prefix_sum = 0;
for (let i = 0; i < N; i++) {
prefix_sum += A[i];
if (prefix_sum === K) {
maxLen = i + 1;
}
else if (sum_index_map.hasOwnProperty(prefix_sum - K)) {
maxLen = Math.max(maxLen, i - sum_index_map[prefix_sum - K]);
}
if (!sum_index_map.hasOwnProperty(prefix_sum)) {
sum_index_map[prefix_sum] = i;
}
}
return maxLen;
}
const arr = [10, 5, 2, 7, 1, 9];
const n = arr.length;
const k = 15;
console.log("Length = " + lenOfLongSubarr(arr, n, k));
Output
Length = 4
Time Complexity: O(N), where N is the length of the given array.
Auxiliary Space: O(N) We are using Hash Table for storing prefix sums.