456. 132 Pattern

Problem Description

Given an array of integers nums, find if there exists a subsequence of length 3 that follows the 132 pattern, where nums[i] < nums[k] < nums[j] and i < j < k. Return true if such a pattern exists, otherwise return false.

Solution Approach 1: Monotonic Stack

This approach uses a monotonic stack to efficiently identify the 132 pattern. The algorithm iterates through the array from right to left.

1. Initialization: A stack stk is used to store potential candidates for the '2' in the 132 pattern, and a variable vk keeps track of the maximum value encountered so far that could be the '3' in the 132 pattern. Initially, vk is set to negative infinity.

2. Iteration: The code iterates through the nums array from right to left.

   • Check for 132: If the current number x is less than vk, it means a 132 pattern has been found (x is '1', vk is '3', and there's a larger number encountered earlier that is '2'). The function immediately returns true.

   • Update Stack: While the stack is not empty and the top element of the stack is less than the current number x, it implies that the top element can potentially be the '3' in the 132 pattern if the current number is the '2'. Thus, the top element is popped and assigned to vk to update the maximum possible '3'.

   • Push: The current number x is pushed onto the stack. This ensures the stack maintains a decreasing order from bottom to top.

3. Return False: If the loop completes without finding a 132 pattern, the function returns false.

Time and Space Complexity Analysis (Solution 1)

• Time Complexity: O(n), where n is the length of the input array. The algorithm iterates through the array once. While there's a nested loop within the while condition, in the worst-case scenario, each element is pushed and popped from the stack at most once, resulting in a linear time complexity.

• Space Complexity: O(n) in the worst case, as the stack could potentially store all elements of the array if the input array is strictly decreasing.

Solution Approach 2: Binary Indexed Tree and Binary Search

This approach uses a Binary Indexed Tree (BIT) and binary search for a more sophisticated solution. The core idea is to efficiently count the number of elements within a specific range that could form the '2' in the 132 pattern.

1. Sort and Deduplicate: The input array nums is sorted and deduplicated to get a unique sorted array s.

2. Precompute Minimum: An array left stores the minimum value up to each index in nums.

3. Binary Indexed Tree: A BIT is used to store the frequency of elements in s.

4. Iteration: The algorithm iterates through nums from right to left. For each element:

   • Binary search is used to locate the indices (x and y) of the current element and the minimum element seen so far in s.
   • Query the BIT to determine if there are any elements between y and x that could act as the '2' (using tree.query(x - 1) > tree.query(y)).
   • Update the BIT with the current element.

Time and Space Complexity Analysis (Solution 2)

• Time Complexity: O(n log n), where n is the length of the input array. The sorting and binary search operations dominate, leading to the logarithmic factor. The BIT updates and queries take O(log n) time.

• Space Complexity: O(n), mainly due to the left array, the BIT, and the sorted unique array s.

Code Implementation (Solution 1 - Monotonic Stack)

Python:

class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        vk = float('-inf')
        stk = []
        for x in nums[::-1]:
            if x < vk:
                return True
            while stk and stk[-1] < x:
                vk = stk.pop()
            stk.append(x)
        return False

Java:

class Solution {
    public boolean find132pattern(int[] nums) {
        int vk = Integer.MIN_VALUE;
        Deque<Integer> stk = new ArrayDeque<>();
        for (int i = nums.length - 1; i >= 0; --i) {
            if (nums[i] < vk) {
                return true;
            }
            while (!stk.isEmpty() && stk.peek() < nums[i]) {
                vk = stk.pop();
            }
            stk.push(nums[i]);
        }
        return false;
    }
}

(Other languages are similar in structure, adapting data structures as needed.)

Code Implementation (Solution 2 - Binary Indexed Tree) - (Python Example)

import bisect
class BinaryIndexedTree:
    # ... (BIT implementation as described above) ...
 
class Solution:
    # ... (Solution using BIT and binary search as described above) ...

The full implementations for Solution 2 are provided in the original response but are significantly more extensive due to the complexity of Binary Indexed Trees. I've included a skeletal structure for the Python version to illustrate the key components. Remember to implement the BinaryIndexedTree class completely.

Choose the solution that best suits your needs. The monotonic stack approach (Solution 1) is generally preferred due to its simpler implementation and linear time complexity, making it efficient for large input arrays. Solution 2 might be considered if you need to explore more advanced data structures and algorithms.