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

Vibhor Bhatnagar
Last Updated: May 13, 2022

Introduction

This blog will discuss various approaches to solve this problem count of subarrays starting or ending at an index i such that arr[i] is maximum in a subarray. Before we deep dive into this problem, we should look at some examples that will help us understand the problem better. 

Some Examples

Input:

 {4, 1, 5, 2}

Output: 

{2, 1, 3, 1}

Explanation:

  • The subarray starting or ending at index 0 with maximum as arr[0] is {4}, {4, 1}. Therefore the count of subarrays is 2.
  • The subarray starting or ending at index 1 with maximum as arr[1] is {1}. Therefore the count of subarrays is 1.
  • The subarray starting or ending at index 2 with maximum as arr[2] is {5}, {5, 2}, {1, 5}, {4, 1, 5}. Therefore the count of subarrays is 4.
  • The subarray starting or ending at index 3 with maximum as arr[3] is {2}. Therefore the count of subarrays is 1.

Input:

{3, 2, 1}

Output:

{3, 1, 1}

Explanation:

  • The subarrays starting or ending at index 0 with maximum as arr[0] is {3}, {3, 2}, {3, 2, 1}. Therefore the count of subarrays is 3.
  • The subarray starting or ending at index 1 with maximum as arr[1] is {2}. Therefore the count of subarrays is 1.
  • The subarray starting or ending at index 2 with maximum as arr[2] is {1}. Therefore the count of subarrays is 1.

Brute Force Approach

The brute force approach to solving this problem count of subarrays starting or ending at an index i such that arr[i] is maximum in a subarray is to traverse in the right and left direction for every index i until the maximum of the subarray is equal to arr[i]. After that, calculate the answer for every index, store them in another array, and return it.

Algorithm

  1. To solve this problem, we will create a function called countOfSubarrays(), and it will take one argument: the initial array.
  2. In the function, we will use for loops to calculate the answer for every element.
  3. For every index i, we will travel in the right direction until the arr[i] is maximum, and we will do the same for the left direction. Now, we will store the answer for index i in another array.
  4. After the outer for loop is over, we will return the array in which we stored the answer.

Code in C++

// C++ code to Count of subarrays starting or ending at an index i such that arr[i] is maximum in a subarray

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

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

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

    for (int i = 0; i < n; i++)
    {
        // count is 1 because we are taking single sized subarray
        int count = 1;

        // traversing in right direction
        for (int j = i + 1; j < n; j++)
        {
            // checking if the current element is maximum or not
            if (a[i] > a[j])
            {
                count++;
            }
            // if not then break
            else
            {
                break;
            }
        }
        for (int j = i - 1; j >= 0; j--)
        {
            // checking if the current element is maximum or not
            if (a[i] > a[j])
            {
                count++;
            }
            // if not then break
            else
            {
                break;
            }
        }
        // storing the answer in the final array
        ans[i] = count;
    }
    return ans;
}

// Driver Code
int main()
{

    int n = 5;

    vector<int> a(n);

    a = {4, 8, 1, 3, 4};

    vector<int> ans = countOfSubarrays(a);

    for (auto x : ans)
    {
        cout << x << " ";
    }

    cout << endl;
}

 

Input and Output

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

 

Complexity Analysis

Time Complexity: O(N*N)

Since we are traveling in the right and the left direction for every element, the time complexity is O(N*N).

Space Complexity: O(1)

Since we are not using extra space to calculate answers for every index, the space complexity is O(1).

Optimized Approach

The above-stated approach can be optimized if we store the index of the next greater element and the previous greater element for every i in the array. Then, we will find the count of subarrays for every index.

Algorithm

  1. We will create two functions, one for storing the indexes of the next greater elements and another for storing the indexes of the previous greater element.
  2. We will initialize two arrays in the function named countOfSubarrays(). One would be nge[] and another would pge[].
  3. After that we will iterate over the given array and we will calculate the answer for every index  ans[i] = next_greater[i] - previous[i] - 1 .
  4. Now, we will return the array ans.

Code in C++

// C++ code to Count of subarrays starting or ending at an index i such that arr[i] is maximum in a subarray
#include <bits/stdc++.h>
using namespace std;

// to store the indexes of the next greater element
vector<int> nextGreaterElement(vector<int> a)
{
    int n = a.size();

    stack<int> s;

    vector<int> ans(n);

    // storing answer for last element
    ans[n - 1] = n;
    s.push(n - 1);

    for (int i = n - 2; i >= 0; i--)
    {
        // iterating untill the stack is empty
        // and the top element is less than the
        // current element
        while (!s.empty() && a[s.top()] < a[i])
        {
            s.pop();
        }
        // if stack is empty then we store n in the answer
        if (s.empty())
        {
            ans[i] = n;
        }
        // else we store the top element of the stack
        else
        {
            ans[i] = s.top();
        }
        s.push(i);
    }
    return ans;
}

// to store the indexes of the previous greater element
vector<int> previousGreaterElement(vector<int> a)
{
    int n = a.size();

    stack<int> s;

    vector<int> ans(n);

    // storing answer for first element
    ans[0] = -1;
    s.push(0);

    for (int i = 1; i < n; i++)
    {
        // iterating untill the stack is empty
        // and the top element is less than the
        // current element
        while (!s.empty() && a[s.top()] < a[i])
        {
            s.pop();
        }
        // if stack is empty then we store n in the answer
        if (s.empty())
        {
            ans[i] = -1;
        }
       // else we store the top element of the stack
        else
        {
            ans[i] = s.top();
        }
        s.push(i);
    }
    return ans;
}


// to find count of subarrays for every element
vector<int> countOfSubarrays(vector<int> a)
{
    int n = a.size();

    // function call to store indexes of next greater element
    vector<int> next_greater = nextGreaterElement(a);

    // function call to store indexed of previous greater element
    vector<int> previous_greater = previousGreaterElement(a);

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

    for (int i = 0; i < n; i++)
    {
        // storing the count of subarrays for every element
        ans[i] = next_greater[i] - previous_greater[i] - 1;
    }

    return ans;
}

// Driver Code
int main()
{

    int n = 5;

    vector<int> a(n);

    a = {6, 3, 1, 2, 9};

    vector<int> ans = countOfSubarrays(a);

    for (auto x: ans)
    {
        cout << x << " ";
    }

    cout << endl;
}

 

Input and Output

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

 

Complexity Analysis

Time Complexity: O(N)

Since we are not using nested for loops, the time complexity is O(N).

Space Complexity: O(N)

Since we are using extra space to calculate the next greater element and the previous greater element, therefore, the space complexity is O(N).

Frequently asked questions

Q1. What is the previous smaller element problem?

Ans. As 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 a stack, and its optimized approach runs simultaneously with complexity and space complexity.

 

Q2. What is a stack?

Ans. Stack is a linear data structure, and it is based on the principle of LIFO (Last In First Out).
 

Q3. What is a queue?

Ans. The queue is also a linear data structure, and it is based on the principle of FIFO (First in First Out)

Key takeaways:

In this article, we discussed the problem is the count of subarrays starting or ending at an index i such that arr[i] is maximum in a subarray. We have discussed two approaches for this problem: the brute force approach and the optimized approach. We hope you have gained a better understanding of the solution to this problem and, now it is your responsibility to solve the problem and try some new and different approaches to this problem. 

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