Problem Statement:
Given an array arr[] of N integers and q queries of the form [L, R], the task is to find the maximum and minimum array elements in the array excluding the elements from the given range [L, R] for each query.
Approach:
The main idea is to efficiently handle multiple queries by precomputing the maximum and minimum values for all subarrays that exclude a specific range. This is achieved using two auxiliary arrays: the prefix array, which stores the maximum and minimum values from the start of the array up to each index, and the suffix array, which stores the maximum and minimum values from each index to the end of the array. With these precomputed arrays, each query can be answered in constant time by combining the relevant prefix and suffix information, allowing us to determine the maximum and minimum values outside the specified range.
Time Complexity:
- Preprocessing: Building the prefix and suffix arrays takes
O(N)time. - Query Handling: Each query is handled in
O(1)time, making the overall complexityO(N + q)whereqis the number of queries.