Title:

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.

1. For each element in nums:
Delta = nums [i+1] - nums [i]
2. 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 conditions hold return true.
3. 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.
4. 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.
5. 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; } } ```