Longest Subarray with Sum K problem GFG
Given an array arr[] containing integers and an integer k, your task is to find the length of the longest subarray where the sum of its elements is equal to the given value k. If there is no subarray with sum equal to k, return 0.
Examples:
Input: arr[] = [10, 5, 2, 7, 1, -10], k = 15
Output: 6
Explanation: Subarrays with sum = 15 are [5, 2, 7, 1], [10, 5] and [10, 5, 2, 7, 1, -10]. The length of the longest subarray with a sum of 15 is 6.
Input: arr[] = [-5, 8, -14, 2, 4, 12], k = -5
Output: 5
Explanation: Only subarray with sum = 15 is [-5, 8, -14, 2, 4] of length 5.
Input: arr[] = [10, -10, 20, 30], k = 5
Output: 0
Explanation: No subarray with sum = 5 is present in arr[].
Brute Force:- Problem in Brute Force - TLE problem because complexity is n^3.
//{ Driver Code Starts
import java.io.*;
import java.util.*;
class Main {
public static void main(String args[]) throws IOException {
BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(read.readLine().trim()); // Read number of test cases
while (t-- > 0) {
String line = read.readLine().trim(); // Read the array input
String[] numsStr = line.split(" "); // Split the input string by spaces
int[] nums =
new int[numsStr.length]; // Convert string array to integer array
for (int i = 0; i < numsStr.length; i++) {
nums[i] = Integer.parseInt(numsStr[i]);
}
int k = Integer.parseInt(read.readLine().trim()); // Read target sum
Solution ob = new Solution();
int ans = ob.longestSubarray(nums, k); // Call the function and store result
System.out.println(ans);
System.out.println("~");
}
}
}
// } Driver Code Ends
// User function Template for Java
class Solution {
public int longestSubarray(int[] arr, int k) {
// code here
int len = 0;
int n=arr.length;
for(int i=0;i<n;i++)
{
for(int j=i;j<n;j++)
{
int currentsum = 0; // Move sum initialization outside the inner loop
for(int l=i;l<=j;l++)
{
currentsum=currentsum+arr[l];
}
if (currentsum == k)
{
len = Math.max(len, j - i + 1);
}
}
}
return len;
}
}
Optimised Solution :-
//{ Driver Code Starts
import java.io.*;
import java.util.*;
class Main {
public static void main(String args[]) throws IOException {
BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(read.readLine().trim()); // Read number of test cases
while (t-- > 0) {
String line = read.readLine().trim(); // Read the array input
String[] numsStr = line.split(" "); // Split the input string by spaces
int[] nums =
new int[numsStr.length]; // Convert string array to integer array
for (int i = 0; i < numsStr.length; i++) {
nums[i] = Integer.parseInt(numsStr[i]);
}
int k = Integer.parseInt(read.readLine().trim()); // Read target sum
Solution ob = new Solution();
int ans = ob.longestSubarray(nums, k); // Call the function and store result
System.out.println(ans);
System.out.println("~");
}
}
}
// } Driver Code Ends
// User function Template for Java
class Solution {
public int longestSubarray(int[] arr, int k) {
// code here
Map<Integer, Integer> mp = new HashMap<>();
int res = 0;
int prefSum = 0;
for (int i = 0; i < arr.length; ++i) {
prefSum += arr[i];
// Check if the entire prefix sums to k
if (prefSum == k)
res = i + 1;
// If prefixSum - k exists in the map then there exist such
// subarray from (index of previous prefix + 1) to i.
else if (mp.containsKey(prefSum - k))
res = Math.max(res, i - mp.get(prefSum - k));
// Store only first occurrence index of prefSum
if (!mp.containsKey(prefSum))
mp.put(prefSum, i);
}
return res;
}
}
Comments
Post a Comment