Given an array arr[] of length N. The task is to find the length of the longest subarray in which elements greater than a given number K are more than elements not greater than K.
Examples:
Input : N = 5, K = 2, arr[]={ 1, 2, 3, 4, 1 }
Output : 3
The subarray [2, 3, 4] or [3, 4, 1] satisfy the given condition, and there is no subarray of
length 4 or 5 which will hold the given condition, so the answer is 3.Input : N = 4, K = 2, arr[]={ 6, 5, 3, 4 }
Output : 4
Approach:
- Idea is to use the concept of binary search over Partial Sum .
- Create a new array pre[] of size n, initialized to 0.
- Traverse the input array a[] of size n, and for each element a[i], do the following:
- If a[i] > k, set pre[i] to 1.
- Else, set pre[i] to -1.
- Traverse the pre[] array of size n, and compute its prefix sum in place, i.e., update each pre[i] to hold the sum of all elements from pre[0] to pre[i]. You can use the following code snippet for this:
for (int i = 1; i < n; i++) pre[i] = pre[i - 1] + pre[i];
- Initialize lo to 1 and hi to n.
- Perform binary search over the possible lengths of subarrays, i.e., while lo <= hi, do the following:
- Set mid to (lo + hi) / 2.
- Set ok to false.
- For each subarray of length mid, check if its sum is greater than 0, i.e., if pre[i] – pre[i-mid] > 0, for some index i >= mid-1 and i < n. If such a subarray exists, set ok to true and break out of the loop.
- If ok is true, update the length of the longest subarray seen so far to mid, and set lo to mid+1.
- Else, set hi to mid-1.
- Return the length of the longest subarray seen so far, which is stored in the variable len.
Below is the implementation of above Approach:
C++
#include <bits/stdc++.h>using namespace std;// C++ implementation of above approach// Function to find the length of a // longest subarray in which elements // greater than K are more than // elements not greater than Kint LongestSubarray(int a[], int n, int k){ int pre[n] = { 0 }; // Create a new array in which we store 1 // if a[i] > k otherwise we store -1. for (int i = 0; i < n; i++) { if (a[i] > k) pre[i] = 1; else pre[i] = -1; } // Taking prefix sum over it for (int i = 1; i < n; i++) pre[i] = pre[i - 1] + pre[i]; // len will store maximum // length of subarray int len = 0; int lo = 1, hi = n; while (lo <= hi) { int mid = (lo + hi) / 2; // This indicate there is at least one // subarray of length mid that has sum > 0 bool ok = false; // Check every subarray of length mid if // it has sum > 0 or not if sum > 0 then it // will satisfy our required condition for (int i = mid - 1; i < n; i++) { // x will store the sum of // subarray of length mid int x = pre[i]; if (i - mid >= 0) x -= pre[i - mid]; // Satisfy our given condition if (x > 0) { ok = true; break; } } // Check for higher length as we // get length mid if (ok == true) { len = mid; lo = mid + 1; } // Check for lower length as we // did not get length mid else hi = mid - 1; } return len;}// Driver codeint main(){ int a[] = { 2, 3, 4, 5, 3, 7 }; int k = 3; int n = sizeof(a) / sizeof(a[0]); cout << LongestSubarray(a, n, k); return 0;} |
Java
// Java implementation of above approachclass GFG {// Function to find the length of a // longest subarray in which elements // greater than K are more than // elements not greater than Kstatic int LongestSubarray(int a[], int n, int k){ int []pre = new int[n]; // Create a new array in which we store 1 // if a[i] > k otherwise we store -1. for (int i = 0; i < n; i++) { if (a[i] > k) pre[i] = 1; else pre[i] = -1; } // Taking prefix sum over it for (int i = 1; i < n; i++) pre[i] = pre[i - 1] + pre[i]; // len will store maximum // length of subarray int len = 0; int lo = 1, hi = n; while (lo <= hi) { int mid = (lo + hi) / 2; // This indicate there is at least one // subarray of length mid that has sum > 0 boolean ok = false; // Check every subarray of length mid if // it has sum > 0 or not if sum > 0 then it // will satisfy our required condition for (int i = mid - 1; i < n; i++) { // x will store the sum of // subarray of length mid int x = pre[i]; if (i - mid >= 0) x -= pre[i - mid]; // Satisfy our given condition if (x > 0) { ok = true; break; } } // Check for higher length as we // get length mid if (ok == true) { len = mid; lo = mid + 1; } // Check for lower length as we // did not get length mid else hi = mid - 1; } return len;}// Driver codepublic static void main(String[] args){ int a[] = { 2, 3, 4, 5, 3, 7 }; int k = 3; int n = a.length; System.out.println(LongestSubarray(a, n, k));}}// This code is contributed by 29AjayKumar |
Python3
# Python3 implementation of above approach# Function to find the Length of a# longest subarray in which elements# greater than K are more than# elements not greater than Kdef LongestSubarray(a, n, k): pre = [0 for i in range(n)] # Create a new array in which we store 1 # if a[i] > k otherwise we store -1. for i in range(n): if (a[i] > k): pre[i] = 1 else: pre[i] = -1 # Taking prefix sum over it for i in range(1, n): pre[i] = pre[i - 1] + pre[i] # Len will store maximum # Length of subarray Len = 0 lo = 1 hi = n while (lo <= hi): mid = (lo + hi) // 2 # This indicate there is at least one # subarray of Length mid that has sum > 0 ok = False # Check every subarray of Length mid if # it has sum > 0 or not if sum > 0 then it # will satisfy our required condition for i in range(mid - 1, n): # x will store the sum of # subarray of Length mid x = pre[i] if (i - mid >= 0): x -= pre[i - mid] # Satisfy our given condition if (x > 0): ok = True break # Check for higher Length as we # get Length mid if (ok == True): Len = mid lo = mid + 1 # Check for lower Length as we # did not get Length mid else: hi = mid - 1 return Len# Driver codea = [2, 3, 4, 5, 3, 7]k = 3n = len(a)print(LongestSubarray(a, n, k))# This code is contributed by Mohit Kumar |
C#
// C# implementation of above approachusing System;class GFG {// Function to find the length of a // longest subarray in which elements // greater than K are more than // elements not greater than Kstatic int LongestSubarray(int[] a, int n, int k){ int []pre = new int[n]; // Create a new array in which we store 1 // if a[i] > k otherwise we store -1. for (int i = 0; i < n; i++) { if (a[i] > k) pre[i] = 1; else pre[i] = -1; } // Taking prefix sum over it for (int i = 1; i < n; i++) pre[i] = pre[i - 1] + pre[i]; // len will store maximum // length of subarray int len = 0; int lo = 1, hi = n; while (lo <= hi) { int mid = (lo + hi) / 2; // This indicate there is at least one // subarray of length mid that has sum > 0 bool ok = false; // Check every subarray of length mid if // it has sum > 0 or not if sum > 0 then it // will satisfy our required condition for (int i = mid - 1; i < n; i++) { // x will store the sum of // subarray of length mid int x = pre[i]; if (i - mid >= 0) x -= pre[i - mid]; // Satisfy our given condition if (x > 0) { ok = true; break; } } // Check for higher length as we // get length mid if (ok == true) { len = mid; lo = mid + 1; } // Check for lower length as we // did not get length mid else hi = mid - 1; } return len;}// Driver codepublic static void Main(){ int[] a = { 2, 3, 4, 5, 3, 7 }; int k = 3; int n = a.Length; Console.WriteLine(LongestSubarray(a, n, k));}}// This code is contributed by Code_Mech |
Javascript
<script>// javascript implementation of above approach// Function to find the length of a // longest subarray in which elements // greater than K are more than // elements not greater than Kfunction LongestSubarray(a , n , k){ var pre = Array.from({length: n}, (_, i) => 0); // Create a new array in which we store 1 // if a[i] > k otherwise we store -1. for (i = 0; i < n; i++) { if (a[i] > k) pre[i] = 1; else pre[i] = -1; } // Taking prefix sum over it for (i = 1; i < n; i++) pre[i] = pre[i - 1] + pre[i]; // len will store maximum // length of subarray var len = 0; var lo = 1, hi = n; while (lo <= hi) { var mid = parseInt((lo + hi) / 2); // This indicate there is at least one // subarray of length mid that has sum > 0 var ok = false; // Check every subarray of length mid if // it has sum > 0 or not if sum > 0 then it // will satisfy our required condition for (i = mid - 1; i < n; i++) { // x will store the sum of // subarray of length mid var x = pre[i]; if (i - mid >= 0) x -= pre[i - mid]; // Satisfy our given condition if (x > 0) { ok = true; break; } } // Check for higher length as we // get length mid if (ok == true) { len = mid; lo = mid + 1; } // Check for lower length as we // did not get length mid else hi = mid - 1; } return len;}// Driver codevar a = [ 2, 3, 4, 5, 3, 7 ];var k = 3;var n = a.length;document.write(LongestSubarray(a, n, k));// This code is contributed by shikhasingrajput </script> |
Output
5
Time Complexity: O(N*logN)
Auxiliary Space: O(N)
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!
… [Trackback]
[…] Find More on on that Topic: geeksforgeeks.org/length-of-longest-subarray-in-which-elements-greater-than-k-are-more-than-elements-not-greater-than-k/ […]
… [Trackback]
[…] Find More Info here on that Topic: geeksforgeeks.org/length-of-longest-subarray-in-which-elements-greater-than-k-are-more-than-elements-not-greater-than-k/ […]
… [Trackback]
[…] Find More Info here to that Topic: geeksforgeeks.org/length-of-longest-subarray-in-which-elements-greater-than-k-are-more-than-elements-not-greater-than-k/ […]