Given an array arr[] consisting of N integers and an array Q[][] consisting of queries of the form [L, R]., the task for each query is to find the maximum and minimum array elements in the array excluding the elements from the given range.
Examples:
Input: arr[] = {2, 3, 1, 8, 3, 5, 7, 4}, Q[][] = {{4, 6}, {0, 4}, {3, 7}, {2, 5}}
Output:
8 1
7 4
3 1
7 2
Explanation:
Query 1: max(arr[0, 1, …, 3], arr[7]) = 8 and min(arr[0, 1, …, 3], arr[7]) = 1
Query 2: max(arr[5, 6, …, 7]) = 7 and min(arr[5, 6, …, 7]) = 4
Query 3: max(arr[0, 1, …, 2]) =3 and min(arr[0, 1, …, 2]) = 1
Query 4: max(arr[0, 1], arr[6, …, 7]) =7 and min(arr[0, 1], arr[6, …, 7]) = 2Input: arr[] = {3, 2, 1, 4, 5}, Q[][] = {{1, 2}, {2, 4}}
Output:
5 3
3 2
Naive Approach: The simplest approach to solve the problem is to traverse the array for each query, and find the maximum and minimum elements present outside the range of indices [L, R].
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: Divide the problem into subtasks by dividing the array into sub-ranges and find the maximum and minimum value from arr[0] to arr[L – 1] and from arr[r + 1] to arr[N – 1] and store them in a prefix and a suffix array respectively. Now find the maximum and minimum values for the given ranges by comparing the prefix and the suffix array.
Follow the below steps:
- Traverse the array and maintain maximum and minimum elements encountered for every index in a 2D prefix array by comparing the value at the current index with the maximum and minimum values of the previous index.
- Now, iterate over the array in reverse and maintain maximum and minimum values for indices in 2D suffix array by comparing the value at the current index with the maximum and minimum values of the next index.
- Now, for each query, perform the following steps:
- If L = 0 and R = N – 1, then no element remains after excluding the range.
- Otherwise, if L = 0, the maximum and minimum value will be present between arr[R + 1] to arr[N – 1].
- Otherwise, if R = N – 1, the maximum and minimum value will be present between arr[0] to arr[L – 1].
- Otherwise, find the maximum and minimum values in the range arr[0] to arr[L – 1] and arr[R + 1] to arr[N – 1].
- Print the maximum and minimum values for this query.
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 and// minimum array elements up to the i-th indexvoid prefixArr(int arr[], int prefix[][2], int N){ // Traverse the array for (int i = 0; i < N; i++) { if (i == 0) { prefix[i][0] = arr[i]; prefix[i][1] = arr[i]; } else { // Compare current value with maximum // and minimum values up to previous index prefix[i][0] = max(prefix[i - 1][0], arr[i]); prefix[i][1] = min(prefix[i - 1][1], arr[i]); } }}// Function to find the maximum and// minimum array elements from i-th indexvoid suffixArr(int arr[], int suffix[][2], int N){ // Traverse the array in reverse for (int i = N - 1; i >= 0; i--) { if (i == N - 1) { suffix[i][0] = arr[i]; suffix[i][1] = arr[i]; } else { // Compare current value with maximum // and minimum values in the next index suffix[i][0] = max(suffix[i + 1][0], arr[i]); suffix[i][1] = min(suffix[i + 1][1], arr[i]); } }}// Function to find the maximum and// minimum array elements for each queryvoid maxAndmin(int prefix[][2], int suffix[][2], int N, int L, int R){ int maximum, minimum; // If no index remains after // excluding the elements // in a given range if (L == 0 && R == N - 1) { cout << "No maximum and minimum value" << endl; return; } // Find maximum and minimum from // from the range [R + 1, N - 1] else if (L == 0) { maximum = suffix[R + 1][0]; minimum = suffix[R + 1][1]; } // Find maximum and minimum from // from the range [0, N - 1] else if (R == N - 1) { maximum = prefix[L - 1][0]; minimum = prefix[R - 1][1]; } // Find maximum and minimum values from the // ranges [0, L - 1] and [R + 1, N - 1] else { maximum = max(prefix[L - 1][0], suffix[R + 1][0]); minimum = min(prefix[L - 1][1], suffix[R + 1][1]); } // Print the maximum and minimum value cout << maximum << " " << minimum << endl;}// Function to perform queries to find the// minimum and maximum array elements excluding// elements from a given rangevoid MinMaxQueries(int a[], int Q[][]){ // Size of the array int N = sizeof(arr) / sizeof(arr[0]); // Size of query array int q = sizeof(queries) / sizeof(queries[0]); // prefix[i][0]: Stores the maximum // prefix[i][1]: Stores the minimum value int prefix[N][2]; // suffix[i][0]: Stores the maximum // suffix[i][1]: Stores the minimum value int suffix[N][2]; // Function calls to store // maximum and minimum values // for respective ranges prefixArr(arr, prefix, N); suffixArr(arr, suffix, N); for (int i = 0; i < q; i++) { int L = queries[i][0]; int R = queries[i][1]; maxAndmin(prefix, suffix, N, L, R); }}// Driver Codeint main(){ // Given array int arr[] = { 2, 3, 1, 8, 3, 5, 7, 4 }; int queries[][2] = { { 4, 6 }, { 0, 4 }, { 3, 7 }, { 2, 5 } }; MinMaxQueries(arr, Q); return 0;} |
Java
// Java program for the above approachpublic class GFG{ // Function to find the maximum and // minimum array elements up to the i-th index static void prefixArr(int arr[], int prefix[][], int N) { // Traverse the array for (int i = 0; i < N; i++) { if (i == 0) { prefix[i][0] = arr[i]; prefix[i][1] = arr[i]; } else { // Compare current value with maximum // and minimum values up to previous index prefix[i][0] = Math.max(prefix[i - 1][0], arr[i]); prefix[i][1] = Math.min(prefix[i - 1][1], arr[i]); } } } // Function to find the maximum and // minimum array elements from i-th index static void suffixArr(int arr[], int suffix[][], int N) { // Traverse the array in reverse for (int i = N - 1; i >= 0; i--) { if (i == N - 1) { suffix[i][0] = arr[i]; suffix[i][1] = arr[i]; } else { // Compare current value with maximum // and minimum values in the next index suffix[i][0] = Math.max(suffix[i + 1][0], arr[i]); suffix[i][1] = Math.min(suffix[i + 1][1], arr[i]); } } } // Function to find the maximum and // minimum array elements for each query static void maxAndmin(int prefix[][], int suffix[][], int N, int L, int R) { int maximum, minimum; // If no index remains after // excluding the elements // in a given range if (L == 0 && R == N - 1) { System.out.println("No maximum and minimum value"); return; } // Find maximum and minimum from // from the range [R + 1, N - 1] else if (L == 0) { maximum = suffix[R + 1][0]; minimum = suffix[R + 1][1]; } // Find maximum and minimum from // from the range [0, N - 1] else if (R == N - 1) { maximum = prefix[L - 1][0]; minimum = prefix[R - 1][1]; } // Find maximum and minimum values from the // ranges [0, L - 1] and [R + 1, N - 1] else { maximum = Math.max(prefix[L - 1][0], suffix[R + 1][0]); minimum = Math.min(prefix[L - 1][1], suffix[R + 1][1]); } // Print the maximum and minimum value System.out.println(maximum + " " + minimum); } // Function to perform queries to find the // minimum and maximum array elements excluding // elements from a given range static void MinMaxQueries(int a[], int Q[][]) { // Size of the array int N = a.length; // Size of query array int q = Q.length; // prefix[i][0]: Stores the maximum // prefix[i][1]: Stores the minimum value int prefix[][] = new int[N][2]; // suffix[i][0]: Stores the maximum // suffix[i][1]: Stores the minimum value int suffix[][] = new int[N][2]; // Function calls to store // maximum and minimum values // for respective ranges prefixArr(a, prefix, N); suffixArr(a, suffix, N); for (int i = 0; i < q; i++) { int L = Q[i][0]; int R = Q[i][1]; maxAndmin(prefix, suffix, N, L, R); } } // Driver Code public static void main (String[] args) { // Given array int arr[] = { 2, 3, 1, 8, 3, 5, 7, 4 }; int queries[][] = { { 4, 6 }, { 0, 4 }, { 3, 7 }, { 2, 5 } }; MinMaxQueries(arr, queries); }}// This code is contributed by AnkThon |
Python3
# Python3 program for the above approach# Function to find the maximum and# minimum array elements up to the i-th indexdef prefixArr(arr, prefix, N): # Traverse the array for i in range(N): if (i == 0): prefix[i][0] = arr[i] prefix[i][1] = arr[i] else: # Compare current value with maximum # and minimum values up to previous index prefix[i][0] = max(prefix[i - 1][0], arr[i]) prefix[i][1] = min(prefix[i - 1][1], arr[i]) return prefix# Function to find the maximum and# minimum array elements from i-th indexdef suffixArr(arr, suffix, N): # Traverse the array in reverse for i in range(N - 1, -1, -1): if (i == N - 1): suffix[i][0] = arr[i] suffix[i][1] = arr[i] else: # Compare current value with maximum # and minimum values in the next index suffix[i][0] = max(suffix[i + 1][0], arr[i]) suffix[i][1] = min(suffix[i + 1][1], arr[i]) return suffix# Function to find the maximum and# minimum array elements for each querydef maxAndmin(prefix, suffix, N, L, R): maximum, minimum = 0, 0 # If no index remains after # excluding the elements # in a given range if (L == 0 and R == N - 1): print("No maximum and minimum value") return # Find maximum and minimum from # from the range [R + 1, N - 1] elif (L == 0): maximum = suffix[R + 1][0] minimum = suffix[R + 1][1] # Find maximum and minimum from # from the range [0, N - 1] elif (R == N - 1): maximum = prefix[L - 1][0] minimum = prefix[R - 1][1] # Find maximum and minimum values from the # ranges [0, L - 1] and [R + 1, N - 1] else: maximum = max(prefix[L - 1][0], suffix[R + 1][0]) minimum = min(prefix[L - 1][1], suffix[R + 1][1]) # Print maximum and minimum value print(maximum, minimum)# Function to perform queries to find the# minimum and maximum array elements excluding# elements from a given rangedef MinMaxQueries(a, queries): # Size of the array N = len(arr) # Size of query array q = len(queries) # prefix[i][0]: Stores the maximum # prefix[i][1]: Stores the minimum value prefix = [ [ 0 for i in range(2)] for i in range(N)] # suffix[i][0]: Stores the maximum # suffix[i][1]: Stores the minimum value suffix = [ [ 0 for i in range(2)] for i in range(N)] # Function calls to store # maximum and minimum values # for respective ranges prefix = prefixArr(arr, prefix, N) suffix = suffixArr(arr, suffix, N) for i in range(q): L = queries[i][0] R = queries[i][1] maxAndmin(prefix, suffix, N, L, R)# Driver Codeif __name__ == '__main__': # Given array arr = [ 2, 3, 1, 8, 3, 5, 7, 4 ] queries = [ [ 4, 6 ], [ 0, 4 ], [ 3, 7 ], [ 2, 5 ] ] MinMaxQueries(arr, 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 and // minimum array elements up to the i-th index static void prefixArr(int[] arr, int[,] prefix, int N) { // Traverse the array for (int i = 0; i < N; i++) { if (i == 0) { prefix[i, 0] = arr[i]; prefix[i, 1] = arr[i]; } else { // Compare current value with maximum // and minimum values up to previous index prefix[i, 0] = Math.Max(prefix[i - 1, 0], arr[i]); prefix[i, 1] = Math.Min(prefix[i - 1, 1], arr[i]); } } } // Function to find the maximum and // minimum array elements from i-th index static void suffixArr(int[] arr, int[,] suffix, int N) { // Traverse the array in reverse for (int i = N - 1; i >= 0; i--) { if (i == N - 1) { suffix[i, 0] = arr[i]; suffix[i, 1] = arr[i]; } else { // Compare current value with maximum // and minimum values in the next index suffix[i, 0] = Math.Max(suffix[i + 1, 0], arr[i]); suffix[i, 1] = Math.Min(suffix[i + 1, 1], arr[i]); } } } // Function to find the maximum and // minimum array elements for each query static void maxAndmin(int[,] prefix, int[,] suffix, int N, int L, int R) { int maximum, minimum; // If no index remains after // excluding the elements // in a given range if (L == 0 && R == N - 1) { Console.WriteLine("No maximum and minimum value"); return; } // Find maximum and minimum from // from the range [R + 1, N - 1] else if (L == 0) { maximum = suffix[R + 1, 0]; minimum = suffix[R + 1, 1]; } // Find maximum and minimum from // from the range [0, N - 1] else if (R == N - 1) { maximum = prefix[L - 1, 0]; minimum = prefix[R - 1, 1]; } // Find maximum and minimum values from the // ranges [0, L - 1] and [R + 1, N - 1] else { maximum = Math.Max(prefix[L - 1, 0], suffix[R + 1, 0]); minimum = Math.Min(prefix[L - 1, 1], suffix[R + 1, 1]); } // Print the maximum and minimum value Console.WriteLine(maximum + " " + minimum); } // Function to perform queries to find the // minimum and maximum array elements excluding // elements from a given range static void MinMaxQueries(int[] a, int[,] Q) { // Size of the array int N = a.GetLength(0); // Size of query array int q = Q.GetLength(0); // prefix[i][0]: Stores the maximum // prefix[i][1]: Stores the minimum value int[,] prefix = new int[N, 2]; // suffix[i][0]: Stores the maximum // suffix[i][1]: Stores the minimum value int[,] suffix = new int[N, 2]; // Function calls to store // maximum and minimum values // for respective ranges prefixArr(a, prefix, N); suffixArr(a, suffix, N); for (int i = 0; i < q; i++) { int L = Q[i, 0]; int R = Q[i, 1]; maxAndmin(prefix, suffix, N, L, R); } } // Driver Code static public void Main () { // Given array int[] arr = { 2, 3, 1, 8, 3, 5, 7, 4 }; int[,] queries = { { 4, 6 }, { 0, 4 }, { 3, 7 }, { 2, 5 } }; MinMaxQueries(arr, queries); }}// This code is contributed by sanjoy_62. |
Javascript
<script>// JavaScript program for the above approach// Function to find the maximum and// minimum array elements up to the i-th indexfunction prefixArr(arr, prefix, N){ // Traverse the array for (var i = 0; i < N; i++) { if (i == 0) { prefix[i][0] = arr[i]; prefix[i][1] = arr[i]; } else { // Compare current value with maximum // and minimum values up to previous index prefix[i][0] = Math.max(prefix[i - 1][0], arr[i]); prefix[i][1] = Math.min(prefix[i - 1][1], arr[i]); } }}// Function to find the maximum and// minimum array elements from i-th indexfunction suffixArr(arr, suffix, N){ // Traverse the array in reverse for (var i = N - 1; i >= 0; i--) { if (i == N - 1) { suffix[i][0] = arr[i]; suffix[i][1] = arr[i]; } else { // Compare current value with maximum // and minimum values in the next index suffix[i][0] = Math.max(suffix[i + 1][0], arr[i]); suffix[i][1] = Math.min(suffix[i + 1][1], arr[i]); } }}// Function to find the maximum and// minimum array elements for each queryfunction maxAndmin(prefix, suffix, N, L, R){ var maximum, minimum; // If no index remains after // excluding the elements // in a given range if (L == 0 && R == N - 1) { document.write( "No maximum and minimum value" + "<br>"); return; } // Find maximum and minimum from // from the range [R + 1, N - 1] else if (L == 0) { maximum = suffix[R + 1][0]; minimum = suffix[R + 1][1]; } // Find maximum and minimum from // from the range [0, N - 1] else if (R == N - 1) { maximum = prefix[L - 1][0]; minimum = prefix[R - 1][1]; } // Find maximum and minimum values from the // ranges [0, L - 1] and [R + 1, N - 1] else { maximum = Math.max(prefix[L - 1][0], suffix[R + 1][0]); minimum = Math.min(prefix[L - 1][1], suffix[R + 1][1]); } // Print the maximum and minimum value document.write( maximum + " " + minimum + "<br>");}// Function to perform queries to find the// minimum and maximum array elements excluding// elements from a given rangefunction MinMaxQueries(a, Q){ // Size of the array var N = arr.length; // Size of query array var q = queries.length; // prefix[i][0]: Stores the maximum // prefix[i][1]: Stores the minimum value var prefix = Array.from(Array(N), ()=> Array(2)); // suffix[i][0]: Stores the maximum // suffix[i][1]: Stores the minimum value var suffix = Array.from(Array(N), ()=> Array(2)); // Function calls to store // maximum and minimum values // for respective ranges prefixArr(arr, prefix, N); suffixArr(arr, suffix, N); for (var i = 0; i < q; i++) { var L = queries[i][0]; var R = queries[i][1]; maxAndmin(prefix, suffix, N, L, R); }}// Driver Code// Given arrayvar arr = [2, 3, 1, 8, 3, 5, 7, 4 ];var queries = [ [ 4, 6 ], [ 0, 4 ], [ 3, 7 ], [ 2, 5 ] ];MinMaxQueries(arr, queries);</script> |
Output:
8 1 7 4 3 1 7 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!
