Maximum range length such that A[i] is maximum in the given range for all i from [1, N]

Vibhor Bhatnagar
Last Updated: May 13, 2022

Introduction  

This blog will discuss the various approaches to solve the problem of maximum range length such that a[i] is maximum in the given range for all i from [1, N].

There are many approaches to solving this problem. Still, before we deep dive into the solution of this problem, we should look at some examples to understand the problem better before discussing the solution.

Some Examples

Input:

 arr[] = {1,4,3,2}

Output: 

{0,0}, {0,3}, {2,3}, {3,3}

Explanation:

  •  arr[0] i.e is maximum in the range {0,0} 
  •  arr[1] i.e is maximum in the range {0,3}
  •  arr[2] i.e is maximum in the range {2,3}
  •  arr[3] i.e is maximum in the range {3,3}

Input:

arr[] = {2,0,1}

Output:

{0,2}, {1,1}, {1,2}

Explanation:

  •  arr[0] i.e is maximum in the range {0,2} 
  •  arr[1] i.e is maximum in the range {1,1}
  •  arr[2] i.e is maximum in the range {1,2}

Brute Force Approach

The brute force approach for this problem of maximum range length such that A[i] is maximum in the given range for all i from [1, N] is to traverse in both left and right directions for every element and find the respective boundaries l and r.

While traversing in the left direction, if at any moment a[l] becomes greater than a[i] (a[i] is the current element), then terminate the loop, and the left boundary becomes l. The same is for right also while traversing in the right direction if at any moment a[r] becomes greater than a[i], terminate the loop and the right boundary becomes r.

Algorithm

  1. Create a function findMaxRange() that takes one parameter, the array given to us, and returns a vector of pairs. 
  2. In the function, we will traverse two nested for loops, and for every element, we will find its next greater element by traveling in the inner for loop. When we find it, we break from the loop and store the index of the next greater element in a variable named R.
  3. We will do the same for the previous greater element, and when we find it, we will break from the loop and store the index of the previous greater element in a variable named L.
  4.  After that, we will store the [L, R] pair for every element in a vector of pairs, and after the loop is over, we will return the vector from the function.

Code in C++

// C++ code for Maximum range length such that A[i] is maximum in the given range for all i from [1, N]
#include <bits/stdc++.h>
using namespace std;

// function to find max range for every element
vector<pair<int, int>> findMaxRange(vector<int> a)
{
    int n = a.size();

    // for storing the answer for every pair
    vector<pair<int, int>> ans;
    for (int i = 0; i < n; i++)
    {
        int left = i, right = i;
        // for left boundary
        for (int j = i - 1; j >= 0; j--)
        {
            // if a[j] > a[i] then we have
            // found our left boundary
            left = j;
            if (a[j] > a[i])
            {
                left = j + 1;
                break;
            }
        }
        // for right boundary
        for (int j = i + 1; j < n; j++)
        {
            // if a[j] > a[i] then we have
            // found our right boundary
            right = j;
            if (a[j] > a[i])
            {
                right = j - 1;
                break;
            }
        }
        // storing the answer for every pair
        ans.push_back(make_pair(left, right));
    }
    return ans;
}

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

    vector<pair<int, int>> ans = findMaxRange(arr);

    for (int i = 0; i < ans.size(); i++)
    {
        cout << "{"<< ans[i].first << "," << ans[i].second <<"} ";
    }
}

 

Input and Output:

Input: 1 2 3 2 5
Output: {0,0} {0,1} {0,3} {3,3} {0,4}

Complexity Analysis

Time Complexity: O(N*N)

Since we are using two nested loops and for every element, we are traversing right to get the right boundary of that element. We are also traveling left to get to the left boundary of the element. Therefore, the overall time complexity is N*N.

Space Complexity: O(N)

Since we are using any extra array to store the answer, the space complexity of the above solution is O(N).

Optimized Approach

In the above-discussed approach, the complexity is very high, and therefore, we need to develop a more efficient method.

So in this approach, we will make one array that will store the index of the next greater element, and we will make another array that will keep the index of the previous greater element. After that, we will store the right boundary index from the next greater element array and the left boundary index from the previous greater element array.

Algorithm

  1. We will maintain a stack of pairs that will contain all the elements in a non-increasing fashion.
  2. We will make two arrays of pairs, one for the left boundary and another for the right boundary. 
  3. We will calculate the left boundaries of elements using the array made by previous greater elements. Also, we will calculate the right boundaries using the array made by the next greater elements.
  4. Now, we just have to push the left and right boundary of every element present in the array into our array of pairs, and then we will return it.

Code in C++

// C++ code for Maximum range length such that A[i] is maximum in the given range for all i from [1, N]
#include <bits/stdc++.h>
using namespace std;

// function to find the range for every element of the array and
//  then returning the answer in the form of a vector of pairs
vector<pair<int,int>> findMaxRange(vector<int> A, int n)
{
    // to store the final answer for every element
    // for storing left and right boundary
    // in the form of an answer
    vector<pair<int,int>> ans;


    // to store left and right boundary, respectively
    vector<int> left(n), right(n);

    // pair of the stack to store value of the element
    // and the index of the element
    stack<pair<int, int> > s;
    s.push({ INT_MAX, -1 });

    // traversing the array to find
    // the left boundary for every element
    for (int i = 0; i < n; i++) {
        // if the top of stack is less than current
        // element then pop it
        while (s.top().first < A[i])
            s.pop();

        // modifying the left boundary of the element
        left[i] = s.top().second;
        s.push({ A[i], i });
    }
    // clearing the stack
    while (!s.empty())
        s.pop();

    s.push(make_pair(INT_MAX, n));

    // traversing the array to find
    // the right boundary of every element
    for (int i = n - 1; i >= 0; i--) {
        // if the top of the stack is less than current
        // element then pop it
        while (s.top().first < A[i])
            s.pop();

        // modifying the right boundary of the element
        right[i] = s.top().second;
        s.push({ A[i], i });
    }

    // storing the answer
    for (int i = 0; i < n; i++) {
        ans.push_back({left[i]+1,right[i]-1});
    }
    return ans;
}

// Driver Code
int main()
{
  
    vector<int> arr{ 9, 1, 9, 10, 2, 3 };
    int n = arr.size();

    vector<pair<int,int>> ans = findMaxRange(arr, n);
    for(int i=0;i<n;i++){
        cout<<"{"<<ans[i].first<<","<<ans[i].second<<"} ";
    }
}

 

Input and Output:

Input: 9 1 9 10 2 3
Output: {0,1} {1,1} {1,2} {0,5} {4,4} {4,5}

Complexity Analysis

Time Complexity: O(N)

Since we are doing single traversals, therefore, the time complexity is O(N).

Space Complexity: O(N)

Since we store our answer in another array, the space complexity will be O(N).

Frequently asked questions

Q1. What is a stack?

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

Q2. What is space complexity?

Ans. The space complexity of an algorithm is the overall space taken by algorithm w.r.t input size.

 

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 of maximum range length such that A[i] is maximum in the given range for all i from [1, N]. We have also discussed two approaches to this problem. The first one is the brute force solution, and the second is the optimal solution implemented using a stack.
 

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