Count of subarrays with maximum value as K

0 0 6 minutes read

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 K
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
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
int 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 approach
 
import 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 K
def 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 K
def 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 Code
if __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 approach
using 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

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 zambiatek!