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 A_{i }where i is the index of the current element, _{ }find all the subarrays which contain A_{i }as 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]

Output

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

For the given array, call the ‘count_subarrays()’ function to count subarrays for each array element such that it is minimum in them.

Declare a ‘ans’ vector for storing the answer for each A_{i}.

Traverse through the array once and for the current element, A_{i }checks all the corresponding subarrays containing A_{i}.

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

Iterate through the possible starting index ‘start’ of the subarray that will contain A_{i }and iterate through the possible ending index ‘end’.

Declare a variable ‘min2’ for storing the minimum from range ‘i’ to ‘end’.

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

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;
}

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

Output

Time Complexity

O(N^{3}) 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^{3}).

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

For the given array, call the ‘count_subarrays()’ function to count subarrays for each array element such that it is minimum in them.

Declare an ‘ans’ vector for storing the answer for each A_{i} where A_{i} is the current element.

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

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.

Iterate through the left side and right side and find the nearest smallest element and if found, break the loop there.

After finding the ‘left’ and ‘right’ index, the ‘count’ for the current A_{i }will be count = (right - i) * (i - left)

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.

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.

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.

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.

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.

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

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

Output

Time Complexity

O(N^{2}) 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^{2}).

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

For the given array, call the ‘count_subarrays()’ function to count subarrays for each array element such that it is minimum in them.

Declare a ‘ans’ vector for storing the answer for each A_{i}.

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

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

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.

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.

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)

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;
}

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

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

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.

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!