456. 132 Pattern
132 Pattern
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.
Example 1:
Input: nums = [1,2,3,4] Output: false Explanation: There is no 132 pattern in the sequence.
Example 2:
Input: nums = [3,1,4,2] Output: true Explanation: There is a 132 pattern in the sequence: [1, 4, 2].
Example 3:
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.length1 <= n <= 2 * 105-109 <= nums[i] <= 109
Here are 3 approaches to solving this problem in Javascript.
Approach 1) BF with O(n^3)
It's easy to use 3 loops to find 3 elements which are 132 pattern, but the time complexity is O(n^3), so it wouldn't be accepted as a timeout.
/**
* @param {number[]} nums
* @return {boolean}
*/
var find132pattern = function(nums) {
len = nums.length;
if(len <= 2){
return false;
}
for (let i = 0; i < len - 2; i++) {
for (let j = i + 1; j < len - 1; j++) {
for (let k = j + 1; k < len; k++) {
if (nums[i] < nums[k] && nums[k] < nums[j]) {
return true;
}
}
}
}
return false;
};
Complexity analysis.
Time Complexity
We are traversing through the complete array which needs O(N^3).
Space Complexity
We are not using any extra space, hence space complexity is O(1).
Approach 2) BF O(n^2)
Noticed that nums[j] is the peak of the 3 elements, suppose the current element is nums[j], we have to find the element nums[k] that is smaller than nums[j] after j, and the element nums[i] that is smaller than nums[k] before j.
Explanation:
Scan left from j to 0, 0 <= i < j, whether there is num[i] < nums[j], update the mininum leftMin;
Scan right from j to the end, j + 1 <= k < len, whether there is num[k] < nums[j], update the maxinum rightMax;
If exists and leftMin < rightMax, return true.
Let's coding it.
/**
* @param {number[]} nums
* @return {boolean}
*/
var find132pattern = function(nums) {
let len = nums.length;
if (len < 3) {
return false;
}
for (let j = 1; j < len - 1; j++) {
let leftMin = Number.MAX_VALUE;
let leftFlag = false;
for (let i = j - 1; i >= 0; i--) {
if (nums[i] < nums[j]) {
leftFlag = true;
leftMin = Math.min(leftMin, nums[i]);
}
}
let rightMax = Number.MIN_VALUE;
let rightFlag = false;
for (let k = j + 1; k < len; k++) {
if (nums[k] < nums[j]) {
rightFlag = true;
rightMax = Math.max(rightMax, nums[k]);
}
}
if (leftFlag && rightFlag && leftMin < rightMax) {
return true;
}
}
return false;
};
Complexity analysis.
Time Complexity
We are traversing through the complete array which needs O(N^2).
Space Complexity
We are not using any extra space, hence space complexity is O(1).
Approach 3) Monotonic Stack
We can use a stack to store the element of the array from the back to front, find nums[k] in the stack, and then continue to scan forward to find nums[i].
The stack must store elements with a larger index and a smaller value than nums[j].
The process is like this:
Explanation:
Scanning from the back to the front, if the current element nums[i] is larger than the top of the stack, which means nums[i] may be the nums[j] we are looking for;
Pop all the elements in the stack that are smaller than it. These elements are the the nums[k], and the last pop-up is the maximum qualified nums[k].
If this num[k] is larger than the nums[i] scanned forward, we find the answer.
Let's coding it.
/**
* @param {number[]} nums
* @return {boolean}
*/
var find132pattern = function(nums) {
let len = nums.length;
if (len < 3) {
return false;
}
let stk = new Stack();
let k = -1;
for (let i = len - 1; i >= 0; i--) {
if (k > -1 && nums[k] > nums[i]) {
return true;
}
while (!stk.isEmpty() && nums[i] > nums[stk.peek()]) {
k = stk.pop();
}
stk.push(i);
}
return false;
};
class Stack {
constructor() {
this.stack = []
}
push(a) {
this.stack.push(a)
}
pop() {
return this.stack.pop()
}
peek() {
return this.stack[this.stack.length - 1]
}
size() {
return this.stack.length
}
isEmpty() {
return this.stack.length == 0
}
}Complexity analysis.
Time Complexity
We are traversing through the complete array which needs O(N).
Space Complexity
We are using stack as an extra space, hence space complexity is O(N).
Resources:
That’s all folks! In this post, we solved LeetCode problem #456. 132 Pattern
I hope you have enjoyed this post. Feel free to share your thoughts on this.
You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.
In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!
Comments
Post a Comment