Given an array arr[] of N elements and Q queries of the form [X]. For each query, the task is to find the largest interval [L, R] of the array such that the greatest element in the interval is arr[X], such that 1 ? L ? X ? R.
Note: The array has 1-based indexing.
Examples:
Input: N = 5, arr[] = {2, 1, 2, 3, 2}, Q = 3, query[] = {1, 2, 4}
Output:
[1, 3]
[2, 2]
[1, 5]
Explanation :
In 1st query, x = 1, so arr[x] = 2 and answer is L = 1 and R = 3. here, we can see that max(arr[1], arr[2], arr[3]) = arr[x], which is the maximum intervals.
In 2nd query, x = 2, so arr[x] = 1 and since it is the smallest element of the array, so the interval contains only one element, thus the range is [2, 2].
In 3rd query, x = 4, so arr[x] = 4, which is maximum element of the arr[], so the answer is whole array, L = 1 and R = N.Input: N = 4, arr[] = { 1, 2, 2, 4}, Q = 2, query[] = {1, 2}
Output:
[1, 1]
[1, 3]
Explanation:
In 1st query, x = 1, so arr[x] = 1 and since it is the smallest element of the array, so the interval contains only one element, thus the range is [1, 1].
In 2nd query, x = 2, so arr[x] = 2 and answer is L = 1 and R = 3. here, we can see that max(arr[1], arr[2], arr[3]) = arr[x] = arr[2] = 2, which is the maximum intervals.
Approach: The idea is to precompute the largest interval for every value K in arr[] from 1 to N. Below are the steps:
- For each element K in arr[], fix the index of the element K, then find how much we can extend the interval to it’s left and right.
- Decrement left iterator till arr[left] ? K and similarly increment right iterator till arr[right] ? K.
- The final value of left and right represents the starting and the ending index of the interval, which is stored in arrL[] and arrR[] respectively.
- After we have precomputed interval range for each value. Then, for each query, we need to print the interval range for arr[x] i.e., arrL[arr[x]] and arrR[arr[x]].
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to precompute the interval// for each queryvoid utilLargestInterval(int arr[], int arrL[], int arrR[], int N){ // For every values [1, N] find // the longest intervals for (int maxValue = 1; maxValue <= N; maxValue++) { int lastIndex = 0; // Iterate the array arr[] for (int i = 1; i <= N; i++) { if (lastIndex >= i || arr[i] != maxValue) continue; int left = i, right = i; // Shift the left pointers while (left > 0 && arr[left] <= maxValue) left--; // Shift the right pointers while (right <= N && arr[right] <= maxValue) right++; left++, right--; lastIndex = right; // Store the range of interval // in arrL[] and arrR[]. for (int j = left; j <= right; j++) { if (arr[j] == maxValue) { arrL[j] = left; arrR[j] = right; } } } }}// Function to find the largest interval// for each query in Q[]void largestInterval( int arr[], int query[], int N, int Q){ // To store the L and R of X int arrL[N + 1], arrR[N + 1]; // Function Call utilLargestInterval(arr, arrL, arrR, N); // Iterate to find ranges for each query for (int i = 0; i < Q; i++) { cout << "[" << arrL[query[i]] << ", " << arrR[query[i]] << "]\n"; }}// Driver Codeint main(){ int N = 5, Q = 3; // Given array arr[] int arr[N + 1] = { 0, 2, 1, 2, 3, 2 }; // Given Queries int query[Q] = { 1, 2, 4 }; // Function Call largestInterval(arr, query, N, Q); return 0;} |
Java
// Java program for the above approachclass GFG{// Function to precompute the interval// for each querystatic void utilLargestInterval(int arr[], int arrL[], int arrR[], int N){ // For every values [1, N] find // the longest intervals for(int maxValue = 1; maxValue <= N; maxValue++) { int lastIndex = 0; // Iterate the array arr[] for(int i = 1; i <= N; i++) { if (lastIndex >= i || arr[i] != maxValue) continue; int left = i, right = i; // Shift the left pointers while (left > 0 && arr[left] <= maxValue) left--; // Shift the right pointers while (right <= N && arr[right] <= maxValue) right++; left++; right--; lastIndex = right; // Store the range of interval // in arrL[] and arrR[]. for(int j = left; j <= right; j++) { if (arr[j] == maxValue) { arrL[j] = left; arrR[j] = right; } } } }}// Function to find the largest interval// for each query in Q[]static void largestInterval(int arr[], int query[], int N, int Q){ // To store the L and R of X int []arrL = new int[N + 1]; int []arrR = new int[N + 1]; // Function Call utilLargestInterval(arr, arrL, arrR, N); // Iterate to find ranges for // each query for(int i = 0; i < Q; i++) { System.out.print("[" + arrL[query[i]] + ", " + arrR[query[i]] + "]\n"); }}// Driver Codepublic static void main(String[] args){ int N = 5, Q = 3; // Given array arr[] int arr[] = { 0, 2, 1, 2, 3, 2 }; // Given queries int query[] = { 1, 2, 4 }; // Function call largestInterval(arr, query, N, Q);}}// This code is contributed by Amit Katiyar |
Python3
# Python3 program for the above approach# Function to precompute the interval# for each querydef utilLargestInterval(arr, arrL, arrR, N): # For every values [1, N] find # the longest intervals for maxValue in range(1, N + 1): lastIndex = 0 # Iterate the array arr[] for i in range(N + 1): if (lastIndex >= i or arr[i] != maxValue): continue left = i right = i # Shift the left pointers while (left > 0 and arr[left] <= maxValue): left -= 1 # Shift the right pointers while (right <= N and arr[right] <= maxValue): right += 1 left += 1 right -= 1 lastIndex = right # Store the range of interval # in arrL[] and arrR[]. for j in range(left, right + 1): if (arr[j] == maxValue): arrL[j] = left arrR[j] = right # Function to find the largest interval# for each query in Q[]def largestInterval(arr, query, N, Q): # To store the L and R of X arrL = [0 for i in range(N + 1)] arrR = [0 for i in range(N + 1)] # Function call utilLargestInterval(arr, arrL, arrR, N); # Iterate to find ranges for each query for i in range(Q): print('[' + str(arrL[query[i]]) + ', ' + str(arrR[query[i]]) + ']') # Driver code if __name__=="__main__": N = 5 Q = 3 # Given array arr[] arr = [ 0, 2, 1, 2, 3, 2 ] # Given Queries query = [ 1, 2, 4 ] # Function call largestInterval(arr, query, N, Q)# This code is contributed by rutvik_56 |
C#
// C# program for the above approachusing System;class GFG{// Function to precompute the interval// for each querystatic void utilLargestInterval(int []arr, int []arrL, int []arrR, int N){ // For every values [1, N] find // the longest intervals for(int maxValue = 1; maxValue <= N; maxValue++) { int lastIndex = 0; // Iterate the array []arr for(int i = 1; i <= N; i++) { if (lastIndex >= i || arr[i] != maxValue) continue; int left = i, right = i; // Shift the left pointers while (left > 0 && arr[left] <= maxValue) left--; // Shift the right pointers while (right <= N && arr[right] <= maxValue) right++; left++; right--; lastIndex = right; // Store the range of interval // in arrL[] and arrR[]. for(int j = left; j <= right; j++) { if (arr[j] == maxValue) { arrL[j] = left; arrR[j] = right; } } } }}// Function to find the largest interval// for each query in Q[]static void largestInterval(int []arr, int []query, int N, int Q){ // To store the L and R of X int []arrL = new int[N + 1]; int []arrR = new int[N + 1]; // Function Call utilLargestInterval(arr, arrL, arrR, N); // Iterate to find ranges for // each query for(int i = 0; i < Q; i++) { Console.Write("[" + arrL[query[i]] + ", " + arrR[query[i]] + "]\n"); }}// Driver Codepublic static void Main(String[] args){ int N = 5, Q = 3; // Given array []arr int []arr = { 0, 2, 1, 2, 3, 2 }; // Given queries int []query = { 1, 2, 4 }; // Function call largestInterval(arr, query, N, Q);}}// This code is contributed by Princi Singh |
Javascript
<script>// Javascript program for the above approach// Function to precompute the interval// for each queryfunction utilLargestInterval(arr, arrL, arrR, N){ // For every values [1, N] find // the longest intervals for (var maxValue = 1; maxValue <= N; maxValue++) { var lastIndex = 0; // Iterate the array arr[] for (var i = 1; i <= N; i++) { if (lastIndex >= i || arr[i] != maxValue) continue; var left = i, right = i; // Shift the left pointers while (left > 0 && arr[left] <= maxValue) left--; // Shift the right pointers while (right <= N && arr[right] <= maxValue) right++; left++, right--; lastIndex = right; // Store the range of interval // in arrL[] and arrR[]. for (var j = left; j <= right; j++) { if (arr[j] == maxValue) { arrL[j] = left; arrR[j] = right; } } } }}// Function to find the largest interval// for each query in Q[]function largestInterval( arr, query, N, Q){ // To store the L and R of X var arrL = Array(N+1).fill(0),arrR = Array(N+1).fill(0); // Function Call utilLargestInterval(arr, arrL, arrR, N); // Iterate to find ranges for each query for (var i = 0; i < Q; i++) { document.write( "[" + arrL[query[i]] + ", " + arrR[query[i]] + "]<br>"); }}// Driver Codevar N = 5, Q = 3;// Given array arr[]var arr = [0, 2, 1, 2, 3, 2];// Given Queriesvar query = [1, 2, 4];// Function CalllargestInterval(arr, query, N, Q);// This code is contributed by itsok.</script> |
Output:
[1, 3] [2, 2] [1, 5]
Time Complexity: O(Q + N2)
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!
