Count of subarrays starting or ending at an Index i such that arr[i] is maximum in the subarray

Approach 1 - Brute Force

The main idea of this approach is to traverse in the right and left direction for every index i only until the maximum of the subarray is equal to arr[i]. To calculate the answer for every index, We count these subarrays to the left and right of that index.

Let’s see the algorithm step-by-step:

Algorithm

1. We will use a for loop to iterate through the given array and calculate the answer for every index.
2. For every index i:
   1. We assign an initial count of valid subarrays as one because of the subarray that contains only one element, arr[i] itself.
   2. We count the valid subarrays to the right of index i by traversing the array in the right direction until we encounter an element arr[j] greater than arr[i].
   3. We count the valid subarrays to the left of index i by traversing the array in the left direction until we encounter an element arr[j] greater than arr[i].
3. We store the answer calculated for each index in a separate array.

Dry Run

Let us look at the valid subarrays to the left of index 4 (0-based indexing) for the array {4, 8, 1, 3, 4}.

Code

// C++ code to count subarrays starting or ending at an index i such that arr[i] is maximum in a subarray - Approach 1

#include <bits/stdc++.h>
using namespace std;

// Function to count the number of subarrays for every index
vector<int> countOfSubarrays(vector<int> &arr) {
   int n = int(arr.size());

   // vector to store the answer
   vector<int> ans(n);

   for (int i = 0; i < n; ++i) {
       // count is one because of subarray with one element, i.e. {arr[i]}
       int count = 1;

       // For counting, subarrays that start at i and end at j (j > i)
       for (int j = i + 1; j < n; ++j) {
           // we break if we have arr[j] in subarray which is greater than arr[i]
           if (arr[j] > arr[i]) break;
           // increment number of subarrays by one for the subarray {arr[i], arr[i + 1], ..., arr[j]}
           ++count;
       }

       // For counting, subarrays that start at j and end at i (j < i)
       for (int j = i - 1; j >= 0; --j) {
           // we break if we have arr[j] in subarray which is greater than arr[i]
           if (arr[j] > arr[i]) break;
           // increment number of subarrays by one for the subarray {arr[j], arr[j + 1], ..., arr[i]}
           ++count;
       }

       // Storing the answer in the final array
       ans[i] = count;
   }

   return ans;
}

// Driver code
int main() {
   vector<int> arr = {4, 8, 1, 3, 4};

   // Calling the Function which calculates the answer vector
   vector<int> ans = countOfSubarrays(arr);
   for (auto &x : ans) {
       cout << x << ' ';
   }
   cout << endl;

   return 0;
}

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

Run Code

Output:

1 5 1 2 3

Complexity Analysis

Time Complexity 

The algorithm’s time complexity is O(n^2) where n is the size of input array arr[] because we traverse the array, and for each index i, we travel in the left and right direction, which may take at most O(n) time.

Space Complexity 

The algorithm’s space complexity is O(1), as we are not using any extra space.

Approach 2 - Using monotonic stack

We can optimise the previous approach if we can quickly get the index of the next greater element and the previous greater element for every i in the range [0, n). For an index i, if the index of the next greater element is j, then all elements in the range [i,j-1] are less than or equal to arr[i]. Thus there are (j-1)-i valid subarrays to the right of index i. Similarly, suppose the index of the previous greater element is k. In that case, there are i-(k+1) valid subarrays to the left of index i. If we also count the subarray containing only arr[i], we have a total of 1 + ((j-1)-i) + (i-(k+1)) valid subarrays for the index i, which directly gives us the formula j-k-1.

We can find the indexes of the previous and next greater elements using a monotonic stack. A monotonic stack is a stack whose elements are monotonically increasing or decreasing. To find the indexes of the next and previous greater elements, we will use a monotonic decreasing stack, which contains elements in decreasing order from the bottom to the top of the stack. We get a monotonic decreasing stack if we pop all smaller elements from the stack before pushing a new element.

Let’s see the algorithm step-by-step:

Algorithm

1. We will calculate and store the indexes of the next greater and the previous greater elements. We can compute the indexes of the next greater elements as follows:
   1. We iterate over the array from right to left to keep all the elements after index i that are larger than arr[i] in the stack.
   2. Before pushing an index into the stack, all indexes are popped from the stack until the array is not empty and the element corresponding to the stack’s top is smaller than the element to be inserted.
   3. If the stack is not empty, then the top of the stack gives the index of the next greater element. 
      Otherwise, we can assign n as the index of the next greater element. Since n is the size of the array a[], it is guaranteed to be a value that is outside the valid index range of a[], so it can be used as a special marker to represent that there is no next greater element for the current element a[i].
   4. Then, we push the current index into the stack.
      
      Similarly, We can find the indexes of previous greater elements if we iterate over the array from left to right.
