Given an array nums[] of length N which contains integers, the task is to find a subarray such that the first and the last element of that subarray is neither the maximum nor minimum element present in that subarray and print the starting and ending index if there is such a subarray otherwise print -1.
Examples:
Input: N = 7, nums = [1, 3, 2, 4, 6, 5, 7]
Output: start = 1, end = 5
Explanation: Subarray starting from the 1st index and ending at 5th index follows the rule that is:
minimum in the subarray is 2, maximum in the subarray is 5 so,
nums[1] = 3 and nums[5] = 5 which is neither the minimum nor maximum of that subarray.Input: N = 6, nums = [2, 3, 6, 5, 4, 1]
Output: -1
Approach: To solve the problem follow the below idea:
We will use two Priority Queues, one of increasing type and the other of decreasing type, and at the same time, we will point two pointers at the start and at the end of the array respectively. Now, those two priority queue contains the maximum and minimum element of the current subarray formed by those two pointers and if the peek() element of those priority queues is not equal to either of the pointed indexed array then we will print the subarray.
For a clear understanding, see the below explanation for the above test case:
Suppose for the above example where N = 7 and nums[] = [1, 3, 2, 4, 6, 5, 7], we will have two priority queue one which is increasing and the other which is decreasing and they will contain:
- increasing: [1, 3, 2, 4, 6, 5, 7] and decreasing: [7, 4, 6, 1, 3, 2, 5] and, our two pointer is at i = 0, and j = 6.
- As nums[i] == increasing.peek() = 1, so we will increment i, also remove a top element from the
- increasing priority queue, after that our two pointers and two priority queue will be:
- increasing: [2, 3, 5, 4, 6, 7], decreasing = [7, 4, 6, 1, 3, 2, 5], i = 1, and j = 6.
- As nums[j] == decreasing.peek() = 7, so we will decrement j and remove the top element from the
- decreasing priority queue, after that our pointers and priority queues will be:
- increasing: [2, 3, 5, 4, 6, 7], decreasing: [6, 4, 5, 1, 3, 2], i = 1 and j = 5.
- Now nums[i], as well as nums[j], is not equal to any of the peek() elements from the priority queues
- Which means this subarray satisfies our condition, so we will print it.
- If in any case i crosses j without satisfying the condition then we will print -1.
Steps to follow to solve the problem:
- Enter all elements in two priority queues, one which is decreasing and the other which is increasing.
- Now we will use two pointer approach, one pointer will start from the 0th index and the other from (N -1)th index.
- If the first indexed element is equal to either of the peek() elements of the maximum priority queue or minimum priority queue we will increment it or if, the second indexed element is equal to either of the peek() element of the maximum priority queue or minimum priority queue we will decrement it.
- If none of the indexed element is equal to the peek() element of the maximum and minimum priority queue, we will print those indices and mark a boolean flag to true which signify that there exist such requires subarray.
- If the flag is false or null, then we will print -1.
- To understand the concept, use the below explanation.
Below is the implementation of the above approach:
C++
// C++ algorithm of the above approach #include <bits/stdc++.h> #include <iostream> #include <queue> using namespace std; int findSubArray( int nums[], int N) { // Initializing decreasing // priority queue priority_queue< int > decreasing; // Initializing increasing // priority queue priority_queue< int , vector< int >, greater< int > > increasing; // Adding all elements to both // of the priority queue for ( int i=0 ; i<N ; i++) { decreasing.push(nums[i]); increasing.push(nums[i]); } // Initializing two pointers one at // starting other at the ending int i = 0; int j = N - 1; // Boolean flag which ensures // whether we got the subarray or not bool flag = true ; while (i <= j && flag) { // Checking if starting element // of subarray is maximum or not if (nums[i] == decreasing.top()) { i++; decreasing.pop(); } // Checking if starting element // of subarray is minimum or not else if (nums[i] == increasing.top()) { i++; increasing.pop(); } // Checking if last element of // subarray is maximum or not else if (nums[j] == decreasing.top()) { j--; decreasing.pop(); } // Checking if last element of // subarray is minimum or not else if (nums[j] == increasing.top()) { j--; increasing.pop(); } // If none of the above case is // applied then we can say for // sure that the current subarray // satisfies the required condition else flag = false ; } // If flag is true means, we are // not able to find the subarray // and will print -1. if (flag) cout << -1 << endl; // Else we will print the starting // and the ending index of the subarray else cout << "start = " << i << ", " << "end = " << j << endl; } // Driver's Code int main() { int N = 7; int nums[] = { 1, 3, 2, 4, 6, 5, 7 }; findSubArray(nums, N); } |
Java
// Java algorithm of the above approach import java.util.*; class GFG { // Driver's Code public static void main(String[] args) { int N = 7 ; int [] nums = { 1 , 3 , 2 , 4 , 6 , 5 , 7 }; findSubArray(nums, N); } // Function to find the subarray public static void findSubArray( int [] nums, int N) { // Initializing decreasing // priority queue PriorityQueue<Integer> decreasing = new PriorityQueue<>( Collections.reverseOrder()); // Initializing increasing // priority queue PriorityQueue<Integer> increasing = new PriorityQueue<>(); // Adding all elements to both // of the priority queue for ( int v : nums) { decreasing.add(v); increasing.add(v); } // Initializing two pointers one at // starting other at the ending int i = 0 ; int j = N - 1 ; // Boolean flag which ensures // whether we got the subarray or not boolean flag = true ; while (i <= j && flag) { // Checking if starting element // of subarray is maximum or not if (nums[i] == decreasing.peek()) { i++; decreasing.remove(); } // Checking if starting element // of subarray is minimum or not else if (nums[i] == increasing.peek()) { i++; increasing.remove(); } // Checking if last element of // subarray is maximum or not else if (nums[j] == decreasing.peek()) { j--; decreasing.remove(); } // Checking if last element of // subarray is minimum or not else if (nums[j] == increasing.peek()) { j--; increasing.remove(); } // If none of the above case is // applied then we can say for // sure that the current subarray // satisfies the required condition else flag = false ; } // If flag is true means, we are // not able to find the subarray // and will print -1. if (flag) System.out.println(- 1 ); // Else we will print the starting // and the ending index of the subarray else System.out.println( "start = " + i + ", " + "end = " + j); } } |
Python3
# Python algorithm of the above approach import heapq def findSubArray(nums, N): # Initializing decreasing # priority queue decreasing = [] # Initializing increasing # priority queue increasing = [] # Adding all elements to both # of the priority queue for i in range (N): heapq.heappush(decreasing, - nums[i]) heapq.heappush(increasing, nums[i]) # Initializing two pointers one at # starting other at the ending i = 0 j = N - 1 # Boolean flag which ensures # whether we got the subarray or not flag = True while i < = j and flag: # Checking if starting element # of subarray is maximum or not if nums[i] = = - decreasing[ 0 ]: i + = 1 heapq.heappop(decreasing) # Checking if starting element # of subarray is minimum or not elif nums[i] = = increasing[ 0 ]: i + = 1 heapq.heappop(increasing) # Checking if last element of # subarray is maximum or not elif nums[j] = = - decreasing[ 0 ]: j - = 1 heapq.heappop(decreasing) # Checking if last element of # subarray is minimum or not elif nums[j] = = increasing[ 0 ]: j - = 1 heapq.heappop(increasing) # If none of the above case is # applied then we can say for # sure that the current subarray # satisfies the required condition else : flag = False # If flag is true means, we are # not able to find the subarray # and will print -1. if flag: print ( - 1 ) # Else we will print the starting # and the ending index of the subarray else : print ( "start =" , i, ", end =" , j) # Driver's Code N = 7 nums = [ 1 , 3 , 2 , 4 , 6 , 5 , 7 ] findSubArray(nums, N) # This code is contributed by prasad264 |
C#
// C# algorithm of the above approach using System; using System.Collections.Generic; public class Program { // Driver's Code public static void Main() { int N = 7; int [] nums = { 1, 3, 2, 4, 6, 5, 7 }; FindSubArray(nums, N); } public static void FindSubArray( int [] nums, int N) { // Initializing decreasing // priority queue var decreasing = new List< int >(); // Initializing increasing // priority queue var increasing = new List< int >(); int i; // Adding all elements to both // of the priority queue for (i = 0; i < N; i++) { decreasing.Add(-nums[i]); increasing.Add(nums[i]); } decreasing.Sort(); increasing.Sort(); // Initializing two pointers one at // starting other at the ending i = 0; int j = N - 1; // Boolean flag which ensures // whether we got the subarray or not bool flag = true ; while (i <= j && flag) { // Checking if starting element // of subarray is maximum or not if (nums[i] == -decreasing[0]) { i++; decreasing.RemoveAt(0); } // Checking if starting element // of subarray is minimum or not else if (nums[i] == increasing[0]) { i++; increasing.RemoveAt(0); } // Checking if last element of // subarray is maximum or not else if (nums[j] == -decreasing[0]) { j--; decreasing.RemoveAt(0); } // Checking if last element of // subarray is minimum or not else if (nums[j] == increasing[0]) { j--; increasing.RemoveAt(0); } // If none of the above case is // applied then we can say for // sure that the current subarray // satisfies the required condition else { flag = false ; } } // If flag is true means, we are // not able to find the subarray // and will print -1. if (flag) { Console.WriteLine(-1); } // Else we will print the starting // and the ending index of the subarray else { Console.WriteLine( "start = " + i + ", end = " + j); } } } // this code is contributed by shivhack999 |
Javascript
// JavaScript Code implementation function findSubArray(nums, N) { // Initializing decreasing priority queue let decreasing = []; // Initializing increasing priority queue let increasing = []; // Adding all elements to both of the priority queue for (let i = 0; i < N; i++) { decreasing.push(-nums[i]); increasing.push(nums[i]); } // sorting the decreasing queue decreasing.sort( function (a, b){ return b - a}); // sorting the increasing queue increasing.sort( function (a, b){ return a - b}); // Initializing two pointers one at starting other at the ending let i = 0; let j = N - 1; // Boolean flag which ensures whether we got the subarray or not let flag = true ; while (i <= j && flag) { // Checking if starting element of subarray is maximum or not if (nums[i] == -decreasing[0]) { i += 1; decreasing.shift(); } // Checking if starting element of subarray is minimum or not else if (nums[i] == increasing[0]) { i += 1; increasing.shift(); } // Checking if last element of subarray is maximum or not else if (nums[j] == -decreasing[0]) { j -= 1; decreasing.shift(); } // Checking if last element of subarray is minimum or not else if (nums[j] == increasing[increasing.length - 1]) { j -= 1; increasing.pop(); } // If none of the above case is applied then we can say for // sure that the current subarray satisfies the required condition else { flag = false ; } } // If flag is true means, we are not able to find the subarray // and will print -1. if (flag) { console.log(-1); } // Else we will print the starting and the ending index of the // subarray else { console.log(`start = ${i}, end = ${j}`); } } // Driver's Code let N = 7; let nums = [1, 3, 2, 4, 6, 5, 7]; findSubArray(nums, N); // This code is contributed by sankar. |
start = 1, end = 5
Time Complexity: O(N * log(N)), log(N) for the priority queue.
Auxiliary Space: O(N) is used by the priority queue.