Given an array arr[] of size N. The task is to check if the array has 3 elements in indices i, j and k such that i < j < k and arr[i] < arr[j] > arr[k] and arr[i] < arr[k].
Examples:
Input: N = 6, arr[] = {4, 7, 11, 5, 13, 2}
Output: True
Explanation: [4, 7, 5] fits the condition.Input: N = 4, arr[] = {11, 11, 12, 9}
Output: False
Explanation: No 3 elements fit the given condition.
Naive Approach: The simplest approach is to have 3 nested loops, each loop represents the possible moves of their indexes, i.e. the first loop shows the all possible indices values of i, the second nested loop shows the possible indices of j, for each value of i, and the third nested loop tells the all possible values of k index, for each value of j and i. Then, check the given condition, arr[i] < arr[k] < arr[j], if it’s true then return true, else return false.
Below is the implementation of the above approach:
C++
// C++ code to implement the above approach#include <bits/stdc++.h>using namespace std;// function to find if the pattern existsbool recreationalSpot(int a[], int n){ // first loop for possible values of i, for (int i = 0; i < n; i++) { // second loop for possible values of j, for each i, for (int j = i + 1; j < n; j++) { // third loop for possible values of k, for each // value of j and i, for (int k = j + 1; k < n; k++) { // if the condition is matched a[i] < a[k] < // a[j], if (a[k] < a[j] && a[k] > a[i]) return true; } } } // if not found the condition to be true, return false;}// Driver Codeint main(){ int arr[] = { 4, 7, 11, 5, 13, 2 }; int N = sizeof(arr) / sizeof(arr[0]); // Function Call if (recreationalSpot(arr, N)) { cout << "True"; } else { cout << "False"; } return 0;} |
Java
import java.util.Arrays;public class Main { // function to find if the pattern exists public static boolean recreationalSpot(int[] a, int n) { // first loop for possible values of i, for (int i = 0; i < n; i++) { // second loop for possible values of j, for each i, for (int j = i + 1; j < n; j++) { // third loop for possible values of k, for each // value of j and i, for (int k = j + 1; k < n; k++) { // if the condition is matched a[i] < a[k] < // a[j], if (a[k] < a[j] && a[k] > a[i]) { return true; } } } } // if not found the condition to be true, return false; } public static void main(String[] args) { int[] arr = { 4, 7, 11, 5, 13, 2 }; int N = arr.length; if (recreationalSpot(arr, N)) { System.out.println("True"); } else { System.out.println("False"); } }} |
Python
# function to find if the pattern existsdef recreationalSpot(a, n): # first loop for possible values of i, for i in range(n): # second loop for possible values of j, for each i, for j in range(i + 1, n): # third loop for possible values of k, for each # value of j and i, for k in range(j + 1, n): # if the condition is matched a[i] < a[k] < # a[j], if a[k] < a[j] and a[k] > a[i]: return True # if not found the condition to be true, return Falsearr = [4, 7, 11, 5, 13, 2]N = len(arr)if recreationalSpot(arr, N): print("True")else: print("False") |
Javascript
// function to find if the pattern existsfunction recreationalSpot(a, n) { // first loop for possible values of i, for (let i = 0; i < n; i++) { // second loop for possible values of j, for each i, for (let j = i + 1; j < n; j++) { // third loop for possible values of k, for each // value of j and i, for (let k = j + 1; k < n; k++) { // if the condition is matched a[i] < a[k] < // a[j], if (a[k] < a[j] && a[k] > a[i]) { return true; } } } } // if not found the condition to be true, return false;}const arr = [4, 7, 11, 5, 13, 2];const N = arr.length;if (recreationalSpot(arr, N)) { console.log("True");} else { console.log("False");} |
Output
True
Time Complexity: O(N3).
Auxiliary Space: O(1).
Efficient Approach: The problem can be solved using the following idea:
Traverse the array from N-1 to 0 and check for every ith element if the greatest element on the right which is smaller than ith element is greater than the smallest element on the left of i then true else false.
To find the greatest element smaller than ith element we can use Next Greater Element
Follow the steps mentioned below to implement the idea:
- Create a vector small[].
- Traverse the array arr[] and maintain a min value that is the smallest value of arr[0, . . ., i].
- If there is no element smaller than Arr[i] store -1 else store min.
- Initialize an empty stack (say S). Run a loop from N-1 to 0:
- If stack is not empty and top element in stack <= small[i], then pop the element;
- If stack is not empty and small[i] < Top element in stack < arr[i] then return true.
- Otherwise, push arr[i] into stack.
- If the condition is not satisfied, return false.
Below is the implementation of the above approach:
C++
// C++ code to implement the above approach#include <bits/stdc++.h>using namespace std;// Function to find if the pattern existbool recreationalSpot(int arr[], int n){ vector<int> small; // min1 is used to keep track of minimum // element from 0th index to current index int min1 = arr[0]; for (int i = 0; i < n; i++) { if (min1 >= arr[i]) { min1 = arr[i]; // If the element itself is smaller than // all the elements on left side // then we push -1 small.push_back(-1); } else { // Push that min1; small.push_back(min1); } } // Initialise empty stack stack<int> s; // Looping from last index to first index // don't consider the possibility of 0th index // because it doesn't have left elements for (int i = n - 1; i > 0; i--) { // Pops up until either stack is empty or // top element greater than small[i] while (!s.empty() && s.top() <= small[i]) { s.pop(); } // Checks the conditions that top element // of stack is less than arr[i] // If true return true; if (!s.empty() && small[i] != -1 && s.top() < arr[i]) return true; s.push(arr[i]); } return false;}// Driver Codeint main(){ int arr[] = { 4, 7, 11, 5, 13, 2 }; int N = sizeof(arr) / sizeof(arr[0]); // Function Call if (recreationalSpot(arr, N)) { cout << "True"; } else { cout << "False"; } return 0;} |
Java
// Java code to implement the above approachimport java.io.*;import java.util.*;class GFG { // Function to find if the pattern exist static boolean recreationalSpot(int[] arr, int n) { List<Integer> small = new ArrayList<>(); // min1 is used to keep track of minimum element // from 0th index to current index int min1 = arr[0]; for (int i = 0; i < n; i++) { if (min1 >= arr[i]) { min1 = arr[i]; // If the element itself is smaller than all // the elements on left side then we push // -1. small.add(-1); } else { // Add that min1; small.add(min1); } } // Initialize empty stack Stack<Integer> s = new Stack<>(); // Looping from last index to first index don't // consider the possibility of 0th index because it // doesn't have left elements for (int i = n - 1; i > 0; i--) { // Pop's up until either stack is empty or top // element greater than small[i] while (!s.isEmpty() && s.peek() <= small.get(i)) { s.pop(); } // Checks the conditions that top element of // stack is less than arr[i] If true, then // return true; if (!s.isEmpty() && small.get(i) != -1 && s.peek() < arr[i]) { return true; } s.push(arr[i]); } return false; } public static void main(String[] args) { int[] arr = { 4, 7, 11, 5, 13, 2 }; int N = arr.length; // Function call if (recreationalSpot(arr, N)) { System.out.print("True"); } else { System.out.print("False"); } }}// This code is contributed by lokeshmvs21. |
Python3
# Python3 code to implement the above approach# Function to find if the pattern existdef recreationalSpot(arr, n) : small = []; # min1 is used to keep track of minimum # element from 0th index to current index min1 = arr[0]; for i in range(n) : if (min1 >= arr[i]) : min1 = arr[i]; # If the element itself is smaller than # all the elements on left side # then we push -1 small.append(-1); else : # Push that min1; small.append(min1); # Initialise empty stack s = []; # Looping from last index to first index # don't consider the possibility of 0th index # because it doesn't have left elements for i in range(n - 1, 0, -1) : # Pops up until either stack is empty or # top element greater than small[i] while (len(s) != 0 and s[-1] <= small[i]) : s.pop(); # Checks the conditions that top element # of stack is less than arr[i] # If true return true; if (len(s) != 0 and small[i] != -1 and s[-1] < arr[i]) : return True; s.append(arr[i]); return False;# Driver Codeif __name__ == "__main__" : arr = [ 4, 7, 11, 5, 13, 2 ]; N = len(arr); # Function Call if (recreationalSpot(arr, N)) : print("True"); else : print("False"); # This code is contributed by AnkThon |
C#
// C# program to of the above approachusing System;using System.Linq;using System.Collections;using System.Collections.Generic;class GFG { // Function to find if the pattern exist static bool recreationalSpot(int[] arr, int n) { List<int> small = new List<int>(); // min1 is used to keep track of minimum element // from 0th index to current index int min1 = arr[0]; for (int i = 0; i < n; i++) { if (min1 >= arr[i]) { min1 = arr[i]; // If the element itself is smaller than all // the elements on left side then we push // -1. small.Add(-1); } else { // Add that min1; small.Add(min1); } } // Initialize empty stack Stack s = new Stack(); // Looping from last index to first index don't // consider the possibility of 0th index because it // doesn't have left elements for (int i = n - 1; i > 0; i--) { // Pop's up until either stack is empty or top // element greater than small[i] while (s.Count > 0 && arr[(int)s.Peek()] <= small[i]) { s.Pop(); } // Checks the conditions that top element of // stack is less than arr[i] If true, then // return true; if (s.Count > 0 && small[i] != -1 && Convert.ToInt32(s.Peek()) < arr[i]) { return true; } s.Push(arr[i]); } return false; } // Driver Code public static void Main() { int[] arr = { 4, 7, 11, 5, 13, 2 }; int N = arr.Length; // Function call if (recreationalSpot(arr, N)) { Console.Write("True"); } else { Console.Write("False"); } }}// This code is contributed by sanjoy_62. |
Javascript
//Javascript code to implement the above approach<script>// Function to find if the pattern exist function recreationalSpot(arr, n) { small = []; // min1 is used to keep track of minimum // element from 0th index to current index let min1 = arr[0]; for(let i = 0; i < n; i++) { if (min1 >= arr[i]) { min1 = arr[i]; // If the element itself is smaller than // all the elements on left side // then we push -1 small.push(-1); } else { // Push that min1; small.push(min1); } } // Initialise empty stack s = []; // Looping from last index to first index // don't consider the possibility of 0th index // because it doesn't have left elements for (let i = n - 1; i > 0; i--) { // Pops up until either stack is empty or // top element greater than small[i] while (s.length>0 && s[s.length-1] <= small[i]) { s.pop(); } // Checks the conditions that top element // of stack is less than arr[i] // If true return true; if (s.length>0 && small[i] != -1 && s[s.length-1] < arr[i]) return true; s.push(arr[i]); } return false; } // Driver Code let arr = [ 4, 7, 11, 5, 13, 2 ]; let N = arr.length; // Function Call if (recreationalSpot(arr, N) == true) { console.log("True"); } else { console.log("False"); }</script>//This code is contributed by Abhijeet Kumar(abhijeet19403) |
Output
True
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!
