Title:

132 Pattern

Link to LeetCode:

https://leetcode.com/problems/132-pattern/

Specification:

Given a sequence of n integers a1, a2, ..., an,

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.

Note: n will be less than 15,000.

Examples:

Example 1:

Input: [1, 2, 3, 4]

Output: False

Explanation: There is no 132 pattern in the sequence.

Example 2:

Input: [3, 1, 4, 2]

Output: True

Explanation: There is a 132 pattern in the sequence: [1, 4, 2].

Example 3:

Input: [-1, 3, 2, 0]

Output: True

Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].

Initial Code and Signature:

```
```
public interface PatternFinder {
public boolean find123Pattern (int [] nums);
}

Algorithm:

Main idea:

Look for a max peak shape , or

a max and min peak shape in the input stream.

- For each element in nums:

Delta = nums [i+1] - nums [i] - As soon as delta gets negative,

check for two criterion:

- an accumulative positive deltas is seen before.
- the absolute value of the seen negative delta is less than the accumulative positive deltas.

- If the negative delta is greater than the accumulative positive difference:
- Reset accumulative positive deltas to zero.
- Remember the min and max nums from the last seen accumulative positive deltas.
- If a positive delta is seen:
- Add it to positive accumulative deltas.
- If a negative delta has been seen before but the search process has not ended,

check whether nums [i] is greater than previous min and smaller than previous max.

If yes, return true. - Repeat (Go to 1-)

Run-Time Analysis:

GitHub Project:

Code:

```
```
/**
*
* @author Mahsa Sadi
*
* @since 2020 - 04 - 04
*
* License: Creative Commons
*
* Copyright by Mahsa Sadi
*
*/
public class PatternFinderV1 implements PatternFinder {
/**
* Problem: 132Pattern
*
*
*
* @see https://leetcode.com/problems/132-pattern/
*
*
* Description:
*
*
* Solution:
*
* Main idea:
*
* Look for a max peak shape , or
* a max and min peak shape in the input stream with the two following forms:
*
* "/"\" "/"\
* "/ "\ or "/ "\ "/
* "/ "/ "\ "/
* "\"/
*
*
* 1- For each element in nums:
*
* 2- Delta = nums [i+1] - nums [i]
*
* 3- As soon as delta gets negative,
* check for two criterion:
* 1- an accumulative positive deltas is seen before.
* 2- the absolute value of the seen negative delta is less than the accumulative positive deltas.
*
* If the conditions hold return true.
*
* 4- If the negative delta is greater than the accumulative positive difference:
* 1- reset accumulative positive deltas to zero.
* 2- remember the min and max nums from the last seen accumulative positive deltas.
*
* 5- If a positive delta is seen:
* 1- add it to positive accumulative deltas.
* 2- If a negative delta has been seen before but the search process has not ended
* check whether nums [i] is greater than previous min and smaller than previous max
*
* if yes, return true.
*
* 6- Repeat (Go to 1-)
*
*
*
*
*/
int accumulativePositiveDif = 0;
int previousMin, currentMin;
int previousMax, currentMax;
boolean twoMins;
@Override
public boolean find123Pattern(int[] nums) {
if (nums.length == 0)
return false;
currentMin = nums [0];
currentMax = nums [0];
for (int i = 1; i < nums.length; i++)
{
int delta = nums[i] - nums [i-1];
if ( delta >= 0 )
{
accumulativePositiveDif += delta;
if (twoMins && nums [i] > previousMin && nums [i] < previousMax)
return true;
}
else
{
if (Math.abs(delta) < accumulativePositiveDif)
return true;
else
{ if (accumulativePositiveDif != 0)
{
accumulativePositiveDif = 0;
previousMin = currentMin;
previousMax= currentMax;
twoMins = true;
}
}
}
if (currentMin > nums [i])
currentMin = nums [i];
if (currentMax < nums [i])
currentMax = nums [i];
}
return false;
}
}