Count Subarrays for every Array Element in Which they are the Minimum

Brute Force Approach

The brute force or naive approach simply checks for each array element how many valid subarrays there are such that the current array element is minimum in that subarray. For this to perform, simply iterate through the array once and generate all possible subarrays, including the current array element, evaluate the minimum along that subarray, and perform the check condition. 

Let’s take a look at the algorithm part of this approach.

Algorithm

1. For the given array, call the ‘count_subarrays()’ function to count subarrays for each array element such that it is minimum in them.
    
2. Declare a ‘ans’ vector for storing the answer for each A_i.
    
3. Traverse through the array once and for the current element, A_i checks all the corresponding subarrays containing A_i.
    
4. Declare a variable ‘count’ for storing the count of subarrays for the current element and a variable ‘min1’ for storing the minimum from range to ‘start’ to ‘i’.
    
5. Iterate through the possible starting index ‘start’ of the subarray that will contain A_i and iterate through the possible ending index ‘end’.
    
6. Declare a variable ‘min2’ for storing the minimum from range ‘i’ to ‘end’.
    
7. Extract the overall minimum of range [start, end] and store it in ‘overall_min’ and check if it equals Ai. If equal, increment the ‘count’.
    
8. After performing this operation for each A_i, store the value of ‘count’ in the ‘ans’ vector for each A_i, return the ‘ans’ vector, and display it as the final output.

Dry Run

Let’s look at the visualization of the approach mentioned above.

• The given array looks like this

For array element arr[0] the valid subarrays are:

• start = 0, end = 0, minimum element(start to end) = 1

• start = 0, end = 1, minimum element(start to end) = 1

• start = 0, end = 2, minimum element(start to end) = 1

• start = 0, end = 3, minimum element(start to end) = 1

• start = 0, end = 4, minimum element(start to end) = 1

Hence, for the array[0] element there are five subarrays in which array[0] is the minimum element.

Similarly, we will calculate for all elements from i = 1 to i = 4.

For the array[1] element, there will be one subarray in which array[1] is the minimum element.

For the array[2] element, there will be four subarrays in which array[2] is the minimum element.

For the array[3] element, there will be one subarray in which array[3] is the minimum element.

There will be five subarrays for the array[4] element in which array[4] is the minimum element.

Hence, the output array is [5, 1, 4, 1, 5].

Implementation in C++

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

// Function which calculates the total subarrays for each element
vector <int> count_subarrays(vector <int>&arr, int n){
    
    // For storing count for each array element
    vector <int> ans(n);
    
    // Outer loop for current element
    for(int i=0;i<n;i++){
        
        // For storing the count for current element
        int count = 0;
        
        // For storing the minimum from start to i
        int min1 = INT_MAX;
        
        // Iterating over starting index
        for(int start=i;start>=0;start--){
            
            // Taking minimum
            min1 = min(min1, arr[start]);
            
            // For storing the minimum from i to end
            int min2 = INT_MAX;
            
            // Iterating over ending index
            for(int end=i;end<n;end++){
                
                // Taking minimum
                min2 = min(min2, arr[end]);
                
                // Extracting the minimum of range start to end
                int overall_min = min(min1, min2);
                
                // Check that minimum is equal to current array element or not
                if(overall_min == arr[i]){
                    ++count;
                }
            }
        }
        
        ans[i] = count;
    }
    
    // Returning the 'ans' vector
    return ans;
}

