Longest Subarray With Sum K

Easy
0/40
Average time to solve is 20m
profile
Contributed by
1043 upvotes
Asked in company
IDEMIA

Problem statement

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'.


Example : 
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.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
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’.


Output format : 
Print the length of the longest subarray whose sum is equal to ‘k’.


Note : 
You do not need to print anything; it has already been taken care of. Just implement the given function.
Sample Input 1 :
7 3
1 2 3 1 1 1 1


Sample Output 1 :
3


Explanation Of Sample Input 1 :
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.


Sample Input 2 :
4 2
1 2 1 3


Sample Output 2 :
1


Sample Input 3 :
5 2
2 2 4 1 2


Sample Output 3 :
1


Expected time complexity :
The expected time complexity is O(n).


Constraints :
1 <= 'n' <= 5 * 10 ^ 6
1 <= 'k' <= 10^18
0 <= 'a[i]' <= 10 ^ 9

Time Limit: 1-second
Hint

Generate all subarrays and check their sum.

Approaches (2)
Brute Force

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):

 

  1. Int ‘n’ be the size of array ‘a’ and ‘k’ be the required sum.
  2. Initialize a variable ‘maxLength’ to ‘0’, storing the maximum length of the subarray whose sum = ‘k’.
  3. Iterate over array ‘a’ and at each iteration:
    • Initialize a variable ‘currentSum’ to ‘0’, storing the sum of the current subarray.
    • Iterate over array ‘a’ from the current index to the end of the array:
      • Add the value of array ‘a’ at the index at which we are currently present.
      • If currentSum == ‘k’
        • maxLength = max(‘maxLength’, ‘length of current subarray’)
  4. Return maxLength
Time Complexity

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).

Space Complexity

O(1).
 

Since we are only using variables to store maximum and currentMaximum,

 

Hence the space complexity is O(1).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Longest Subarray With Sum K
Full screen
Console