1.
Introduction
2.
Problem Statement
2.1.
Input
2.2.
Output
2.3.
Explanation
3.
Brute Force Approach
3.1.
Algorithm
3.2.
Dry Run
3.3.
Implementation in C++
3.3.1.
Output
3.4.
Implementation in Java
3.4.1.
Output
3.5.
Time Complexity
3.6.
Space Complexity
4.
Efficient Approach
4.1.
Algorithm
4.2.
Dry Run
4.3.
Implementation in C++
4.3.1.
Output
4.4.
Implementation in Java
4.4.1.
Output
4.5.
Time Complexity
4.6.
Space Complexity
5.
Optimized Approach using Stack
5.1.
Algorithm
5.2.
Implementation in C++
5.2.1.
Output
5.3.
Implementation in Java
5.3.1.
Output
5.4.
Time Complexity
5.5.
Space Complexity
6.
6.1.
What is the best time complexity for calculating the next and previous smaller elements for each element in the array?
6.2.
What do you understand by space complexity?
6.3.
What are different operations that can be performed on a stack?
6.4.
What is an Array?
6.5.
How is the memory allocation performed for arrays in Java?
7.
Conclusion
Last Updated: Mar 27, 2024
Medium

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

Sahil Setia
0 upvote

## Introduction

An essential subject for programming interviews is the Array. You'll discover that arrays are used in numerous problems, from complex to easy ones. Since arrays are so standard, you will find them being used in any programming language you select.

This article will look at a problem involving subarrays and the minimum element in them. Array-based questions are the most popular in coding interviews and programming competitions.

In this blog, we will discuss the various approaches to solve the problem of counting subarrays for every array element in which they are the minimum. Before diving directly into the solution, let’s briefly discuss the problem statement.

## Problem Statement

Given an array of size N containing integers. The task is to count all the subarrays for every array element in which that element is minimum. Simply put, for the current element Awhere i is the index of the current element,  find all the subarrays which contain Aas the minimum element and this needs to be done for each element of the array.

Note: A subarray is an array that is contained within another array. It is a continuous portion of an array.

### Input

Total elements of the array(N) = 5

Array = [1, 4, 3, 5, 1]

5  1  4  1  5

### Explanation

• There are five sub-arrays in which arr[0] occurs as a minimum, and those are {1}, {1, 4}, {1, 4, 3}, {1, 4, 3, 5} and {1, 4, 3, 5, 1}.

• There is one subarray in which arr[1] occurs as a minimum, and that is {4}.

• There are four subarrays in which arr[2] occurs as a minimum, and that are {4, 3}, {3}, {4, 3, 5} and {3, 5}.

• There is one subarray in which arr[3] occurs as a minimum, and that is {5}.

• There are five sub-arrays in which arr[0] occurs as a minimum, and those are {1, 4, 3, 5, 1}, {4, 3, 5, 1}, {3, 5, 1}, {5, 1} and {1}.

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

## 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 Ai.

3. Traverse through the array once and for the current element, Achecks all the corresponding subarrays containing Ai.

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 Aand 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 Ai, store the value of ‘count’ in the ‘ans’ vector for each Ai, 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;
}``````

### 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+" ");
}
}
}``````

### Time Complexity

O(N3where ‘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(N3).

### 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 Ai and this subarray will be invalid for the current element Ai

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 Ai, 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 Ai where Ai is the current element.

3. Traverse through the array once, and for the current element, Acalculates the nearest smallest element on the left and right side of Ai.

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 Awill be
count = (right - i) * (i - left)

7. After performing this operation for each Ai, store the value of ‘count’ in the ‘ans’ vector for each Aand 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;
}``````

### 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+" ");
}
}
}``````

### Time Complexity

O(N2where ‘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(N2).

### 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 Ai we can calculate the valid subarray count for the current Athrough 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 Ai.

3. Traverse through the array once and for the current element, Ai calculates the nearest smallest element on the left and right side of Ai.

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 Ai.

5. Traverse through the array and for each element Ai, 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 Ai, 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 Ai the ‘count’ for current Awill be
count = (right - i) * (i - left)

8. After performing this operation for each Ai, store the value of ‘count’ in the ‘ans’ vector for each Ai, 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;
}``````

### 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+" ");
}
}
}``````

### 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

### 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.

And many more on our platform Coding Ninjas Studio.

Refer to our Guided Path to upskill yourself in DSACompetitive ProgrammingJavaScriptSystem 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 problemsinterview 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!

Live masterclass