int main(){
    
    // Size of the array
    int N = 5;
    
    // Elements of the array
    vector <int> arr(N);
    arr[0] = 1;
    arr[1] = 4;
    arr[2] = 3;
    arr[3] = 5;
    arr[4] = 1;
    
    // Calling the function
    vector <int> ans = count_subarrays(arr,N);
    
    // Displaying the result
    for(auto i:ans){
        cout<<i<<" ";
    }
    
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Implementation in Java

public class MyClass {
    
    // Function which calculates the total subarrays for each element
    static int[] count_subarrays(int arr[], int n){
        
        // For storing the count for each array element
        int ans[] = new int [n];
        
        // Outer loop for the current element
        for(int i=0;i<n;i++){
            
            // For storing the count for the current element
            int count = 0;
            
            // For storing the minimum from start to i
            int min1 = Integer.MAX_VALUE;
            
            // Iterating over starting index
            for(int start=i;start>=0;start--){
                
                // Taking minimum
                min1 = Math.min(min1, arr[start]);
                
                // For storing the minimum from i to end
                int min2 = Integer.MAX_VALUE;
                
                // Iterating over ending index
                for(int end=i; end<n;end++){
                    
                    // Taking minimum
                    min2 = Math.min(min2, arr[end]);
                    
                    // Extracting the minimum of range start to end
                    int overall_min = Math.min(min1, min2);
                    
                    // Check that minimum is equal to a current array element or not
                    if(overall_min == arr[i]){
                        ++count;
                    }
                }
            }
            
            ans[i] = count;
        }
        
        // Returning the 'ans' array
        return ans;
    }
    
    public static void main(String args[]){
        
        // Size of the array
        int N = 5;
        
        // Elements of the array
        int arr[] = new int[N];
        arr[0] = 1;
        arr[1] = 4;
        arr[2] = 3;
        arr[3] = 5;
        arr[4] = 1;
        
        // Calling the function
        int ans[] = count_subarrays(arr,N);
        
        // Displaying the result
        for(int i:ans){
            System.out.print(i+" ");
        }
    }
}

You can also try this code with Online Java Compiler

Run Code

Output

Time Complexity

O(N³) where ‘N’ is the total number of elements in the given array.

Explanation: We used three nested loops for ‘i’, ‘start,’ and ‘end’; each loop will go up to at max N iterations. We used the minimum function inside the nested loop and performed the check condition, which takes O(1) time. Hence, the time complexity of O(N³).

Space Complexity

O(N), where ‘N’ is the total number of elements in the given array.

Explanation: We used an array ‘ans’ to store the results for each array element, giving a space complexity of O(N). We didn’t use any extra space, so if we ignore these storing results array, the space complexity is O(1).

Efficient Approach

Before diving into the solution to this approach, let’s take a closer look at the brute force approach. If we observe closely, we can see that the overall minimum is affected when we get a smaller element on the left side of some index ‘i’ or a smaller element on the right side of some index ‘i’. In any case, the overall minimum will be smaller than the current element A_i and this subarray will be invalid for the current element A_i. 

Now, we have a clear direction to think that we just need to find the nearest smallest element on the left and right sides. Let’s suppose for the current element A_i, the next smallest element on the left side is on index ‘left’, and the next smallest element on the right side is on index ‘right.’ Now, simply we can see that the total number of valid subarrays will be: 

Subarray Count = (i - left) * (right - i) 

This is because the subarray can be extended by (i - left) on the left side and (right - i) on the right side. Now, let’s look at the algorithmic part of this approach.

Algorithm

1. For the given array, call the ‘count_subarrays()’ function to count subarrays for each array element such that it is minimum in them.
    
2. Declare an ‘ans’ vector for storing the answer for each A_i where A_i is the current element.
    
3. Traverse through the array once, and for the current element, A_i calculates the nearest smallest element on the left and right side of A_i.
    
4. Declare two variables ‘left’ with value ‘-1’ and ‘right’ with value ‘n’ for storing the nearest smallest element on the left and right side respectively.
    
5. Iterate through the left side and right side and find the nearest smallest element and if found, break the loop there.
    
6. After finding the ‘left’ and ‘right’ index, the ‘count’ for the current A_i will be
                                            count = (right - i) * (i - left)
    
7. After performing this operation for each A_i, store the value of ‘count’ in the ‘ans’ vector for each A_i and return the ‘ans’ vector and display it as the final output.

Dry Run

In this approach, we will find the previous smallest element, ‘left’, and the next greater element, ‘right’, by simply iterating over the left and right portions of the array.
 

Let’s take a look at the visualization of the approach mentioned above.

• For array element arr[0], the previous smaller element ‘left’ and the next greater element ‘right’ does not exist. Hence, the ‘left’ pointer will be equal to -1, and the right will be equal to n = 5, i.e., right = 5.

Subarray count  = (right - i) * (i - left) = (5 - 0) * (0 - (-1)) = 5

• For array element arr[1], the corresponding previous smaller element ‘left’, and the next greater element ‘right’ exists. As we can see from the figure below, the ‘left’ pointer will be equal to 0, and the right will be equal to 2.

Subarray count  = (right - i) * (i- left) = (2 - 1) * (1 - 0) = 1

• For array element arr[2], the corresponding previous smaller element ‘left,’ and the next greater element ‘right’ exists. As we can see from the figure below, the ‘left’ pointer will be equal to 0, and the right will be equal to 4.

Subarray count  = (right - i) * (i - left) = (4 - 2) * (2 - 0) = 4

• For array element arr[3], the corresponding previous smaller element ‘left,’ and next greater element ‘right’ exists. As we can see from the figure below, the ‘left’ pointer will be equal to 2, and the right will be equal to 4.

Subarray count  = (right - i) * (i - left) = (4 - 3) * (3 - 2) = 1

• For array element arr[4], the corresponding previous smaller element ‘left’ and next greater element ‘right’ does not exist. Hence, the ‘left’ pointer will be equal to -1, and the right will be equal to N = 5.

Subarray count  = (right - i) * (i - left) = (5 - 4) * (4 - (-1)) = 5

Hence, the output array is [5, 1, 4, 1, 5].

Implementation in C++

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

// Function which calculates the total subarrays for each element
vector <int> count_subarrays(vector <int>&arr, int n){
    
    // For storing count for each array element
    vector <int> ans(n);
    
    // Outer loop for current element
    for(int i=0;i<n;i++){
        
        // Left and right index for storing nearest smallest elements
        int left = -1;
        int right = n;
        
        // Traversing through the left side
        for(int j=i;j>=0;j--){
            
            if(arr[j] < arr[i]){
                left = j;
                break;
            }
        }
        
        // Traversing through the right side
        for(int j=i;j<n;j++){
            
            if(arr[j] < arr[i]){
                right = j;
                break;
            }
        }
        
        // Calculating the subarray count
        int count = (right -i) * (i - left);
        ans[i] = count;
    }
    
    // Returning the 'ans' vector
    return ans;
}

int main(){
    
    // Size of the array
    int N = 5;
    
    // Elements of the array
    vector <int> arr(N);
    arr[0] = 1;
    arr[1] = 4;
    arr[2] = 3;
    arr[3] = 5;
    arr[4] = 1;
    
    // Calling the function
    vector <int> ans = count_subarrays(arr,N);
    
    // Displaying the result
    for(auto i:ans){
        cout<<i<<" ";
    }
    
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Implementation in Java

public class MyClass {
    
    // Function which calculates the total subarrays for each element
    static int[] count_subarrays(int arr[], int n){
        
        // For storing the count for each array element
        int ans[] = new int [n];
        
        // Outer loop for the current element
        for(int i=0;i<n;i++){
            
            // Left and right index for storing nearest smallest elements
            int left = -1;
            int right = n;
            
            // Traversing through the left side
            for(int j=i;j>=0;j--){
                
                if(arr[j] < arr[i]){
                    left = j;
                    break;
                }
            }
            
            // Traversing through the right side
            for(int j=i;j<n;j++){
                
                if(arr[j] < arr[i]){
                    right = j;
                    break;
                }
            }
            
            // Calculating the subarray count
            int count = (right -i) * (i - left);
            ans[i] = count;
        }
        
        // Returning the 'ans' array
        return ans;
    }
    public static void main(String args[]){
        
        // Size of the array
        int N = 5;
        
        // Elements of the array
        int arr[] = new int[N];
        arr[0] = 1;
        arr[1] = 4;
        arr[2] = 3;
        arr[3] = 5;
        arr[4] = 1;
        
        // Calling the function
        int ans[] = count_subarrays(arr,N);
        
        // Displaying the result
        for(int i:ans){
            System.out.print(i+" ");
        }
    }
}

You can also try this code with Online Java Compiler

Run Code

Output

Time Complexity

O(N²) where ‘N’ is the total number of elements in the given array.

Explanation: We used two nested loops for ‘i’ and ‘left & right’; each loop will go up to at max N iterations. We used the minimum function inside the nested loop and performed the check condition, which takes O(1) time. Hence, the time complexity of O(N²).

Space Complexity

O(N), where ‘N’ is the total number of elements in the given array.

Explanation: We used an array ‘ans’ to store the results for each array element, giving a space complexity of O(N). We didn’t use any extra space, so if we ignore these storing results array, the space complexity is O(1).

Optimized Approach using Stack

In the previous approach, we saw how after calculating the nearest smallest elements on the ‘left’ and ‘right’ side of the A_i we can calculate the valid subarray count for the current A_i through the formula:

Subarray Count = (i - left) * (right - i) 

For calculating the left and right nearest smallest element, we took an O(N) time in the previous approach. 

In this approach, we will calculate the left and right nearest smallest element in O(1) time using the stack approach. We recommend you go through this article before proceeding further.

Using stack, the calculation of the ‘left’ and ‘right’ index can be done in O(1) time by pre-calculating them using stack. Then simply, using the formula stated above, the required count can be obtained. Let’s take a look at the algorithm of this approach.

Algorithm

1. For the given array, call the ‘count_subarrays()’ function to count subarrays for each array element such that it is minimum in them.
    
2. Declare a ‘ans’ vector for storing the answer for each A_i.
    
3. Traverse through the array once and for the current element, A_i calculates the nearest smallest element on the left and right side of A_i.
    
4. Declare a stack ‘s’ which will be used for maintaining a monotonic stack for calculating the left and right nearest smallest elements for each A_i.
    
5. Traverse through the array and for each element A_i, pop all elements from the stack which are greater than or equal to the current element. If the stack is not empty, the top element will be the previous smaller element, and it will be stored in the ‘left’ array. Finally, push the current element index.
    
6. Traverse through the array from the end and for each element A_i, pop all elements from the stack which are greater than or equal to the current element. If the stack is not empty, the top element will be the next smaller element, and it will be stored in the ‘right’ array. Finally, push the current element index.
    
7. After finding the ‘left’ and ‘right’ index for each element A_i the ‘count’ for current A_i will be 
                                     count = (right - i) * (i - left)
    
8. After performing this operation for each A_i, store the value of ‘count’ in the ‘ans’ vector for each A_i, return the ‘ans’ vector, and display it as the final output.

Implementation in C++

#include <iostream>
#include <vector>
#include <climits>
#include <stack>
using namespace std;

// Function which calculates the total subarrays for each element
vector <int> count_subarrays(vector <int>& arr, int n){
    
    // For storing count for each array element
    vector <int> ans(n);
    
    /*
        For storing the left and right smaller elements of each i
        If no element is smaller in left to it than taking -1.
        If no element is smaller in right to it taking n.
    */
    vector <int> left(n,-1), right(n,n);
    
    // Monotonic stack
    stack<int> s;
    
    // Traversing through the array and calculating the previous smaller element
    for(int i=0;i<n;i++){
        
        // Popping elements > = arr[i]
        while(!s.empty() && arr[s.top()] >= arr[i]){
            s.pop();
        }
        
        // If not empty
        if(!s.empty()){
            
            left[i] = s.top();
        }
        
        // Pushing the current element
        s.push(i);
    }
    
    // Clearing the stack
    while(!s.empty()){
        s.pop();
    }
    
    // Traversing through the array and calculating the next smaller element
    for(int i=n-1;i>=0;i--){
        
        // Popping elements > = arr[i]
        while(!s.empty() && arr[s.top()] >= arr[i]){
            s.pop();
        }
        
        // If not empty
        if(!s.empty()){
            
            right[i] = s.top();
        }
        
        // Pushing the current element
        s.push(i);
    }
    
    // Outer loop for current element
    for(int i=0;i<n;i++){
        
        // Calculating the subarray count
        int count = (right[i] -i) * (i - left[i]);
        ans[i] = count;
    }
    
    // Returning the 'ans' vector
    return ans;
}

int main(){
    
    // Size of the array
    int N = 5;
    
    // Elements of the array
    vector <int> arr(N);
    arr[0] = 1;
    arr[1] = 4;
    arr[2] = 3;
    arr[3] = 5;
    arr[4] = 1;
    
    // Calling the function
    vector <int> ans = count_subarrays(arr,N);
    
    // Displaying the result
    for(auto i:ans){
        cout<<i<<" ";
    }
    
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Implementation in Java

import java.io.*;
import java.util.*;
public class MyClass {
    
    // Function which calculates the total subarrays for each element
    static int[] count_subarrays(int arr[], int n){
        
        // For storing count for each array element
        int ans[] = new int [n];
        
        /*
            For storing the left and right smaller elements of each i
            If no element is smaller in left to it than taking -1.
            If no element is smaller in right to it taking n.
        */
        int left[] = new int [n];
        int right[] = new int [n];
        for(int i=0;i<n;i++){
            left[i] = -1;
            right[i] = n;
        }
        
        // Monotonic stack
        Stack<Integer> s = new Stack<Integer>();
        
        // Traversing through the array and calculating the previous smaller element
        for(int i=0;i<n;i++){
            
            // Popping elements > = arr[i]
            while(!s.empty() && arr[s.peek()] >= arr[i]){
                s.pop();
            }
            
            // If not empty
            if(!s.empty()){
                
                left[i] = s.peek();
            }
            
            // Pushing the current element
            s.push(i);
        }
        
        // Clearing the stack
        while(!s.empty()){
            s.pop();
        }
        
        // Traversing through the array and calculating the next smaller element
        for(int i=n-1;i>=0;i--){
            
            // Popping elements > = arr[i]
            while(!s.empty() && arr[s.peek()] >= arr[i]){
                s.pop();
            }
            
            // If not empty
            if(!s.empty()){
                
                right[i] = s.peek();
            }
            
            // Pushing the current element
            s.push(i);
        }
        
        // Outer loop for current element
        for(int i=0;i<n;i++){
            
            // Calculating the subarray count
            int count = (right[i] -i) * (i - left[i]);
            ans[i] = count;
        }
        
        // Returning the 'ans' array
        return ans;
    }
    public static void main(String args[]){
        
        // Size of the array
        int N = 5;
        
        // Elements of the array
        int arr[] = new int[N];
        arr[0] = 1;
        arr[1] = 4;
        arr[2] = 3;
        arr[3] = 5;
        arr[4] = 1;
        
        // Calling the function
        int ans[] = count_subarrays(arr,N);
        
        // Displaying the result
        for(int i:ans){
            System.out.print(i+" ");
        }
    }
}

You can also try this code with Online Java Compiler

Run Code

Output

Time Complexity

O(N) where ‘N’ is the total number of elements in the given array.

Explanation: We used a single traversal for iterating through the array, and calculating the ‘left’ and ‘right’ array takes O(N) time. Inside the loop, we used the minimum function inside the loop and performed the check condition, which takes O(1) time. Hence, the time complexity of O(N).

Space Complexity

O(N), where ‘N’ is the total number of elements in the given array.

Explanation: We used a monotonic stack ‘ans’ to calculate the next and previous smaller elements for each array element which gives a space complexity of O(N).

Must Read Array of Objects in Java

Frequently Asked Questions

What is the best time complexity for calculating the next and previous smaller elements for each element in the array?

The best time complexity for finding the next and previous smaller elements for each element in the array is O(N), where ‘N’ is the number of elements in the array.

What do you understand by space complexity?

The space complexity of a program can be defined as the total space taken in the memory by the algorithm concerning its input.

What are different operations that can be performed on a stack?

The various operations that can be performed on a stack are push(), pop(), empty(), and top().

What is an Array?

An array is a data structure that sequentially stores an element of the same data type. In C/C++ or any other programming language, an array is a collection of similar data items. The data items are always stored in an array at contiguous memory locations.

How is the memory allocation performed for arrays in Java?

Since arrays are objects in Java, their memory is always allocated to the heap.

Conclusion

This article discusses the problem of counting the number of subarrays for each array element such that is minimum in that subarray. In detail, we have covered three solution approaches to solving the problem, and we saw the implementation of the solution approach in C++ and Java. 

We also discussed the time complexity and space complexity of each approach. We would suggest you solve them to gain more confidence in these kinds of problems. These questions are asked during various coding contests as well as placement tests and thus are very important. 

We hope this blog has helped you enhance your knowledge of the array of problems and the breadth-first search approach. If you want to improve more, then check out our blogs.

• Next Greater and Smaller Element for Every Element in an Array
• Trapping Rainwater
• Maximum Equal Sum in Three Stacks
   

And many more on our platform Coding Ninjas Studio.

Refer to our Guided Path to upskill yourself in DSA, Competitive Programming, JavaScript, System Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio!

But suppose you have just started your learning process and are looking for questions from tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problems, interview experiences, and interview bundles for placement preparations.

However, you may consider our paid courses to give your career an edge over others!

Happy Learning, Ninjas!