30.09.2023
456. 132 Pattern medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/355
Problem TLDR
132
pattern in array
Intuition
If we slide the array from behind, we simplify the task to find the smallest element.
When searching for largest decreasing subsequence, we can use a monotonic Stack.
Approach
we must remember the popped element, as it is the second largest one
Complexity
Time complexity:
O(n)Space complexity:
O(1)
Code
fun find132pattern(nums: IntArray): Boolean {
val stack = Stack<Int>()
var lo = Int.MIN_VALUE
return (nums.lastIndex downTo 0).any { i ->
while (stack.isNotEmpty() && stack.peek() < nums[i]) lo = stack.pop()
stack.push(nums[i])
nums[i] < lo
}
}