Discover 132 Sample from given Array

Given an array arr[] of dimension N. The duty is to test if the array has 3 components in indices i, j and ok such that i < j < ok and arr[i] < arr[j] > arr[k] and arr[i] < arr[k].

Examples:

Enter: N = 6, arr[] = {4, 7, 11, 5, 13, 2}
Output: True
Rationalization: [4, 7, 5] suits the situation.

Enter: N = 4, arr[] = {11, 11, 12, 9}
Output: False
Rationalization: No 3 components match the given situation. 

Method: The issue could be solved utilizing the next thought:

Traverse the array from N-1 to 0 and test for each i^th factor if the best factor on the fitting which is smaller than i^th factor is larger than the smallest factor on the left of i then true else false. 

To seek out the best factor smaller than i^th factor we will use Subsequent Larger Aspect 

Comply with the steps talked about under to implement the concept:

• Create a vector small[]. 
• Traverse the array arr[] and preserve a min worth that’s the smallest worth of arr[0, . . ., i]. 
  • If there isn’t a factor smaller than Arr[i] retailer -1 else retailer min.
• Initialize an empty stack (say S). Run a loop from N-1 to 0:
  • If stack isn’t empty and high factor in stack <= small[i], then pop the factor;
  • If stack isn’t empty and small[i] < Prime factor in stack < arr[i] then return true.
  • In any other case, push arr[i] into stack.
• If the situation isn’t glad, return false.

Under is the implementation of the above method:

Time Complexity: O(N).
Auxiliary Area: O(N).