132 Pattern

Given a sequence A of N integers , a 132 pattern is a subsequence Ai, Aj, Ak such that i < j < k and Ai < Ak < Aj. Design an algorithm that takes a list of N numbers as input and checks whether there is a 132 pattern in the list. You have to return 1 if there is a 132 pattern otherwise return 0.

Input Format:

First and only argument of input contains a single integer array A

Output Format:

Return a single integer 1 if 132 pattern is present, 0 otherwise

Constraints:

1 <= N <= 100000
INT_MIN <= A[i] <= INT_MAX

For Example:

Example Input 1:
    A = [1, 2, 3, 4]
Example Output 1:
    0
Explanation:
    There is no 132 pattern in the given input array.
Example Input 2:
    A = [2, 1, 6, 4]
Example Output 2:
    1
Explanation:
    The given input array has [2, 6, 4] and [1, 6, 4] as the 132 patterns in it.
NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.
Start solving 132 Pattern on Interview Code Editor
Sign Up
to access hints and editorial solutions for 132 Pattern

Discussion


Loading...
Click here to start solving coding interview questions