Given an array arr[] of N distinct integers, the task is to calculate for each index i (1≤i≤N) a range [L, R] such that arr[i] = min(arr[L], arr[L+1], … arr[R]), where L≤i≤R and R-L is maximized.
Examples:
Input: N = 3, arr[] = {1, 3, 2}
Output: 1 3
2 2
2 3
Explanation: 1 is minimum in the range [1, 3]
3 is minimum in the range [2, 2]
2 is minimum in range [2, 3]Input: N = 3, arr[] = {4, 5, 6}
Output: 1 3
2 3
3 3
Approach: It can be observed that previous smaller and next smaller elements are required at each index to calculate the required range. The idea is to use stacks to find the previous greater and the next greater elements. Follow the steps below to solve the problem:
- Create two arrays, L[] and R[], to store the closest smaller element at left and the closest smaller element at the right of the current element respectively.
- Create a stack S, and add the index of the first element in it.
- Traverse the given array, arr[], and pop stack until the top of the stack, S is not smaller than the current element.
- Now set the closest smaller element at the left i.e L[i] as the top of S, and if S is empty, set it as 0. Push the current element into S.
- Similarly, traverse from the end in opposite direction and follow the same steps to fill the array, R[].
- Iterate in the range [1, N] and print L[i] and R[i] for each index i.
Below is the implementation for the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to print the range for each indexvoid rangeFinder(int arr[], int N){ // Array to store index of closest smaller // element at left sub-array int L[N]; // Array to store index of closest smaller // element at right sub-array int R[N]; // Stack to find previous smaller element stack<int> S; // Since there is no element before first // element, so set L[0]=0 L[0] = 0; // Push the first element index in stack S.push(0); // Traverse the array, arr[] for (int i = 1; i < N; i++) { // Pop until the top of stack is greater // than current element while (!S.empty() && arr[S.top()] > arr[i]) S.pop(); // Update L[i] as peek as it is // previous smaller element if (!S.empty()) L[i] = S.top() + 1; // Otherwise, update L[i] to 0 else L[i] = 0; // Push the current index S.push(i); } // Empty the stack, S while (!S.empty()) S.pop(); // Since there is no element after // last element, so set R[N-1]=N-1 R[N - 1] = N - 1; // Push the last element index into stack S.push(N - 1); // Traverse the array from the end for (int i = N - 2; i >= 0; i--) { // Pop until the top of S is greater // than current element while (!S.empty() && arr[S.top()] > arr[i]) S.pop(); // Set R[i] as top as it is previous // smaller element from end if (!S.empty()) R[i] = S.top() - 1; // Otherwise, update R[i] as N-1 else R[i] = N - 1; // Push the current index S.push(i); } // Print the required range using L and R array for (int i = 0; i < N; i++) { cout << L[i] + 1 << " " << R[i] + 1 << endl; }}// Driver Codeint main(){ // Given Input int arr[] = { 1, 3, 2 }; int N = sizeof(arr) / sizeof(arr[0]); // Function Call rangeFinder(arr, N); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG{// Function to print the range for each indexstatic void rangeFinder(int arr[], int N){ // Array to store index of closest smaller // element at left sub-array int[] L = new int[N]; // Array to store index of closest smaller // element at right sub-array int[] R = new int[N]; // Stack to find previous smaller element Stack<Integer> S = new Stack<Integer>(); // Since there is no element before first // element, so set L[0]=0 L[0] = 0; // Push the first element index in stack S.push(0); // Traverse the array, arr[] for(int i = 1; i < N; i++) { // Pop until the top of stack is greater // than current element while (!S.empty() && arr[S.peek()] > arr[i]) S.pop(); // Update L[i] as peek as it is // previous smaller element if (!S.empty()) L[i] = S.peek() + 1; // Otherwise, update L[i] to 0 else L[i] = 0; // Push the current index S.push(i); } // Empty the stack, S while (!S.empty()) S.pop(); // Since there is no element after // last element, so set R[N-1]=N-1 R[N - 1] = N - 1; // Push the last element index into stack S.push(N - 1); // Traverse the array from the end for(int i = N - 2; i >= 0; i--) { // Pop until the top of S is greater // than current element while (!S.empty() && arr[S.peek()] > arr[i]) S.pop(); // Set R[i] as top as it is previous // smaller element from end if (!S.empty()) R[i] = S.peek() - 1; // Otherwise, update R[i] as N-1 else R[i] = N - 1; // Push the current index S.push(i); } // Print the required range using L and R array for(int i = 0; i < N; i++) { System.out.println((L[i] + 1) + " " + (R[i] + 1)); }}// Driver Codepublic static void main(String[] args){ // Given Input int arr[] = { 1, 3, 2 }; int N = arr.length; // Function Call rangeFinder(arr, N);}}// This code is contributed by MuskanKalra1 |
Python3
# Python3 program for the above approach# Function to print the range for each indexdef rangeFinder(arr, N): # Array to store index of closest smaller # element at left sub-array L = [0 for i in range(N)] # Array to store index of closest smaller # element at right sub-array R = [0 for i in range(N)] # Stack to find previous smaller element S = [] # Since there is no element before first # element, so set L[0]=0 L[0] = 0 # Push the first element index in stack S.append(0) # Traverse the array, arr[] for i in range(1, N, 1): # Pop until the top of stack is greater # than current element while (len(S) > 0 and arr[S[len(S) - 1]] > arr[i]): S = S[:-1] # Update L[i] as peek as it is # previous smaller element if (len(S) > 0): L[i] = S[len(S) - 1] + 1 # Otherwise, update L[i] to 0 else: L[i] = 0 # Push the current index S.append(i) # Empty the stack, S while (len(S) > 0): S.pop() # Since there is no element after # last element, so set R[N-1]=N-1 R[N - 1] = N - 1 # Push the last element index into stack S.append(N - 1) # Traverse the array from the end i = N - 2 while (i >= 0): # Pop until the top of S is greater # than current element while (len(S) > 0 and arr[S[len(S) - 1]] > arr[i]): S = S[:-1] # Set R[i] as top as it is previous # smaller element from end if (len(S) > 0): R[i] = S[len(S) - 1] - 1; # Otherwise, update R[i] as N-1 else: R[i] = N - 1 # Push the current index S.append(i) i -= 1 # Print the required range using L and R array for i in range(N): print(L[i] + 1, R[i] + 1)# Driver Codeif __name__ == '__main__': # Given Input arr = [ 1, 3, 2 ] N = len(arr) # Function Call rangeFinder(arr, N) # This code is contributed by ipg2016107 |
C#
// C# program for the above approachusing System;using System.Collections;class GFG { // Function to print the range for each index static void rangeFinder(int[] arr, int N) { // Array to store index of closest smaller // element at left sub-array int[] L = new int[N]; // Array to store index of closest smaller // element at right sub-array int[] R = new int[N]; // Stack to find previous smaller element Stack S = new Stack(); // Since there is no element before first // element, so set L[0]=0 L[0] = 0; // Push the first element index in stack S.Push(0); // Traverse the array, arr[] for(int i = 1; i < N; i++) { // Pop until the top of stack is greater // than current element while (S.Count > 0 && arr[(int)S.Peek()] > arr[i]) S.Pop(); // Update L[i] as peek as it is // previous smaller element if (S.Count > 0) L[i] = (int)S.Peek() + 1; // Otherwise, update L[i] to 0 else L[i] = 0; // Push the current index S.Push(i); } // Empty the stack, S while (S.Count > 0) S.Pop(); // Since there is no element after // last element, so set R[N-1]=N-1 R[N - 1] = N - 1; // Push the last element index into stack S.Push(N - 1); // Traverse the array from the end for(int i = N - 2; i >= 0; i--) { // Pop until the top of S is greater // than current element while (S.Count > 0 && arr[(int)S.Peek()] > arr[i]) S.Pop(); // Set R[i] as top as it is previous // smaller element from end if (S.Count > 0) R[i] = (int)S.Peek() - 1; // Otherwise, update R[i] as N-1 else R[i] = N - 1; // Push the current index S.Push(i); } // Print the required range using L and R array for(int i = 0; i < N; i++) { Console.WriteLine((L[i] + 1) + " " + (R[i] + 1)); } } static void Main() { // Given Input int[] arr = { 1, 3, 2 }; int N = arr.Length; // Function Call rangeFinder(arr, N); }}// This code is contributed by divyesh072019. |
Javascript
<script>// JavaScript program for the above approach// Function to print the range for each indexfunction rangeFinder(arr, N) { // Array to store index of closest smaller // element at left sub-array let L = new Array(N).fill(0); // Array to store index of closest smaller // element at right sub-array let R = new Array(N).fill(0); // Stack to find previous smaller element let S = []; // Since there is no element before first // element, so set L[0]=0 L[0] = 0; // Push the first element index in stack S.push(0); // Traverse the array, arr[] for (let i = 1; i < N; i++) { // Pop until the top of stack is greater // than current element while (S.length && arr[S[S.length - 1]] > arr[i]) S.pop(); // Update L[i] as peek as it is // previous smaller element if (S.length) L[i] = S[S.length - 1] + 1; // Otherwise, update L[i] to 0 else L[i] = 0; // Push the current index S.push(i); } // Empty the stack, S while (S.length) S.pop(); // Since there is no element after // last element, so set R[N-1]=N-1 R[N - 1] = N - 1; // Push the last element index into stack S.push(N - 1); // Traverse the array from the end for (let i = N - 2; i >= 0; i--) { // Pop until the top of S is greater // than current element while (S.length && arr[S[S.length - 1]] > arr[i]) S.pop(); // Set R[i] as top as it is previous // smaller element from end if (S.length) R[i] = S[S.length - 1] - 1; // Otherwise, update R[i] as N-1 else R[i] = N - 1; // Push the current index S.push(i); } // Print the required range using L and R array for (let i = 0; i < N; i++) { document.write(L[i] + 1 + " ") document.write(R[i] + 1 + "<br>"); }}// Driver Code// Given Inputlet arr = [1, 3, 2];let N = arr.length;// Function CallrangeFinder(arr, N);</script> |
Output:
1 3 2 2 2 3
Time Complexity: O(N)
Auxiliary Space: O(N)
Take a part in the ongoing discussion