2. Now, we can calculate the answer for any index i, ans[i] = nextGreater[i] - prevGreater[i] - 1.

Dry Run

Let us visualise how we find the indexes of the next greater elements for all the indexes.

We find the indexes of the previous greater elements similarly by just iterating from left to right. Using these arrays, we can calculate the answer for each index. For example, for index 3:

The count of valid sub-arrays for index i = j - k - 1 = 4 - 1 - 1 = 2. The two valid sub-arrays are {3}, {1, 3}.

Code

// C++ code to count subarrays starting or ending at an index i such that arr[i] is maximum in a subarray - Approach 2

#include <bits/stdc++.h>
using namespace std;

// Function, which creates a vector that stores indexes of the next greater elements
vector<int> nextGreaterElement(vector<int> &a) {
   int n = int(a.size());
   vector<int> nextGreater(n);
   stack<int> st;
   for (int i = n - 1; i >= 0; --i) {
       // Remove previously inserted indexes of elements from the stack that are smaller or equal to a[i]
       while (!st.empty() && a[st.top()] <= a[i]) {
           st.pop();
       }
       /*
           The element at the top of the stack is the next greater element (if it exists)
           Otherwise, assign n as the next greater index.
       */
       nextGreater[i] = st.empty() ? n : st.top();
       // Push the current index into the stack
       st.push(i);
   }
   return nextGreater;
}

// Function, which creates a vector that stores indexes of the previous greater elements
vector<int> previousGreaterElement(vector<int> &a) {
   int n = int(a.size());
   vector<int> prevGreater(n);
   stack<int> st;
   for (int i = 0; i < n; ++i) {
       // Remove previously inserted indexes of elements from the stack that are smaller or equal to a[i]
       while (!st.empty() && a[st.top()] <= a[i]) {
           st.pop();
       }
       /*
           The element at the top of the stack is the previous greater element (if it exists)
           Otherwise, assign -1 as the previous greater index.
       */
       prevGreater[i] = st.empty() ? -1 : st.top();
       // Push the current index into the stack
       st.push(i);
   }
   return prevGreater;
}

// Function to count the number of subarrays for every index
vector<int> countOfSubarrays(vector<int> &a) {
   int n = int(a.size());

   // Function call to store indexes of the next greater element
   vector<int> nextGreater = nextGreaterElement(a);

   // Function call to store indexes of the previous greater element
   vector<int> prevGreater = previousGreaterElement(a);

   vector<int> ans(n);
   for (int i = 0; i < n; ++i) {
       // Calculating the answer for each index using the derived formula
       ans[i] = nextGreater[i] - prevGreater[i] - 1;
   }
   return ans;
}

// Driver code
int main() {
   vector<int> a = {4, 8, 1, 3, 4};
   // vector<int> a = {6, 3, 1, 2, 9};

   // Calling the function which calculates the answer vector
   vector<int> ans = countOfSubarrays(a);
   for (auto &x : ans) {
       cout << x << ' ';
   }
   cout << endl;

   return 0;
}

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

Run Code

Output:

1 5 1 2 3

Complexity Analysis

Time Complexity 

The algorithm’s time complexity is O(n), where n is the size of the input array arr[]. We calculate the indexes of the previous and next greater elements in O(n) time and use it to calculate the answer for index i in O(1) time while traversing the array.

Space Complexity 

The algorithm’s space complexity is O(n), as we use extra space to calculate (the monotonic stack) and store the indexes of the previous and next greater elements.

Frequently Asked Questions

What is a subarray?

A subarray is a continuous section or part of an array.

What is a stack?

A stack is a linear data structure that follows the LIFO principle (Last In, First Out).

What is a queue?

A queue is a linear data structure that follows the FIFO principle (First In, First Out).

What is a monotonic stack?

A monotonic stack is a stack whose elements always increase or decrease monotonically.

What is the time and space complexity for finding the next greater element?

The time complexity to find the next greater element for all indexes using a monotonic stack is O(n) because only n elements are pushed into or popped from the stack.

The space complexity is also O(n) because we use a stack which stores at most n elements.

Conclusion

This article discussed how to count subarrays starting or ending at index i such that arr[i] is maximum in the subarray. Along with the solutions, we also discussed their time and space complexity.

Recommended Problems -

• Next Greater Element
• Next Smaller Element

If you want to learn more about arrays and want to practice some questions requiring you to take your basic knowledge on these topics a notch higher, then you can visit our Guided Path for arrays on Coding Ninjas Studio. To be more confident in data structures and algorithms, try out our DS and Algo Courses. Until then, All the best for your future endeavours, and Keep Coding.