0456-132-pattern.rb

# frozen_string_literal: true

# 456. 132 Pattern
# Medium
# https://leetcode.com/problems/132-pattern

=begin
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.length
1 <= n <= 2 * 105
-109 <= nums[i] <= 109
=end

# @param {Integer[]} nums
# @return {Boolean}
deffind132pattern(nums)
stack=[]
minVal=nums[0]
(1...nums.size).eachdo |i|
while(!stack.empty?) && nums[i] >= stack[-1][0]
stack.pop
end
if(!stack.empty?) && nums[i] > stack[-1][1]
returntrue
end
stack.push([nums[i],minVal])
minVal=nums[i] < minVal ? nums[i] : minVal
end
false
end

# **************** #
# TEST #
# **************** #

require"test/unit"
classTest_find132pattern < Test::Unit::TestCase
deftest_
assert_equalfalse,find132pattern([1,2,3,4])
assert_equaltrue,find132pattern([3,1,4,2])
assert_equaltrue,find132pattern([-1,3,2,0])
end
end