hard20 pts · first answer countsstacks-and-queues

Detecting a 132 pattern in O(n)

You must find whether an array has indices i < j < k with nums[i] < nums[k] < nums[j], a "132 pattern". What is the standard O(n) approach?

A.Sort a copy, then binary search for each candidate middle valueB.Scan right to left with a stack, keeping the largest popped valueC.Keep a min-heap of every value seen so far and poll as you goD.Use two pointers moving inward from both ends of the array

Discussion 0

Join free to post in the discussion.

Detecting a 132 pattern in O(n)

Discussion 0

Related questions