Medium

132 Pattern

LAB

Return true if nums contains indices i < j < k such that nums[i] < nums[k] < nums[j].

EXAMPLES

Example 1

Input
{
  "nums": [
    3,
    1,
    4,
    2
  ]
}

Output
true

FUNCTION SHAPE

nums: intArray→bool

SOLUTION NOTE

Fix the middle index j. The segment tree tracks values to the right of j; query whether any right-side value lies strictly between the prefix minimum on the left and nums[j].

Reveal reference solution +

pythonREFERENCE

from bisect import bisect_left, bisect_right

def find132pattern(self, nums: List[int]) -> bool:
    n = len(nums)
    if n < 3:
        return False

    prefix_min = [0] * n
    prefix_min[0] = nums[0]
    for i in range(1, n):
        prefix_min[i] = min(prefix_min[i - 1], nums[i])

    values = sorted(set(nums))
    rank = {v: i for i, v in enumerate(values)}
    tree = SegTree([0] * len(values), 0, len(values) - 1)

    # Tree stores frequencies of candidate nums[k] to the right of j.
    for num in nums[2:]:
        r = rank[num]
        tree.update(r, tree.query(r, r) + 1)

    for j in range(1, n - 1):
        lo = bisect_right(values, prefix_min[j - 1])
        hi = bisect_left(values, nums[j]) - 1
        if lo <= hi and tree.query(lo, hi) > 0:
            return True

        r = rank[nums[j + 1]]
        tree.update(r, tree.query(r, r) - 1)

    return False

TimeO(n log n)

SpaceO(n)

Open on LeetCode ↗