Day 51: Count of Subarrays

/*
Count of Subarrays

Given an array of N positive integers  Arr1, Arr2 ............ Arrn. The value of each contiguous subarray of given array is the maximum element present in that subarray. The task is to return the number of subarrays having value strictly greater than K.

Example 1:

Input:
N = 3, K = 2
Arr[] = {3, 2, 1}
Output: 3
Explanation: The subarrays having value
strictly greater than K are: [3], [3, 2]
and [3, 2, 1]. Thus there are 3 such
subarrays.
Example 2:

Input:
N = 4, K = 1
Arr[] = {1, 2, 3, 4}
Output: 9
Explanation: There are 9 subarrays having
value strictly greater than K.
Your Task:
Complete the function countSubarray() which takes an array arr, two integers n, k, as input parameters and returns an integer denoting the answer. You don't to print answer or take inputs.

Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

Constraints:
1 <= N <= 105
1 <= Arr[i] <= 105
*/


//{ Driver Code Starts
// Initial Template for Java

import java.io.*;
import java.util.*;

class GFG {
    // Driver code
    public static void main(String[] args) throws Exception {
        BufferedReader br =
            new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine().trim());
        while (t-- > 0) {
            String[] str = br.readLine().trim().split(" ");
            int n = Integer.parseInt(str[0]);
            int k = Integer.parseInt(str[1]);
            str = br.readLine().trim().split(" ");
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = Integer.parseInt(str[i]);
            }

            long ans = new Solution().countSubarray(arr, n, k);

            System.out.println(ans);
        }
    }
}

// } Driver Code Ends


// User function Template for Java


class Solution {

    long getSubArrayCount(long n)
    {
        //long n = num;
        return n * (n + 1) / 2;
    }
    long countSubarray(int arr[], int n, int k) 
    {
        
        long total_subarray = getSubArrayCount(n);
        long rem_subarray=0;
        int curSub = 0;
        for(int i = 0;i < n;i++)
        {
            if(arr[i] <= k) curSub++;
            else
            {
                rem_subarray += getSubArrayCount(curSub);
                curSub = 0;
            }
        }
        rem_subarray += getSubArrayCount(curSub);
       // System.out.println(total_subarray +" -- " + rem_subarray);
        return total_subarray - rem_subarray;
    }
}