
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 1 is maximum in the range {0,0}
- arr[1] i.e 4 is maximum in the range {0,3}
- arr[2] i.e 3 is maximum in the range {2,3}
- arr[3] i.e 2 is maximum in the range {3,3}
Input:
arr[] = {2,0,1}
Output:
{0,2}, {1,1}, {1,2}
Explanation:
- arr[0] i.e 2 is maximum in the range {0,2}
- arr[1] i.e 0 is maximum in the range {1,1}
- arr[2] i.e 1 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
- Create a function findMaxRange() that takes one parameter, the array given to us, and returns a vector of pairs.
- 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.
- 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.
- 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).