Given an array arr[] consisting of N integers, where each array element represents the height of a building situated on the X co-ordinates, the task is to check if it is possible to select 3 buildings, such that the third selected building is taller than the first selected building and shorter than the second selected building.
Examples:
Input: arr[] = {4, 7, 11, 5, 13, 2}
Output: Yes
Explanation:
One possible way is to select the building at indices [0, 1, 3] with heights 4, 7 and 5 respectively.Input: arr[] = {11, 11, 12, 9}
Output: No
Approach: The given problem can be solved using the Stack data structure. Follow the steps below to solve the problem:
- If N is less than 3, then print “No“.
- Initialize an array, say preMin[], to store the prefix minimum array of array arr[].
- Traverse the array arr[] and update preMin[i] as preMin[i] = min(preMin[i-1], arr[i]).
- Now, initialize a Stack, say stack, to store the elements from the ending in ascending order.
- Traverse the array arr[] in reverse using a variable, say i, and perform the following steps:
- If arr[i] is greater than the preMin[i] then do the following:
- Iterate while the stack is not empty and the top element of the stack is less than preMin[i], then pop the top element of the stack in each iteration.
- If the stack is not empty and the top element of the stack is less than the arr[i], then print “Yes” and return.
- Otherwise, after the above step, push arr[i] into the stack.
- If arr[i] is greater than the preMin[i] then do the following:
- After completing the above steps, if none of the above cases satisfy, then print “No“.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// Function to check if it is possible// to select three buildings that// satisfy the given conditionstring recreationalSpot(int arr[], int N){ if (N < 3) { return "No"; } // Stores prefix min array int preMin[N]; preMin[0] = arr[0]; // Iterate over the range [1, N-1] for (int i = 1; i < N; i++) { preMin[i] = min(preMin[i - 1], arr[i]); } // Stores the element from the // ending in increasing order stack<int> stack; // Iterate until j is greater than // or equal to 0 for (int j = N - 1; j >= 0; j--) { // If current array element is // greater than the prefix min // upto j if (arr[j] > preMin[j]) { // Iterate while stack is not // empty and top element is // less than or equal to preMin[j] while (!stack.empty() && stack.top() <= preMin[j]) { // Remove the top element stack.pop(); } // If stack is not empty and top // element of the stack is less // than the current element if (!stack.empty() && stack.top() < arr[j]) { return "Yes"; } // Push the arr[j] in stack stack.push(arr[j]); } } // If none of the above case // satisfy then return "No" return "No";}// Driver codeint main(){ // Input int arr[] = { 4, 7, 11, 5, 13, 2 }; int size = sizeof(arr) / sizeof(arr[0]); cout << recreationalSpot(arr, size);} |
Java
// Java implementation of the above approachimport java.io.*;import java.util.*;class GFG{// Function to check if it is possible// to select three buildings that// satisfy the given conditionstatic String recreationalSpot(int arr[], int N){ if (N < 3) { return "No"; } // Stores prefix min array int preMin[] = new int[N]; preMin[0] = arr[0]; // Iterate over the range [1, N-1] for(int i = 1; i < N; i++) { preMin[i] = Math.min(preMin[i - 1], arr[i]); } // Stores the element from the // ending in increasing order Stack<Integer> stack = new Stack<Integer>(); // Iterate until j is greater than // or equal to 0 for(int j = N - 1; j >= 0; j--) { // If current array element is // greater than the prefix min // upto j if (arr[j] > preMin[j]) { // Iterate while stack is not // empty and top element is // less than or equal to preMin[j] while (stack.empty() == false && stack.peek() <= preMin[j]) { // Remove the top element stack.pop(); } // If stack is not empty and top // element of the stack is less // than the current element if (stack.empty() == false && stack.peek() < arr[j]) { return "Yes"; } // Push the arr[j] in stack stack.push(arr[j]); } } // If none of the above case // satisfy then return "No" return "No";}// Driver codepublic static void main(String[] args){ // Input int arr[] = { 4, 7, 11, 5, 13, 2 }; int size = arr.length; System.out.println(recreationalSpot(arr, size));}}// This code is contributed by Dharanendra L V. |
Python3
# Python3 implementation of the above approach# Function to check if it is possible# to select three buildings that# satisfy the given conditiondef recreationalSpot(arr, N): if (N < 3): return "No" # Stores prefix min array preMin = [0] * N preMin[0] = arr[0] # Iterate over the range [1, N-1] for i in range(1, N): preMin[i] = min(preMin[i - 1], arr[i]) # Stores the element from the # ending in increasing order stack = [] # Iterate until j is greater than # or equal to 0 for j in range(N - 1, -1, -1): # If current array element is # greater than the prefix min # upto j if (arr[j] > preMin[j]): # Iterate while stack is not # empty and top element is # less than or equal to preMin[j] while (len(stack) > 0 and stack[-1] <= preMin[j]): # Remove the top element del stack[-1] # If stack is not empty and top # element of the stack is less # than the current element if (len(stack) > 0 and stack[-1] < arr[j]): return "Yes" # Push the arr[j] in stack stack.append(arr[j]) # If none of the above case # satisfy then return "No" return "No"# Driver codeif __name__ == '__main__': # Input arr = [ 4, 7, 11, 5, 13, 2 ] size = len(arr) print (recreationalSpot(arr, size))# This code is contributed by mohit kumar 29 |
C#
// C# implementation of the above approachusing System;using System.Collections.Generic;public class GFG{// Function to check if it is possible// to select three buildings that// satisfy the given conditionstatic String recreationalSpot(int []arr, int N){ if (N < 3) { return "No"; } // Stores prefix min array int []preMin = new int[N]; preMin[0] = arr[0]; // Iterate over the range [1, N-1] for(int i = 1; i < N; i++) { preMin[i] = Math.Min(preMin[i - 1], arr[i]); } // Stores the element from the // ending in increasing order Stack<int> stack = new Stack<int>(); // Iterate until j is greater than // or equal to 0 for(int j = N - 1; j >= 0; j--) { // If current array element is // greater than the prefix min // upto j if (arr[j] > preMin[j]) { // Iterate while stack is not // empty and top element is // less than or equal to preMin[j] while (stack.Count!=0 && stack.Peek() <= preMin[j]) { // Remove the top element stack.Pop(); } // If stack is not empty and top // element of the stack is less // than the current element if (stack.Count!=0 && stack.Peek() < arr[j]) { return "Yes"; } // Push the arr[j] in stack stack.Push(arr[j]); } } // If none of the above case // satisfy then return "No" return "No";}// Driver codepublic static void Main(String[] args){ // Input int []arr = { 4, 7, 11, 5, 13, 2 }; int size = arr.Length; Console.WriteLine(recreationalSpot(arr, size));}}// This code is contributed by 29AjayKumar |
Javascript
<script>// JavaScript implementation of the above approach// Function to check if it is possible// to select three buildings that// satisfy the given conditionfunction recreationalSpot(arr, N){ if (N < 3) { return "No"; } // Stores prefix min array var preMin = new Array(N); preMin[0] = arr[0]; var i; // Iterate over the range [1, N-1] for (i = 1; i < N; i++) { preMin[i] = Math.min(preMin[i - 1], arr[i]); } // Stores the element from the // ending in increasing order var st = []; var j; // Iterate until j is greater than // or equal to 0 for (j = N - 1; j >= 0; j--) { // If current array element is // greater than the prefix min // upto j if (arr[j] > preMin[j]) { // Iterate while st is not // empty and top element is // less than or equal to preMin[j] while (st.length>0 && st[st.length-1] <= preMin[j]) { // Remove the top element st.pop(); } // If st is not empty and top // element of the st is less // than the current element if (st.length>0 && st[st.length-1] < arr[j]) { return "Yes"; } // Push the arr[j] in st st.push(arr[j]); } } // If none of the above case // satisfy then return "No" return "No";}// Driver code // Input var arr = [4, 7, 11, 5, 13, 2]; var size = arr.length; document.write(recreationalSpot(arr, size));</script> |
Output
Yes
Time Complexity: O(N)
Auxiliary Space: O(N)
ANOTHER APPROACH USING 2 ARRAYS AND STACK:
Intuition:
- We create 2 arrays named nse(next smaller element) and nge(next greater element) for storing each element nge and nse on left.
- We create a Stack to keep track of the highest and lowest element encountered to fill the 2 arrays.
- Algorithm works like:
- For filling the nse array, we check everytime if st.peek()>=arr[i], then we keep poping to ensure the next smaller element is at the top of stack and if stack comes to be empty, then we fill -1.
- Similarly, for nge array,we check if st.peek()<=arr[i] , then we keep poping to ensure the next greater element is at the top and if stack comes to be empty, then we fill -1.
- Atlast we traverse though the array and check if nge[i]>nse[i] then we return true because we would get the 132 combination.
Implementation:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// Function to recreate the spotbool recreationalSpot(int a[], int n){ // sm[i]-> smallest element in [0,i] int sm[n]; stack<int> s; sm[0] = a[0]; // Find the minimum value for (int i = 1; i < n; i++) sm[i] = min(sm[i - 1], a[i]); for (int i = n - 1; i > 0; i--) { while (!s.empty() && a[i] > s.top()) { if (sm[i - 1] < s.top()) { return true; } s.pop(); } // Stores the element in the stack s.push(a[i]); } return false;}// Driver Codeint main(){ int arr[] = { 4, 7, 11, 5, 13, 2 }; int size = sizeof(arr) / sizeof(arr[0]); cout << recreationalSpot(arr, size);} |
Java
// Java program to create recreational spot.import java.io.*;import java.util.*;class GFG { static boolean recreationalSpot(int[] arr, int n) { int nge[] = new int[n]; int nse[] = new int[n]; Stack<Integer> st = new Stack<>(); for (int i = 0; i < n; i++) { while (st.isEmpty() == false && arr[st.peek()] >= arr[i]) st.pop(); if (st.isEmpty()) nse[i] = -1; else nse[i] = st.peek(); st.push(i); } st.clear(); for (int i = 0; i < n; i++) { while (st.isEmpty() == false && arr[st.peek()] <= arr[i]) st.pop(); if (st.isEmpty()) nge[i] = -1; else nge[i] = st.peek(); st.push(i); } for (int i = 0; i < n; i++) { if (nge[i] != -1 && nse[i] != -1) { if (nge[i] > nse[i]) return true; else { int x = nse[nge[i]]; // Find the nse of // nge[i]; while (x != -1) { if (arr[x] < arr[i]) return true; x = nse[x]; // Check if the nge's // nse is smaller than // arr[i] } } } } return false; } public static void main(String[] args) { int arr[] = { 4, 7, 11, 5, 13, 2 }; int size = arr.length; System.out.println(recreationalSpot(arr, size)); }}// This code is contributed by Raunak Singh |
Python3
# Function to recreate the spotdef recreationalSpot(a, n): # sm[i] -> smallest element in [0, i] sm = [0] * n s = [] sm[0] = a[0] # Find the minimum value for i in range(1, n): sm[i] = min(sm[i - 1], a[i]) for i in range(n - 1, 0, -1): while len(s) > 0 and a[i] > s[-1]: if sm[i - 1] < s[-1]: return True s.pop() # Stores the element in the stack s.append(a[i]) return False# Driver Codearr = [4, 7, 11, 5, 13, 2]size = len(arr)print(recreationalSpot(arr, size)) |
C#
using System;using System.Collections.Generic;public class Program{ public static bool RecreationalSpot(int[] a, int n) { // sm[i]-> smallest element in [0,i] int[] sm = new int[n]; Stack<int> s = new Stack<int>(); sm[0] = a[0]; // Find the minimum value for (int i = 1; i < n; i++) sm[i] = Math.Min(sm[i - 1], a[i]); for (int i = n - 1; i > 0; i--) { while (s.Count > 0 && a[i] > s.Peek()) { if (sm[i - 1] < s.Peek()) { return true; } s.Pop(); } // Stores the element in the stack s.Push(a[i]); } return false; } public static void Main() { int[] arr = { 4, 7, 11, 5, 13, 2 }; int size = arr.Length; Console.WriteLine(RecreationalSpot(arr, size)); }} |
Javascript
// Function to recreate the spotfunction recreationalSpot(a) { const n = a.length; const sm = []; const stack = []; sm[0] = a[0]; // Find the minimum value for (let i = 1; i < n; i++) sm[i] = Math.min(sm[i - 1], a[i]); for (let i = n - 1; i > 0; i--) { while (stack.length > 0 && a[i] > stack[stack.length - 1]) { if (sm[i - 1] < stack[stack.length - 1]) { return true; } stack.pop(); } // Stores the element in the stack stack.push(a[i]); } return false;}// Driver Codeconst arr = [4, 7, 11, 5, 13, 2];console.log(recreationalSpot(arr)); |
Output
true
Time Complexity: O(N), since we are traversing the array.
Space Complexity: O(N), because we are using 2 arrays and 1 stack.
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!
