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.
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;
}
}