Given an array arr[] of length N, the task is to find the number of non-decreasing sub-arrays of length K.
Examples:
Input: arr[] = {1, 2, 3, 2, 5}, K = 2
Output: 3
{1, 2}, {2, 3} and {2, 5} are the increasing
subarrays of length 2.
Input: arr[] = {1, 2, 3, 2, 5}, K = 1
Output: 5
Naive approach Generate all the sub-arrays of length K and then check whether the sub-array satisfies the condition. Thus, the time complexity of the approach will be O(N * K).
Better approach: A better approach will be using two-pointer technique. Let’s say the current index is i.
- Find the largest index j, such that the sub-array arr[i…j] is non-decreasing. This can be achieved by simply incrementing the value of j starting from i + 1 and checking whether arr[j] is greater than arr[j – 1].
- Let’s say the length of the sub-array found in the previous step is L. The number of sub-arrays of length K contained in it will be max(L – K + 1, 0).
- Now, update i = j and repeat the above steps while i is in the index range.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the count of// increasing subarrays of length kint cntSubArrays(int* arr, int n, int k){ // To store the final result int res = 0; int i = 0; // Two pointer loop while (i < n) { // Initialising j int j = i + 1; // Looping till the subarray increases while (j < n and arr[j] >= arr[j - 1]) j++; // Updating the required count res += max(j - i - k + 1, 0); // Updating i i = j; } // Returning res return res;}// Driver codeint main(){ int arr[] = { 1, 2, 3, 2, 5 }; int n = sizeof(arr) / sizeof(int); int k = 2; cout << cntSubArrays(arr, n, k); return 0;} |
Java
// Java implementation of the approachclass GFG{// Function to return the count of// increasing subarrays of length kstatic int cntSubArrays(int []arr, int n, int k){ // To store the final result int res = 0; int i = 0; // Two pointer loop while (i < n) { // Initialising j int j = i + 1; // Looping till the subarray increases while (j < n && arr[j] >= arr[j - 1]) j++; // Updating the required count res += Math.max(j - i - k + 1, 0); // Updating i i = j; } // Returning res return res;}// Driver codepublic static void main(String []args){ int arr[] = { 1, 2, 3, 2, 5 }; int n = arr.length; int k = 2; System.out.println(cntSubArrays(arr, n, k));}}// This code is contributed by PrinciRaj1992 |
Python3
# Python3 implementation of the approach # Function to return the count of # increasing subarrays of length k def cntSubArrays(arr, n, k) : # To store the final result res = 0; i = 0; # Two pointer loop while (i < n) : # Initialising j j = i + 1; # Looping till the subarray increases while (j < n and arr[j] >= arr[j - 1]) : j += 1; # Updating the required count res += max(j - i - k + 1, 0); # Updating i i = j; # Returning res return res; # Driver code if __name__ == "__main__" : arr = [ 1, 2, 3, 2, 5 ]; n = len(arr); k = 2; print(cntSubArrays(arr, n, k)); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approachusing System; class GFG{// Function to return the count of// increasing subarrays of length kstatic int cntSubArrays(int []arr, int n, int k){ // To store the final result int res = 0; int i = 0; // Two pointer loop while (i < n) { // Initialising j int j = i + 1; // Looping till the subarray increases while (j < n && arr[j] >= arr[j - 1]) j++; // Updating the required count res += Math.Max(j - i - k + 1, 0); // Updating i i = j; } // Returning res return res;}// Driver codepublic static void Main(String []args){ int []arr = { 1, 2, 3, 2, 5 }; int n = arr.Length; int k = 2; Console.WriteLine(cntSubArrays(arr, n, k));}}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript implementation of the approach// Function to return the count of// increasing subarrays of length kfunction cntSubArrays(arr, n, k){ // To store the final result var res = 0; var i = 0; // Two pointer loop while (i < n) { // Initialising j var j = i + 1; // Looping till the subarray increases while (j < n && arr[j] >= arr[j - 1]) j++; // Updating the required count res += Math.max(j - i - k + 1, 0); // Updating i i = j; } // Returning res return res;}// Driver codevar arr = [ 1, 2, 3, 2, 5 ];var n = arr.length;var k = 2;document.write( cntSubArrays(arr, n, k));</script> |
3
Time Complexity: O(n)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

… [Trackback]
[…] Information on that Topic: geeksforgeeks.org/number-of-non-decreasing-sub-arrays-of-length-k/ […]
… [Trackback]
[…] Read More to that Topic: geeksforgeeks.org/number-of-non-decreasing-sub-arrays-of-length-k/ […]