Data Modelling & AI Data Structure & Algorithm

Find 132 Pattern from given Array

23 June 2025

0

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 exists
bool 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 Code
int 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 exists
def 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 False
 
arr = [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 exists
function 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(N³).
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 i^th element if the greatest element on the right which is smaller than i^th element is greater than the smallest element on the left of i then true else false.

To find the greatest element smaller than i^th 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 exist
bool 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 Code
int 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 approach
 
import 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 exist
def 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 Code
if __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 approach
using 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).

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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!

Find 132 Pattern from given Array

C++

Java

Python

Javascript

C++

Java

Python3

C#

Javascript

From Word2Vec to LLM2Vec: How to Choose the Right Embedding Model for RAG

How to Debug Slow Search Requests in Milvus

When Context Engineering Is Done Right, Hallucinations Can Be the Spark of AI Creativity

LEAVE A REPLY Cancel reply

Most Popular

Google TV wants to take your video-watching experience to the next level with a bunch of AI features

I asked NotebookLM to analyze my emails, notes, and chats — and I was surprised by the results

Google Docs wants to bring Gemini’s writing chops to Android

The single best Pixel feature that turned me into a power user

EDITOR PICKS

Google TV wants to take your video-watching experience to the next level with a bunch of AI features

I asked NotebookLM to analyze my emails, notes, and chats — and I was surprised by the results

Google Docs wants to bring Gemini’s writing chops to Android

POPULAR POSTS

Google TV wants to take your video-watching experience to the next level with a bunch of AI features

I asked NotebookLM to analyze my emails, notes, and chats — and I was surprised by the results

Google Docs wants to bring Gemini’s writing chops to Android

POPULAR CATEGORY

ABOUT US

FOLLOW US