Given an array arr[] of N integers and an integer K. The task is to find the number of subarrays with a maximum value is equal to K.
Examples:
Input: arr[ ] = {2, 1, 3, 4}, K = 3
Output: 3
Explanation:
Sub-arrays with maximum value is equals K are { 2, 1, 3 }, { 1, 3 }, { 3 }, hence the answer is 3.Input: arr[ ] = {1, 2, 3}, K = 1.
Output: 1
Approach: The number of subarrays in the array arr[] is equal to the number of subarrays with a maximum not greater than K minus the number of subarrays with a maximum not greater than K-1. Refer here to counting the number of subarrays with a maximum greater than K. Follow the steps below to solve the problem:
- Initialize the variable say, count1 as 0 to calculate the number of subarrays with a maximum not greater than K-1.
- Initialize the variable say, count2 as 0 to calculate the number of subarrays with a maximum not greater than K.
- Define a function say, totalSubarrays(arr, N, K) to count the number of subarrays with a maximum not greater than K and do the following steps:
- Initialize the variable say, ans as 0 to store the count of subarrays with a maximum not greater than K.
- Iterate in the range [0, N-1] and perform the following steps.
- If the value of arr[i] is greater than K, then increase the value of i by 1 and continue.
- Initialize the variable count as 0 to store the total count possible subarrays.
- Iterate in the range till i is less than N and arr[i] is less than equal to K.
- Increase the value of i and count by 1.
- Add the value of (count*(count+1))/2 to the value of ans.
- Return the value of ans.
- Calculate the number of subarrays with a maximum not greater than K-1 by calling function totalSubarrays(arr, N, K-1) and store in count1.
- Calculate the number of subarrays with a maximum not greater than K by calling function totalSubarrays(arr, N, K) and store in count2.
- Store the value of (count2 – count1) in the final value of ans and print it.
Below is the implementation of the above approach.
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// Function to count the subarrays with maximum// not greater than Kint totalSubarrays(int arr[], int n, int k){ int ans = 0, i = 0; while (i < n) { // If arr[i]>k then arr[i] cannot be // a part of any subarray. if (arr[i] > k) { i++; continue; } int count = 0; // Count the number of elements where // arr[i] is not greater than k. while (i < n && arr[i] <= k) { i++; count++; } // Summation of all possible subarrays // in the variable ans. ans += ((count * (count + 1)) / 2); } return ans;}// Function to count the subarrays with// maximum value is equal to Kint countSubarrays(int arr[], int n, int k){ // Stores count of subarrays with max <= k - 1. int count1 = totalSubarrays(arr, n, k - 1); // Stores count of subarrays with max >= k + 1. int count2 = totalSubarrays(arr, n, k); // Stores count of subarrays with max = k. int ans = count2 - count1; return ans;}// Driver Codeint main(){ // Given Input int n = 4, k = 3; int arr[] = { 2, 1, 3, 4 }; // Function Call cout << countSubarrays(arr, n, k); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG { // Function to count the subarrays with maximum // not greater than K static int totalSubarrays(int arr[], int n, int k) { int ans = 0, i = 0; while (i < n) { // If arr[i]>k then arr[i] cannot be // a part of any subarray. if (arr[i] > k) { i++; continue; } int count = 0; // Count the number of elements where // arr[i] is not greater than k. while (i < n && arr[i] <= k) { i++; count++; } // Summation of all possible subarrays // in the variable ans. ans += ((count * (count + 1)) / 2); } return ans; } // Function to count the subarrays with // maximum value is equal to K static int countSubarrays(int arr[], int n, int k) { // Stores count of subarrays with max <= k - 1. int count1 = totalSubarrays(arr, n, k - 1); // Stores count of subarrays with max >= k + 1. int count2 = totalSubarrays(arr, n, k); // Stores count of subarrays with max = k. int ans = count2 - count1; return ans; } // Driver Code public static void main(String[] args) { // Given Input int n = 4, k = 3; int arr[] = { 2, 1, 3, 4 }; // Function Call System.out.println(countSubarrays(arr, n, k)); // This code is contributed by Potta Lokesh }} |
Python3
# Python3 implementation of the above approach# Function to count the subarrays with maximum# not greater than Kdef totalSubarrays(arr, n, k): ans = 0 i = 0 while (i < n): # If arr[i]>k then arr[i] cannot be # a part of any subarray. if (arr[i] > k): i += 1 continue count = 0 # Count the number of elements where # arr[i] is not greater than k. while (i < n and arr[i] <= k): i += 1 count += 1 # Summation of all possible subarrays # in the variable ans. ans += ((count * (count + 1)) // 2) return ans# Function to count the subarrays with# maximum value is equal to Kdef countSubarrays(arr, n, k): # Stores count of subarrays with max <= k - 1. count1 = totalSubarrays(arr, n, k - 1) # Stores count of subarrays with max >= k + 1. count2 = totalSubarrays(arr, n, k) # Stores count of subarrays with max = k. ans = count2 - count1 return ans# Driver Codeif __name__ == '__main__': # Given Input n = 4 k = 3 arr = [ 2, 1, 3, 4 ] # Function Call print(countSubarrays(arr, n, k))# This code is contributed by ipg2016107 |
C#
// C# program for the above approachusing System;class GFG{ // Function to count the subarrays with maximum // not greater than K static int totalSubarrays(int[] arr, int n, int k) { int ans = 0, i = 0; while (i < n) { // If arr[i]>k then arr[i] cannot be // a part of any subarray. if (arr[i] > k) { i++; continue; } int count = 0; // Count the number of elements where // arr[i] is not greater than k. while (i < n && arr[i] <= k) { i++; count++; } // Summation of all possible subarrays // in the variable ans. ans += ((count * (count + 1)) / 2); } return ans; } // Function to count the subarrays with // maximum value is equal to K static int countSubarrays(int[] arr, int n, int k) { // Stores count of subarrays with max <= k - 1. int count1 = totalSubarrays(arr, n, k - 1); // Stores count of subarrays with max >= k + 1. int count2 = totalSubarrays(arr, n, k); // Stores count of subarrays with max = k. int ans = count2 - count1; return ans; } static void Main() { // Given Input int n = 4, k = 3; int[] arr = { 2, 1, 3, 4 }; // Function Call Console.WriteLine(countSubarrays(arr, n, k)); }}// This code is contributed by abhinavjain194 |
Javascript
<script> // JavaScript program for the above approach // Function to count the subarrays with maximum // not greater than K function totalSubarrays(arr, n, k) { let ans = 0, i = 0; while (i < n) { // If arr[i]>k then arr[i] cannot be // a part of any subarray. if (arr[i] > k) { i++; continue; } let count = 0; // Count the number of elements where // arr[i] is not greater than k. while (i < n && arr[i] <= k) { i++; count++; } // Summation of all possible subarrays // in the variable ans. ans += (Math.floor((count * (count + 1)) / 2)); } return ans; } // Function to count the subarrays with // maximum value is equal to K function countSubarrays(arr, n, k) { // Stores count of subarrays with max <= k - 1. let count1 = totalSubarrays(arr, n, k - 1); // Stores count of subarrays with max >= k + 1. let count2 = totalSubarrays(arr, n, k); // Stores count of subarrays with max = k. let ans = count2 - count1; return ans; } // Driver Code // Given Input let n = 4, k = 3; let arr = [2, 1, 3, 4]; // Function Call document.write(countSubarrays(arr, n, k)); // This code is contributed by Potta Lokesh </script> |
Output
3
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
