Given an array arr[] and an array Q[][] consisting of queries of the form of {L, R}, the task for each query is to find the maximum array element after removing array elements from the range of indices [L, R]. If the array becomes empty after removing the elements from given range of indices, then print 0.
Examples:
Input: arr[] = {5, 6, 8, 10, 15}, Q = {{0, 1}, {0, 2}, {1, 4}}
Output:
15
15
5
Explanation:
For the first query {0 1}: Remove array elements in range [0, 1], array modifies to {8, 10, 15}. Hence, the maximum element is 15.
For the second query {0, 2}: Remove array elements in range [0, 2], array modifies to {10, 15}. Hence, the maximum element is 15.
For the third query {1 4}: Remove array elements in range [1, 4], array modifies to {5}. Hence, the maximum element is 5.Input: arr[] = {8, 12, 14, 10, 13}, Q = {{0, 3}, {0, 4}, {4, 4}}
Output:
13
-1
14
Naive Approach: The simplest approach is to traverse the array to find the maximum element after removing the array elements in the given range in each query.
Time Complexity: O(N*Q)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to use two auxiliary arrays: one will store the prefix maximum (maximum element in the range [0, i]) and the other array will store the suffix maximum (maximum element in the range [i, N – 1]). Then for every query [L, R], the answer will be a maximum of prefixMax[l – 1] and suffixMax[r + 1]. Follow the steps below to solve the problem:
- Initialize two auxiliary arrays: prefixMax and suffixMax of size N + 1 and initialize prefixMax[0] as arr[0] and suffixMax[N – 1] as arr[N – 1].
- Iterate over the range [1, N – 1] using the variable i and set prefixMax[i] to the maximum of prefixMax[i – 1] and arr[i].
- Iterate over the range [N – 2, 0] using the variable i and set suffixMax[i] to the maximum of suffixMax[i + 1] and arr[i].
- Traverse the array Q[][] and for each query, check the following conditions:
- If L = 0 and R = N – 1, print 0 as the result.
- Otherwise, if L = 0, print suffixMax[R + 1] as the result.
- Otherwise, if R = N – 1, print prefixMax[L – 1] as the result.
- For all other cases, print the maximum of prefixMax[L – 1] and suffixMax[R + 1].
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 the maximum element// after removing elements in range [l, r]int findMaximum(int arr[], int N, int Q, int queries[][2]){ // Store prefix maximum element int prefix_max[N + 1] = { 0 }; // Store suffix maximum element int suffix_max[N + 1] = { 0 }; // Prefix max till first index // is first index itself prefix_max[0] = arr[0]; // Traverse the array to fill // prefix max array for (int i = 1; i < N; i++) { // Store maximum till index i prefix_max[i] = max(prefix_max[i - 1], arr[i]); } // Suffix max till last index // is last index itself suffix_max[N - 1] = arr[N - 1]; // Traverse the array to fill // suffix max array for (int i = N - 2; i >= 0; i--) { // Store maximum till index i suffix_max[i] = max(suffix_max[i + 1], arr[i]); } // Traverse all queries for (int i = 0; i < Q; i++) { // Store the starting and the // ending index of the query int l = queries[i][0]; int r = queries[i][1]; // Edge Cases if (l == 0 && r == (N - 1)) cout << "0\n"; else if (l == 0) cout << suffix_max[r + 1] << "\n"; else if (r == (N - 1)) cout << prefix_max[l - 1] << "\n"; // Otherwise else cout << max(prefix_max[l - 1], suffix_max[r + 1]) << "\n"; }}// Driver Codeint main(){ int arr[] = { 5, 6, 8, 10, 15 }; int N = sizeof(arr) / sizeof(arr[0]); int queries[][2] = { { 0, 1 }, { 0, 2 }, { 1, 4 } }; int Q = sizeof(queries) / sizeof(queries[0]); findMaximum(arr, N, Q, queries); return 0;} |
Java
// Java program for the above approachclass GFG{// Function to find the maximum element// after removing elements in range [l, r]static void findMaximum(int arr[], int N, int Q, int queries[][]){ // Store prefix maximum element int prefix_max[] = new int[N + 1]; // Store suffix maximum element int suffix_max[] = new int[N + 1]; // Prefix max till first index // is first index itself prefix_max[0] = arr[0]; // Traverse the array to fill // prefix max array for (int i = 1; i < N; i++) { // Store maximum till index i prefix_max[i] = Math.max(prefix_max[i - 1], arr[i]); } // Suffix max till last index // is last index itself suffix_max[N - 1] = arr[N - 1]; // Traverse the array to fill // suffix max array for (int i = N - 2; i >= 0; i--) { // Store maximum till index i suffix_max[i] = Math.max(suffix_max[i + 1], arr[i]); } // Traverse all queries for (int i = 0; i < Q; i++) { // Store the starting and the // ending index of the query int l = queries[i][0]; int r = queries[i][1]; // Edge Cases if (l == 0 && r == (N - 1)) System.out.print("0\n"); else if (l == 0) System.out.print(suffix_max[r + 1] + "\n"); else if (r == (N - 1)) System.out.print(prefix_max[l - 1] + "\n"); // Otherwise else System.out.print(Math.max(prefix_max[l - 1], suffix_max[r + 1]) + "\n"); }}// Driver Codepublic static void main(String[] args){ int arr[] = { 5, 6, 8, 10, 15 }; int N = arr.length; int queries[][] = { { 0, 1 }, { 0, 2 }, { 1, 4 } }; int Q = queries.length; findMaximum(arr, N, Q, queries);}}// This code is contributed by shikhasingrajput |
Python3
# Python3 program for the above approach# Function to find the maximum element# after removing elements in range [l, r]def findMaximum(arr, N, Q, queries): # Store prefix maximum element prefix_max = [0]*(N + 1) # Store suffix maximum element suffix_max = [0]*(N + 1) # Prefix max till first index # is first index itself prefix_max[0] = arr[0] # Traverse the array to fill # prefix max array for i in range(1, N): # Store maximum till index i prefix_max[i]= max(prefix_max[i - 1], arr[i]) # Suffix max till last index # is last index itself suffix_max[N - 1] = arr[N - 1] # Traverse the array to fill # suffix max array for i in range(N - 2, -1, -1): # Store maximum till index i suffix_max[i] = max(suffix_max[i + 1], arr[i]) # Traverse all queries for i in range(Q): # Store the starting and the # ending index of the query l = queries[i][0] r = queries[i][1] # Edge Cases if (l == 0 and r == (N - 1)): print("0") elif (l == 0): print(suffix_max[r + 1]) elif (r == (N - 1)): print(prefix_max[l - 1]) # Otherwise else: print(max(prefix_max[l - 1], suffix_max[r + 1]))# Driver Codeif __name__ == '__main__': arr = [5, 6, 8, 10, 15] N = len(arr) queries = [ [ 0, 1 ], [ 0, 2 ], [ 1, 4 ] ] Q = len(queries) findMaximum(arr, N, Q, queries) # This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;public class GFG{// Function to find the maximum element// after removing elements in range [l, r]static void findMaximum(int[] arr, int N, int Q, int[,] queries){ // Store prefix maximum element int[] prefix_max = new int[N + 1]; // Store suffix maximum element int[] suffix_max = new int[N + 1]; // Prefix max till first index // is first index itself prefix_max[0] = arr[0]; // Traverse the array to fill // prefix max array for (int i = 1; i < N; i++) { // Store maximum till index i prefix_max[i] = Math.Max(prefix_max[i - 1], arr[i]); } // Suffix max till last index // is last index itself suffix_max[N - 1] = arr[N - 1]; // Traverse the array to fill // suffix max array for (int i = N - 2; i >= 0; i--) { // Store maximum till index i suffix_max[i] = Math.Max(suffix_max[i + 1], arr[i]); } // Traverse all queries for (int i = 0; i < Q; i++) { // Store the starting and the // ending index of the query int l = queries[i, 0]; int r = queries[i, 1]; // Edge Cases if (l == 0 && r == (N - 1)) Console.Write("0\n"); else if (l == 0) Console.Write(suffix_max[r + 1] + "\n"); else if (r == (N - 1)) Console.Write(prefix_max[l - 1] + "\n"); // Otherwise else Console.Write(Math.Max(prefix_max[l - 1], suffix_max[r + 1]) + "\n"); }}// Driver Codestatic public void Main (){ int[] arr = { 5, 6, 8, 10, 15 }; int N = arr.Length; int[,] queries = { { 0, 1 }, { 0, 2 }, { 1, 4 } }; int Q = queries.GetLength(0); findMaximum(arr, N, Q, queries);}}// This code is contributed by sanjoy_62. |
Javascript
<script>// JavaScript program of the above approach// Function to find the maximum element// after removing elements in range [l, r]function findMaximum(arr, N, Q, queries){ // Store prefix maximum element let prefix_max = []; // Store suffix maximum element let suffix_max = []; // Prefix max till first index // is first index itself prefix_max[0] = arr[0]; // Traverse the array to fill // prefix max array for (let i = 1; i < N; i++) { // Store maximum till index i prefix_max[i] = Math.max(prefix_max[i - 1], arr[i]); } // Suffix max till last index // is last index itself suffix_max[N - 1] = arr[N - 1]; // Traverse the array to fill // suffix max array for (let i = N - 2; i >= 0; i--) { // Store maximum till index i suffix_max[i] = Math.max(suffix_max[i + 1], arr[i]); } // Traverse all queries for (let i = 0; i < Q; i++) { // Store the starting and the // ending index of the query let l = queries[i][0]; let r = queries[i][1]; // Edge Cases if (l == 0 && r == (N - 1)) document.write("0"); else if (l == 0) document.write(suffix_max[r + 1] + "<br/>"); else if (r == (N - 1)) document.write(prefix_max[l - 1] + "<br/>"); // Otherwise else document.write(Math.max(prefix_max[l - 1], suffix_max[r + 1]) + "<br/>"); }} // Driver Code let arr = [ 5, 6, 8, 10, 15 ]; let N = arr.length; let queries = [[ 0, 1 ], [ 0, 2 ], [ 1, 4 ]]; let Q = queries.length; findMaximum(arr, N, Q, queries);// This code is contributed by avijitmondal1998.</script> |
Output:
15 15 5
Time Complexity: O(N + Q)
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!
