LeetCode Entry

456. 132 Pattern

30.09.2023 medium 2023 kotlin

132 pattern in array

456. 132 Pattern medium blog post substack

image.png

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