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.
Follow up: The O(n^2) is trivial, could you come up with the O(n logn) or the O(n) solution?
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.length -
1 <= n <= 104 -
-109 <= nums[i] <= 109
class Solution {
public boolean find132pattern (int[] nums) {
Stack <Integer> stack = new Stack ();
int second = Integer.MIN_VALUE;
for (int i = nums.length - 1; i >= 0; i--) {
if (nums [i] < second)
return true;
while (!stack.isEmpty() && nums [i] > stack.peek ())
second = stack.pop ();
stack.push (nums [i]);
}
return false;
}
}The above problem can be solved using Brute Force Approach, solution will be accepted but we need to optimize the solution. The above given solution is optimized one.
1) Create a empty stack of Integer type.
2) Set a second value to Integer minimum.
3) a) If current num is less than second then return true.
b) If stack is not empty and current num is greater than top of stack, then set second to value which is popped from stack.
c) Push a num to stack
4) If all numbers are traversed and exit from loop, then return false.
[Ideology] Take 132 pattern. Assume 3 as peek element of stack. Then with help of stack, we can find 32 pattern. After with help of for loop iteration, we can find 1 pattern.
-----/\-----/\------/\------/\------/\-----
Click Follow button to receive latest updates from us instantly.
:-) ..Happy Coding... :-)
Comments
Post a Comment