Given an array of n integers nums, a 132 pattern is a subsequence of three integers nums[i], nums[j] and nums[k]
such that i < j < k and nums[i] < nums[k] < nums[j].
Return true if there is a 132 pattern in nums, otherwise, return false.
Input: nums = [1,2,3,4]
Output: false
Explanation: There is no 132 pattern in the sequence.
Input: nums = [3,1,4,2]
Output: true
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].
Input: nums = [-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].
Constraints:
- n == nums.length
- 1 <= n <= 2 * 105
- -109 <= nums[i] <= 109
Contents
- Solution 1 - Using a Stack
The main idea behind this solution is, as per the problem statement i < j < k, so the indexes will be in increasing order, that is
as we loop through input array from left to right, current index will be k and previous indexes will be j and i.
So, the current number we are at is nums[k], so we need to identify a pair of numbers such that nums[i] < nums[k] < nums[j],
so we will be looking at previous number pairs, current number we are iterating nums[j] , minimum number found so far nums[i], so we will be constructing a
monotomically decreasing stack.
When we are at index k, previous index must be j and anything before that will be i, since we are are storing
current number, min number so far as a pair, these are nothing but, nums[j], nums[i] and this also satisfies the condition
nums[i] < nums[j], so all we have to do is, check if the current number we are it is greater than nums[i]
(second element from the pair of numbers that is top of stack) and the current number is also less than nums[j] (first element from the pair of numbers that is top of stack).
import java.util.Stack;
public class Find132Pattern {
static boolean find132pattern(int[] nums) {
Stack<int[]> stack = new Stack<>();
int currentMin = nums[0];
for(int i =1; i<nums.length; i++) {
int current = nums[i];
while(!stack.isEmpty() && current>=stack.peek()[0]) {
stack.pop();
}
if(!stack.isEmpty() && current <stack.peek()[0] && current > stack.peek()[1]) {
return true;
}
stack.push(new int[]{current, currentMin});
currentMin = Math.min(current, currentMin);
}
return false;
}
public static void main(String[] args) {
System.out.println(find132pattern(new int[]{3,1,4,2}));
System.out.println(find132pattern(new int[]{1,2,3,4}));
}
}
Complexity Analysis:
Time complexity: Time complexity for the solution will be O(n) where n is the length of input array nums.
Space complexity: O(n) for storing elements into stack.
Above implementations source code can be found at
GitHub link for Java code