Approach 3 : Sliding Window Technique.
Algorithm:
1. Initialize a variable ans = 0 , a varialble maxElement = 0 and a variable count = 0 .
2. Iterate through the array, doing the following for each element:
a. If the current element i.e. arr[ i ] is greater than current maximum , update the maximum i.e. maxElement = arr[ i ] and reset the count to 0.
b. If the current element is less than or eual to the current maximum, then increment the count.
c. If maxElement is grteater than k, then add count of subarrays to final answer and update the maxElement to current element.
3. Return Final answer.
Here’s the the implementation of Sliding window technique.
C++
#include <bits/stdc++.h> using namespace std; int countSubarray(int arr[], int n, int k) { int maxElement = 0, count = 0, ans = 0; for(int i=0; i<n; i++) { if(arr[i] > maxElement) { maxElement = arr[i]; count = 0; } else { count++; } if(maxElement > k) { ans += (i - count + 1); maxElement = arr[i]; count = 0; } } return ans; } int main() { int arr[] = {1, 2, 3, 4}; int k = 1; int n = sizeof(arr) / sizeof(arr[0]); cout << countSubarray(arr, n, k); return 0; } // This code is contributed by Vaibhav Saroj |
C
#include <stdio.h> int countSubarray(int arr[], int n, int k) { int maxElement = 0, count = 0, ans = 0; for(int i=0; i<n; i++) { if(arr[i] > maxElement) { maxElement = arr[i]; count = 0; } else { count++; } if(maxElement > k) { ans += (i - count + 1); maxElement = arr[i]; count = 0; } } ans += (count * (count + 1)) / 2; return ans; } int main() { int arr[] = {1, 2, 3, 4}; int k = 1; int n = sizeof(arr) / sizeof(arr[0]); printf("%d\n", countSubarray(arr, n, k)); return 0; } // This code is contributed by Vaibhav Saroj |
Java
import java.util.*; public class GFG { // Function to count the number of subarrays with the maximum element greater than k public static int countSubarray(int[] arr, int n, int k) { int maxElement = 0; // Variable to store the maximum element encountered so far int count = 0; // Variable to count the length of the subarray with elements <= k int ans = 0; // Variable to store the final result for (int i = 0; i < n; i++) { if (arr[i] > maxElement) { // If the current element is greater than the maximum element // update the maximum element and reset the count to zero. maxElement = arr[i]; count = 0; } else { // increment the count count++; } if (maxElement > k) { // If the maximum element in the current subarray is greater than k, // add the count of subarrays ending at the current index (i - count + 1) to the result. ans += (i - count + 1); // Reset the maximum element and count to zero. maxElement = arr[i]; count = 0; } } // Return the final result return ans; } public static void main(String[] args) { int[] arr = {1, 2, 3, 4}; int k = 1; int n = arr.length; // Call the countSubarray function to count the number of subarrays with maximum element greater than k int result = countSubarray(arr, n, k); System.out.println(result); } } // THIS CODE IS CONTRIBUTED BY KIRTI AGARWAL |
Python3
def countSubarray(arr, n, k): maxElement, count, ans = 0, 0, 0 for i in range(n): if arr[i] > maxElement: maxElement = arr[i] count = 0 else: count += 1 if maxElement > k: ans += (i - count + 1) maxElement = arr[i] count = 0 ans += (count * (count + 1)) // 2 return ans arr = [1, 2, 3, 4] k = 1n = len(arr) print(countSubarray(arr, n, k)) # This code is contributed by Vaibhav Saroj |
C#
using System; public class Program { public static int CountSubarray(int[] arr, int n, int k) { int maxElement = 0, count = 0, ans = 0; for(int i=0; i<n; i++) { if(arr[i] > maxElement) { maxElement = arr[i]; count = 0; } else { count++; } if(maxElement > k) { ans += (i - count + 1); maxElement = arr[i]; count = 0; } } ans += (count * (count + 1)) / 2; return ans; } public static void Main() { int[] arr = {1, 2, 3, 4}; int k = 1; int n = arr.Length; Console.WriteLine(CountSubarray(arr, n, k)); } } // This code is contributed by Vaibhav Saroj |
Javascript
function countSubarray(arr, n, k) { let maxElement = 0, count = 0, ans = 0; for(let i=0; i<n; i++) { if(arr[i] > maxElement) { maxElement = arr[i]; count = 0; } else { count++; } if(maxElement > k) { ans += (i - count + 1); maxElement = arr[i]; count = 0; } } ans += (count * (count + 1)) / 2; return ans; } let arr = [1, 2, 3, 4]; let k = 1; let n = arr.length; console.log(countSubarray(arr, n, k)); // This code is contributed by Vaibhav Saroj |
Output
9
The Sliding Window Technique is contributed by Vaibhav Saroj .
Time Complexity: O( n ).
Space Complexity: O( 1 ).
Practice here Count of Subarrays .
Count of subarrays whose maximum element is greater than k
Given an array of n elements and an integer k. The task is to find the count of the subarray which has a maximum element greater than K.
Examples :
Input : arr[] = {1, 2, 3} and k = 2.
Output : 3
All the possible subarrays of arr[] are
{ 1 }, { 2 }, { 3 }, { 1, 2 }, { 2, 3 },
{ 1, 2, 3 }.
Their maximum elements are 1, 2, 3, 2, 3, 3.
There are only 3 maximum elements > 2.