1.
Introduction
2.
Brute Force Approach
2.1.
Algorithm
2.2.
Code in C++
2.3.
Complexity Analysis
3.
Optimized Approach
3.1.
Algorithm
3.2.
Code in C++
3.3.
Complexity Analysis
4.
4.1.
What is a stack?
4.2.
What is space complexity?
4.3.
What is a queue?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

# Maximum Range Length such that A[i] is Maximum in the given Range for all i from [1, N]

## Introduction

Strings are one of the most basic Data Structures and are one of the favorite topics of interviews to ask about in interviews even in top tech companies. A mastery of string could help you solve a wide range of problems using various approaches. Here in this blog we discuss one such problem.

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

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

### What is a stack?

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

### What is space complexity?

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

### What is a queue?

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

## Conclusion

In this article, we discussed the problem of maximum range length such that A[i] is maximumthe 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!