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

Vibhor Bhatnagar
Last Updated: May 13, 2022

Introduction

In this blog, we will discuss the various approaches to solve the problem count subarrays for every array element in which they are the minimum. Before jumping into the problem, let’s first understand what this problem is asking us to do?

So, this problem asks us to count all the subarrays for every array element in which that element is minimum. There are many approaches to this problem, but before discussing them, we should Functionlook at some examples of this problem to understand the problem better.

Some Examples

Input:

 arr[] = {1,2,3}

Output: 

{3,2,1}

Explanation:

  • There are three sub-arrays in which arr[0] occurs as a minimum, and those are {1}, {1,2}, {1,2,3}.
  • There are two subarrays in which arr[1] occurs as a minimum, and those are {2}, {2,3}.
  • There is only one subarray in which arr[0] occurs as a minimum, and that is {3}.

 

Input:

arr[] = {2,7,4,9}

Output:

{4,1,4,1}

Explanation:

  • There are four subarrays in which arr[0] occurs as a minimum element, and    those are {2}, {2,7}, {2,7,4}, {2,7,4,9}.
  • There is only one subarray in which arr[1] occurs as a minimum element, and that is {7}.
  • There are four subarrays in which arr[2] occurs as a minimum element, and those are {4}, {7,4}, {4,9}, {7,4,9}.
  • There is only one subarray in which arr[3] occurs as a minimum element, and that is {9}.           

Brute Force Approach

The brute force approach of this problem to “Count subarrays for every array element in which they are the minimum” generates all the subarrays and then finds a minimum element in every subarray and hashing it in the map. After that, we have to place those values in the respective positions of elements of the array. 

Algorithm

  1. Create a function minimumsOfSubarray() which takes two parameters:: the array itself, and the other is the array’s length.
  2. In the function, we will traverse two nested for loops to generate subarrays and simultaneously hash the minimum value of the subarray at every instance of the inner loop.    
  3. After that, we will print the hash values of every element of the array.

Code in C++

// Count subarrays for every array element in which they are the minimum
#include <bits/stdc++.h>
using namespace std;

// function to generate all the subarrays of an array
// and hashing the minimum element of the subarrays
void minimumsOfSubarray(int arr[], int N)
{

    // Map for storing the frequencies of the
    // minimum of every subarray
    unordered_map<int, int> m;

    // Traversing all possible subarrays and hashing the
    // minimum element of the subarray simultaneously
    for (int i = 0; i < N; i++)
    {

        int minimum_element = INT_MAX;

        for (int j = i; j < N; j++)
        {

            // Minimum element of each subarray
            minimum_element = min(minimum_element, arr[j]);
            m[minimum_element]++;
        }
    }

    // Printing the output
    for (int i = 0; i < N; i++)
    {

        cout << m[arr[i]] << " ";
    }
}

// Driver Code
int main()
{

    int arr[] = {4, 7, 8, 9};
    int n=4;

    minimumsOfSubarray(arr, n);

    return 0;
}

 

Input: 4 7 8 9
Output: 4 3 2 1 

Complexity Analysis

Time Complexity: O(N*N)

Since we are using two nested loops and every element we are traversing from the index of that element to N. So time complexity will be the sum of N+N-1+N-2+N-3+ …1, and the sum of this series will be (N*(N+1))/2, and if the values of N are large, then this sum would be approximately equal to N*N.

Space Complexity: O(N)

Since we are using a map to store the frequency of the minimum element of all the subarrays, space complexity will be O(N).

Efficient Approach

In the above-discussed approach, the complexity is very high, and therefore, we need to develop a more efficient approach.

So in this approach, we will find the boundaries of every element in which it is the smallest and then use a simple formula to calculate subarrays in which it would be the smallest element. So if L is the left boundary and R is the right boundary, then the subarrays present in this range would be calculated using this formula:

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

Algorithm

  1. Store all the indices of array elements in a map.
  2. Sort the array in increasing order.
  3. Initialize array boundaries having two values {-1, N} here N is the size of the given array.
  4. Now, iterate over the sorted array and insert the index of that element in the boundaries array using binary search. Let us suppose it got inserted at index i, then its left boundary would be boundaries[i-1], and its right boundary would be boundaries[i+1].
  5. Use the above formula to calculate the answer for every element and then store that answer in another array. Now, return this array.

Code in C++

// Count subarrays for every array element in which they are the minimum
#include <bits/stdc++.h>
using namespace std;

// Function to find the boundary of every
// element in which it is minimum
int findBoundaryForElement(vector<int> &boundaries, int i)
{
    int l = 0;
    int r = boundaries.size() - 1;

    // Performing Binary Search
    while (l <= r)
    {

        // Finding mid m
        int m = (l + r) / 2;

        // Updating l
        if (boundaries[m] < i)
            l = m + 1;

        // Updating r
        else
            r = m - 1;
    }

    // Inserting the index in the vector
    boundaries.insert(boundaries.begin() + l, i);

    return l;
}

