Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 456 with 18 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 456 # by problem number
lcpy gen -s pattern_132 # by problem name
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.
Input: nums = [1,2,3,4]
Output: false
Explanation: There is no 132 pattern in the sequence.
Input: nums = [3,1,4,2]
Output: true
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].
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].
n == nums.length1 <= n <= 2 * 10^5-10^9 <= nums[i] <= 10^9class Solution:
# Time: O(n)
# Space: O(n)
def find_132pattern(self, nums: list[int]) -> bool:
if len(nums) < 3:
return False
stack: list[int] = []
third = float("-inf")
for i in range(len(nums) - 1, -1, -1):
if nums[i] < third:
return True
while stack and stack[-1] < nums[i]:
third = stack.pop()
stack.append(nums[i])
return False
| Time | Space |
|---|---|
| O(n) | O(n) |