Given an array arr[] consisting of N distinct integers. For each i (0 ? i < n), find a range [l, r] such that A[i] = max(A[l], A[l+1], …, A[r]) and l ? i ? r and r-l is maximized.
Examples:
Input: arr[] = {1, 3, 2}
Output: {0 0}, {0 2}, {2 2}
Explanation: For i=0, 1 is maximum in range [0, 0] only. For i=1, 3 is maximum in range [0, 2] and for i = 2, 2 is maximum in range [2, 2] only.Input: arr[] = {1, 2}
Output: {0, 0}, {0, 1}
Naive Approach: The simplest approach to solve the problem is for each i, Iterate in the range [i+1, N-1] using variable r and iterate in the range [i-1, 0] using the variable l and terminate the loop when arr[l] > arr[i] and arr[r]>arr[i] respectively. The answer will be [l, r].
Time Complexity: O(N×N)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized further by using a stack data structure. Follow the steps below to solve the problem:
- Initialize two vectors, say left and right that will store the left index and right index for each i respectively.
- Initialize a stack of pairs, say s.
- Insert INT_MAX and -1 as a pair in the stack.
- Iterate in the range [0, N-1] using the variable i and perform the following steps:
- While s.top().first<arr[i], pop the top element from the stack.
- Modify the value of left[i] as s.top().second.
- Push {arr[i], i} in the stack.
- Now remove all the elements from the stack.
- Insert INT_MAX and N in the stack as pairs.
- Iterate in the range [N-1, 0] using the variable i and perform the following steps:
- While s.top().first<arr[i], pop the top element from the stack.
- Modify the value of right[i] as s.top().second.
- Push {arr[i], i} in the stack.
- Iterate in the range [0, N-1] using the variable i and print left[i] +1, right[i] -1 as the answer for ith element.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find maximum range for// each i such that arr[i] is max in rangevoid MaxRange(vector<int> A, int n){ // Vector to store the left and right index // for each i such that left[i]>arr[i] // and right[i] > arr[i] vector<int> left(n), right(n); stack<pair<int, int> > s; s.push({ INT_MAX, -1 }); // Traverse the array for (int i = 0; i < n; i++) { // While s.top().first<a[i] // remove the top element from // the stack while (s.top().first < A[i]) s.pop(); // Modify left[i] left[i] = s.top().second; s.push({ A[i], i }); } // Clear the stack while (!s.empty()) s.pop(); s.push(make_pair(INT_MAX, n)); // Traverse the array to find // right[i] for each i for (int i = n - 1; i >= 0; i--) { // While s.top().first<a[i] // remove the top element from // the stack while (s.top().first < A[i]) s.pop(); // Modify right[i] right[i] = s.top().second; s.push({ A[i], i }); } // Print the value range for each i for (int i = 0; i < n; i++) { cout << left[i] + 1 << ' ' << right[i] - 1 << "\n"; }}// Driver Codeint main(){ // Given Input vector<int> arr{ 1, 3, 2 }; int n = arr.size(); // Function Call MaxRange(arr, n); return 0;} |
Java
//Java program for above approachimport java.awt.*;import java.util.*;class GFG{ static class pair<T, V>{ T first; V second; } // Function to find maximum range for // each i such that arr[i] is max in range static void MaxRange(ArrayList<Integer> A, int n) { // Vector to store the left and right index // for each i such that left[i]>arr[i] // and right[i] > arr[i] int[] left = new int[n]; int[] right = new int[n]; Stack<pair<Integer,Integer>> s = new Stack<>(); pair<Integer,Integer> x = new pair<>(); x.first =Integer.MAX_VALUE; x.second = -1; s.push(x); // Traverse the array for (int i = 0; i < n; i++) { // While s.top().first<a[i] // remove the top element from // the stack while (s.peek().first < A.get(i)) s.pop(); // Modify left[i] left[i] = s.peek().second; pair<Integer,Integer> y = new pair<>(); y.first = A.get(i); y.second = i; s.push(y); } // Clear the stack while (!s.empty()) s.pop(); pair<Integer,Integer> k = new pair<>(); k.first =Integer.MAX_VALUE; k.second = n; s.push(k); // Traverse the array to find // right[i] for each i for (int i = n - 1; i >= 0; i--) { // While s.top().first<a[i] // remove the top element from // the stack while (s.peek().first < A.get(i)) s.pop(); // Modify right[i] right[i] = s.peek().second; pair<Integer,Integer> y = new pair<>(); y.first = A.get(i); y.second = i; s.push(y); } // Print the value range for each i for (int i = 0; i < n; i++) { System.out.print(left[i]+1); System.out.print(" "); System.out.println(right[i]-1); } } // Driver Code public static void main(String[] args) { // Given Input ArrayList<Integer> arr = new ArrayList<>(); arr.add(1); arr.add(3); arr.add(2); int n = arr.size(); // Function Call MaxRange(arr, n); }}// This code is contributed by hritikrommie. |
Python3
# Python 3 program for the above approachimport sys# Function to find maximum range for# each i such that arr[i] is max in rangedef MaxRange(A, n): # Vector to store the left and right index # for each i such that left[i]>arr[i] # and right[i] > arr[i] left = [0] * n right = [0] * n s = [] s.append((sys.maxsize, -1)) # Traverse the array for i in range(n): # While s.top().first<a[i] # remove the top element from # the stack while (s[-1][0] < A[i]): s.pop() # Modify left[i] left[i] = s[-1][1] s.append((A[i], i)) # Clear the stack while (len(s) != 0): s.pop() s.append((sys.maxsize, n)) # Traverse the array to find # right[i] for each i for i in range(n - 1, -1, -1): # While s.top().first<a[i] # remove the top element from # the stack while (s[-1][0] < A[i]): s.pop() # Modify right[i] right[i] = s[-1][1] s.append((A[i], i)) # Print the value range for each i for i in range(n): print(left[i] + 1, ' ', right[i] - 1)# Driver Codeif __name__ == "__main__": # Given Input arr = [1, 3, 2] n = len(arr) # Function Call MaxRange(arr, n) # This code is contributed by ukasp. |
C#
// C# program for the above approach.using System;using System.Collections;using System.Collections.Generic;class GFG{ // Function to find maximum range for // each i such that arr[i] is max in range static void MaxRange(List<int> A, int n) { // Vector to store the left and right index // for each i such that left[i]>arr[i] // and right[i] > arr[i] int[] left = new int[n]; int[] right = new int[n]; Stack s = new Stack(); s.Push(new Tuple<int, int>(Int32.MaxValue, -1)); // Traverse the array for (int i = 0; i < n; i++) { // While s.top().first<a[i] // remove the top element from // the stack while (((Tuple<int, int>)s.Peek()).Item1 < A[i]) s.Pop(); // Modify left[i] left[i] = ((Tuple<int, int>)s.Peek()).Item2; s.Push(new Tuple<int, int>(A[i], i)); } // Clear the stack while (s.Count > 0) s.Pop(); s.Push(new Tuple<int, int>(Int32.MaxValue, n)); // Traverse the array to find // right[i] for each i for (int i = n - 1; i >= 0; i--) { // While s.top().first<a[i] // remove the top element from // the stack while (((Tuple<int, int>)s.Peek()).Item1 < A[i]) s.Pop(); // Modify right[i] right[i] = ((Tuple<int, int>)s.Peek()).Item2; s.Push(new Tuple<int, int>(A[i], i)); } // Print the value range for each i for (int i = 0; i < n; i++) { Console.WriteLine((left[i] + 1) + " " + (right[i] - 1)); } } static void Main () { List<int> arr = new List<int>(); // adding elements in firstlist arr.Add(1); arr.Add(3); arr.Add(2); int n = arr.Count; // Function Call MaxRange(arr, n); }}// This code is contributed by suresh07. |
Javascript
<script>// Javascript program for the above approach// Function to find maximum range for// each i such that arr[i] is max in rangefunction MaxRange(A, n){ // Vector to store the left and right index // for each i such that left[i]>arr[i] // and right[i] > arr[i] let left = new Array(n).fill(0), right = new Array(n).fill(0); let s = []; s.push([Number.MAX_SAFE_INTEGER, -1]); // Traverse the array for(let i = 0; i < n; i++) { // While s.top()[0]<a[i] // remove the top element from // the stack while (s[s.length - 1][0] < A[i]) s.pop(); // Modify left[i] left[i] = s[s.length - 1][1]; s.push([A[i], i]); } // Clear the stack while (s.length) s.pop(); s.push([Number.MAX_SAFE_INTEGER, n]); // Traverse the array to find // right[i] for each i for(let i = n - 1; i >= 0; i--) { // While s.top()[0]<a[i] // remove the top element from // the stack while (s[s.length - 1][0] < A[i]) s.pop(); // Modify right[i] right[i] = s[s.length - 1][1]; s.push([A[i], i]); } // Print the value range for each i for(let i = 0; i < n; i++) { document.write(left[i] + 1 + " ") document.write(right[i] - 1 + "<br>") }}// Driver Code// Given Inputlet arr = [ 1, 3, 2 ];let n = arr.length;// Function CallMaxRange(arr, n);// This code is contributed by gfgking</script> |
Output:
0 0 0 2 2 2
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
