Count subarrays for every array element in which they are the minimum

Given an array arr[] consisting of N integers, the task is to create an array brr[] of size N where brr[i] represents the count of subarrays in which arr[i] is the smallest element.

Examples:

Input: arr[] = {3, 2, 4} 

Output: {1, 3, 1} 

Explanation: 

For arr[0], there is only one subarray in which 3 is the smallest({3}). 

For arr[1], there are three such subarrays where 2 is the smallest({2}, {3, 2}, {2, 4}). 

For arr[2], there is only one subarray in which 4 is the smallest({4}).

Input: arr[] = {1, 2, 3, 4, 5} 

Output: {5, 4, 3, 2, 1}

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Naive Approach: The simplest approach is to generate all subarrays of the given array and for every array element arr[i], count the number of subarrays in which it is the smallest element. 

Time Complexity: O(2N) 

Auxiliary Space: O(N)

Efficient Approach: To optimize the above approach, the idea is to find the boundary index for every element, up to which it is the smallest element. For each element let L and R be the boundary indices on the left and right side respectively up to which arr[i] is the minimum. Therefore, the count of all subarrays can be calculated by:

(L + R + 1)*(R + 1)

Follow the steps below to solve the problem:

Store all the indices of array elements in a Map.

Sort the array in increasing order.

Initialize an array boundary[].

Iterate over the sorted array arr[] and simply insert the index of that element using Binary Search. Suppose it got inserted at index i, then its left boundary is boundary[i – 1] and its right boundary is boundary[i + 1].

Now, using the above formula, find the number of subarrays and keep track of that count in the resultant array.

After completing the above steps, print all the counts stored in resultant array.

Below is the implementation of the above approach:

// C++14 program for the above approach 

#include <bits/stdc++.h> 

using namespace std; 

  

// Function to find the boundary of every 

// element within which it is minimum 

int binaryInsert(vector<int> &boundary, int i) 

{ 

    int l = 0; 

    int r = boundary.size() - 1; 

  

    // Perform Binary Search 

    while (l <= r) 

    { 

          

        // Find mid m 

        int m = (l + r) / 2; 

  

        // Update l 

        if (boundary[m] < i) 

            l = m + 1; 

  

        // Update r 

        else

            r = m - 1; 

    } 

  

    // Inserting the index 

    boundary.insert(boundary.begin() + l, i); 

  

    return l; 

} 

  

// Function to required count subarrays 

vector<int> countingSubarray(vector<int> arr, int n) 

{ 

      

    // Stores the indices of element 

    unordered_map<int, int> index; 

  

    for(int i = 0; i < n; i++) 

        index[arr[i]] = i; 

  

    vector<int> boundary = {-1, n}; 

    sort(arr.begin(), arr.end()); 

  

    // Initialize the output array 

    vector<int> ans(n, 0); 

  

    for(int num : arr) 

    { 

        int i = binaryInsert(boundary, index[num]); 

  

        // Left boundary, till the 

        // element is smallest 

        int l = boundary[i] - boundary[i - 1] - 1; 

  

        // Right boundary, till the 

        // element is smallest 

        int r = boundary[i + 1] - boundary[i] - 1; 

  

        // Calculate the number of subarrays 

        // based on its boundary 

        int cnt = l + r + l * r + 1; 

  

        // Adding cnt to the ans 

        ans[index[num]] += cnt; 

    } 

    return ans; 

} 

  

// Driver Code 

int main() 

{ 

    int N = 5; 

      

    // Given array arr[] 

    vector<int> arr = { 3, 2, 4, 1, 5 }; 

      

    // Function call 

    auto a = countingSubarray(arr, N); 

      

    cout << "["; 

    int n = a.size() - 1; 

    for(int i = 0; i < n; i++)  

        cout << a[i] << ", "; 

          

    cout << a[n] << "]"; 

      

    return 0; 

} 

  

// This code is contributed by mohit kumar 29 

Output: 

[1, 4, 1, 8, 1]

Time Complexity: O(N log N) 

Auxiliary Space: O(N)

# Python3 program for the above approach 

  

# Function to find the boundary of every 

# element within which it is minimum 

def binaryInsert(boundary, i): 

  

    l = 0

    r = len(boundary) - 1

  

    # Perform Binary Search 

    while l <= r: 

          

        # Find mid m 

        m = (l + r) // 2

          

        # Update l 

        if boundary[m] < i: 

            l = m + 1

              

        # Update r 

        else: 

            r = m - 1

  

    # Inserting the index 

    boundary.insert(l, i) 

  

    return l 

  

# Function to required count subarrays 

def countingSubarray(arr, n): 

  

    # Stores the indices of element 

    index = {} 

  

    for i in range(n): 

        index[arr[i]] = i 

  

    boundary = [-1, n] 

    arr.sort() 

  

    # Initialize the output array 

    ans = [0 for i in range(n)] 

  

    for num in arr: 

        i = binaryInsert(boundary, index[num]) 

  

        # Left boundary, till the 

        # element is smallest 

        l = boundary[i] - boundary[i - 1] - 1

  

        # Right boundary, till the 

        # element is smallest 

        r = boundary[i + 1] - boundary[i] - 1

  

        # Calculate the number of subarrays 

        # based on its boundary 

        cnt = l + r + l * r + 1

  

        # Adding cnt to the ans 

        ans[index[num]] += cnt 

  

    return ans 

  

  

# Driver Code 

  

N = 5

  

# Given array arr[] 

arr = [3, 2, 4, 1, 5] 

  

# Function Call 

print(countingSubarray(arr, N))