Length of longest subarray having sum in given range [L, R]
Given an array arr[] of N integers, find the length of the longest subarray having sum in the range [L, R].
Examples:
Input: arr[] = {1, 4, 6}, L = 3, R = 8
Output: 2
Explanation: The valid subarrays with there sum in range [3, 8] are {1, 4}, {4}, {6}. Longest subarray among them is {1, 4} having its length as 2.Input: arr[] = {15, 2, 4, 8, 9, 5, 10, 23}, L = 10, R = 23
Output: 4
Approach: The given problem can be solved using the sliding window technique. Initially, create a window from the starting elements of the array such that its sum is greater than L. Maintain two variables i and j representing the starting and the ending index of the current window. If the sum of the current window is more than R, increment the value of i and if the sum is less than L, increment the value of j. For the windows with their sum in the range [L, R], maintain their maximum length in a variable len, which is the required answer.
Below is the implementation of the above approach:
C++
// C++ program of the above approach #include <bits/stdc++.h> using namespace std; // Function to find the length of // the longest subarray having its // sum in the given range [L, R] int largestSubArraySum( int arr[], int N, int L, int R) { // Store sum of current window int sum = 0; // Stores indices of current window int i = 0, j = 0; // Stores the maximum length int len = 0; // Calculating initial window while (sum < L && j < N) { sum += arr[j]; j++; } // Loop to iterate over all windows // of having sum in range [L, R] while (i < N && j < N) { // If sum of window is less than L if (sum < L) { sum += arr[j]; j++; } // If sum of window is more than R else if (sum > R) { sum -= arr[i]; i++; } // If sum is in the range [L, R] else { // Update length len = max(len, j - i); sum += arr[j]; j++; } } // Return Answer return len; } // Driver Code int main() { int arr[] = { 15, 2, 4, 8, 9, 5, 10, 23 }; int N = sizeof (arr) / sizeof (arr[0]); int L = 10, R = 23; cout << largestSubArraySum(arr, N, L, R); return 0; } |
Java
// Java program of the above approach class GFG { // Function to find the length of // the longest subarray having its // sum in the given range [L, R] static int largestSubArraySum( int [] arr, int N, int L, int R) { // Store sum of current window int sum = 0 ; // Stores indices of current window int i = 0 , j = 0 ; // Stores the maximum length int len = 0 ; // Calculating initial window while (sum < L && j < N) { sum += arr[j]; j++; } // Loop to iterate over all windows // of having sum in range [L, R] while (i < N && j < N) { // If sum of window is less than L if (sum < L) { sum += arr[j]; j++; } // If sum of window is more than R else if (sum > R) { sum -= arr[i]; i++; } // If sum is in the range [L, R] else { // Update length len = Math.max(len, j - i); sum += arr[j]; j++; } } // Return Answer return len; } // Driver Code public static void main(String args[]) { int [] arr = { 15 , 2 , 4 , 8 , 9 , 5 , 10 , 23 }; int N = arr.length; int L = 10 , R = 23 ; System.out.println(largestSubArraySum(arr, N, L, R)); } } // This code is contributed by Saurabh Jaiswal |
Python3
# Python 3 program of the above approach # Function to find the length of # the longest subarray having its # sum in the given range [L, R] def largestSubArraySum(arr, N, L, R): # Store sum of current window sum = 0 # Stores indices of current window i = 0 j = 0 # Stores the maximum length len = 0 # Calculating initial window while ( sum < L and j < N): sum + = arr[j] j + = 1 # Loop to iterate over all windows # of having sum in range [L, R] while (i < N and j < N): # If sum of window is less than L if ( sum < L): sum + = arr[j] j + = 1 # If sum of window is more than R elif ( sum > R): sum - = arr[i] i + = 1 # If sum is in the range [L, R] else : # Update length len = max ( len , j - i) sum + = arr[j] j + = 1 # Return Answer return len # Driver Code if __name__ = = "__main__" : arr = [ 15 , 2 , 4 , 8 , 9 , 5 , 10 , 23 ] N = len (arr) L = 10 R = 23 print (largestSubArraySum(arr, N, L, R)) # This code is contributed by gaurav01. |
C#
// C# program of the above approach using System; class GFG { // Function to find the length of // the longest subarray having its // sum in the given range [L, R] static int largestSubArraySum( int [] arr, int N, int L, int R) { // Store sum of current window int sum = 0; // Stores indices of current window int i = 0, j = 0; // Stores the maximum length int len = 0; // Calculating initial window while (sum < L && j < N) { sum += arr[j]; j++; } // Loop to iterate over all windows // of having sum in range [L, R] while (i < N && j < N) { // If sum of window is less than L if (sum < L) { sum += arr[j]; j++; } // If sum of window is more than R else if (sum > R) { sum -= arr[i]; i++; } // If sum is in the range [L, R] else { // Update length len = Math.Max(len, j - i); sum += arr[j]; j++; } } // Return Answer return len; } // Driver Code public static void Main() { int [] arr = { 15, 2, 4, 8, 9, 5, 10, 23 }; int N = arr.Length; int L = 10, R = 23; Console.WriteLine(largestSubArraySum(arr, N, L, R)); } } // This code is contributed by ukasp. |
Javascript
<script> // JavaScript program of the above approach // Function to find the length of // the longest subarray having its // sum in the given range [L, R] const largestSubArraySum = (arr, N, L, R) => { // Store sum of current window let sum = 0; // Stores indices of current window let i = 0, j = 0; // Stores the maximum length let len = 0; // Calculating initial window while (sum < L && j < N) { sum += arr[j]; j++; } // Loop to iterate over all windows // of having sum in range [L, R] while (i < N && j < N) { // If sum of window is less than L if (sum < L) { sum += arr[j]; j++; } // If sum of window is more than R else if (sum > R) { sum -= arr[i]; i++; } // If sum is in the range [L, R] else { // Update length len = Math.max(len, j - i); sum += arr[j]; j++; } } // Return Answer return len; } // Driver Code let arr = [15, 2, 4, 8, 9, 5, 10, 23]; let N = arr.length; let L = 10, R = 23; document.write(largestSubArraySum(arr, N, L, R)); // This code is contributed by rakeshsahni </script> |
4
Time Complexity: O(N)
Auxiliary Space: O(1)