// Function to count subarrays
vector<int> countingSubarraysForElements(vector<int> a, int n)
{

    // Declaring a map for storing indices of elements
    unordered_map<int, int> indexOfElements;

    for (int i = 0; i < n; i++)
    indexOfElements[a[i]] = i;

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

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

    // Initialize the output array
    vector<int> ans(n, 0);

    for (int x: a)
    {
        int i = findBoundaryForElement(boundaries,indexOfElements[x]);

        // Left boundary for the element
        int l = boundaries[i] - boundaries[i - 1] - 1;

        // Right boundary for the element
        int r = boundaries[i + 1] - boundaries[i] - 1;

  // Calculating number of subarrays in which the element is smallest
        int countOfSubarrays = l + r + l * r + 1;

        // Adding countOfSubarrays to the ans
        ans[indexOfElements[x]] += countOfSubarrays;
    }
    return ans;
}

// Driver Code
int main()
{
    int n = 5;

    // Given array a[]
    vector<int> a = {7,12,1,4,9};

    vector<int> ans = countingSubarraysForElements(a, n);

    n = ans.size() - 1;
    for (int i = 0; i < n; i++)
        cout << ans[i] << " ";

    cout << ans[n];

    return 0;
}

 

Input: 7 12 1 4 9
Output: 2 1 9 2 1

 

Complexity Analysis

Time Complexity: O(N * log(N))

Since we are doing a binary search for every element of the array, the time complexity is O(N * log(N)).

Space Complexity: O(N * W)

Therefore, as we are using an extra map and an extra array, the overall space complexity is O(N).

Optimized Approach

In the above approach, we are doing a binary search for every element. Therefore, the complexity exceeds N, so to get a better approach, we will use the concept of the next greater element and the previous greater element, which is implemented using stack.

We will find the index of the previous smaller element and store it in L. Then we will find the index of the next smaller element and will store it in R. After that, for every element, we will use this formula to calculate the subarrays in which it is minimum:

(R - i)*(i - L)

*  i is the index of the current element

Algorithm

  1. We will find the previous smaller element for every element of the array and store it in the array, and we will do the same thing for the next smaller element and store their indexes in another array.
  2. After that, we will calculate the answer for every element of the array using the above-stated formula, and then we will store the answer for every element in a different array.
  3. Now, we return the array.  

Code in C++

// Count subarrays for every array element in which they are the minimum
#include <bits/stdc++.h>
using namespace std;

// Function to required count subarrays and to store the answer for every element
vector<int> countingSubarraysForElements(vector<int> arr, int n)
{
    // for storing count of subarrays for every
    vector<int> ans(n);

    // for storing indexes of previous smaller element
    // if there is no previous smaller element then
    // we will store -1 in it's position
    vector<int> previous_smaller(n, -1);

    // for storing indexes of next smaller element
    // if there is no next smaller element then
    // we will store n in it's position
    vector<int> next_smaller(n, n);

    stack<int> st;
    for (int i = n - 1; i >= 0; i--)
    {
        while (!st.empty() && arr[st.top()] >= arr[i])
            st.pop();
        if (!st.empty())
            next_smaller[i] = st.top();

        else
            next_smaller[i] = n;
        st.push(i);
    }
    while (!st.empty())
        st.pop();

    for (int i = 0; i < n; i++)
    {
        while (!st.empty() && arr[st.top()] >= arr[i])
            st.pop();
        if (!st.empty())
            previous_smaller[i] = st.top();
        else
            previous_smaller[i] = -1;
        st.push(i);
    }

    for (int i = 0; i < n; i++)
    {
        // Right boundary
        int r = next_smaller[i] - i ;
        // Left boundary
        int l = i - previous_smaller[i];

        // Storing the answer of every element
        ans[i] = r * l;
    }

    return ans;
}

// Driver Code
int main()
{

    int N = 5;

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

    vector<int> ans = countingSubarraysForElements(arr, N);

    int n = ans.size() - 1;
    for (int i = 0; i < n; i++)
        cout << ans[i] << " ";

    cout << ans[n] << " ";

    return 0;
}

 

Input: 1 2 3 4 5
Output: 5 4 3 2 1

Complexity Analysis

Time Complexity: O(N)

Since we are finding the index of the previous smaller element and index of the next smaller element, they will take O(N) time, and after that, we are just using one loop to store the overall time complexity is O(N).

Space Complexity: O(N)

Since we use arrays to store the indexes of previous smaller elements and next smaller elements and store the answer, the overall space complexity is O(N).

Frequently asked questions

Q1. What is the previous smaller element problem?

Ans: The name suggests, the previous smaller element is a problem in which we have to find the previous smaller element of the current element and store it in an array.

This problem is implemented using stack, and its optimized approach runs in the same time complexity and space complexity.

Q2. What is space complexity?

Ans: The space complexity of an algorithm is the overall space taken by algorithm w.r.t input size.

Q3. What is the process of solving such problems?

Ans. To solve this type of problem, we first have to think of a brute force solution or a naive solution that is of the highest time and space complexity, and after that, we have to think about how we can optimize the solution and develop an intuition of better solution. 

The order we should follow is:

Brute -> Better -> Optimal  

Key takeaways

In this article, we discussed the problem count subarrays for every array element in which they are the minimum. We have discussed three approaches of this problem: one being brute force solution, the second being better solution, and the third being the optimal solution. 

We hope you gained some insight into this problem, and now it is your turn to practice this problem and code it out in your way. 

Don’t Stop here; try more problems and gain some more expertise in DSA!

  1. Next Greater Element
  2. Least Greater Element
  3. Next Smaller Element
  4. Kth Smallest Element

Until then, Keep Learning and Keep Coding.


Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think