132 Pattern

Problem Statement

In this problem, you are given an array of integers named nums. Your task is to determine if there exists at least one subsequence that follows the 132 pattern. A subsequence in this context is defined by three integers from the given array: nums[i], nums[j], nums[k], where the indices meet the condition i < j < k. The values at these indices must satisfy the pattern nums[i] < nums[k] < nums[j]. If such a subsequence exists, your function should return true; otherwise, it returns false.

Examples

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

Approach and Intuition

Understanding the 132 pattern requires visualizing or tracing through potential subsequences within the array, adhering to the index and value conditions. Our objective is to identify three integers where the first one is less than the third, and the third is less than the second, forming a peak-like structure. To clarify this approach, consider the examples provided:

Breakdown of Examples

Example 1

• Input: nums = [1,2,3,4]
• Output: false
• Explanation: Sequentially increasing or decreasing numbers cannot form a valid 132 pattern since no middle value can be both greater and lesser between two other values.

Example 2

• Input: nums = [3,1,4,2]
• Output: true
• Explanation: The subsequence [1, 4, 2] adheres to the 132 pattern because 1 < 2 < 4. Here 1 is nums[i], 4 is nums[j], and 2 is nums[k] fulfilling i < j < k.

Example 3

• Input: nums = [-1,3,2,0]
• Output: true
• Explanation: Several subsequences here meet the 132 criteria:
  • [-1, 3, 2] fits because -1 < 2 < 3
  • [-1, 3, 0] fits because -1 < 0 < 3
  • [-1, 2, 0] also fits since -1 < 0 < 2

Intuition behind Solution

To solve this problem efficiently:

1. Use a structure to maintain a record of possible values for nums[k]. You can use a stack, which keeps track of potential candidates for nums[k] as you iterate the array from right to left.
2. Continuously update the minimum possible value for nums[i] as you go through array elements.
3. For each element, check against the potential nums[k] values in the stack — ensuring that the current element can serve as nums[j], checking if it can form a valid pattern with some values behind it considering nums[i] and nums[k].

This combination of scanning and stack-based approach leverages past computations efficiently, attempting to optimize the nested iteration scenario, particularly under constraints where n can be very large.

This approach effectively manages complexity, navigating through numerous possible index combinations efficiently, which otherwise could escalate into a time-intensive process given large array inputs as stated in the constraints.

Solutions

class Solution {
public:
    bool check132pattern(vector<int>& elements) {
        int n = elements.size();
        if (n < 3) {
            return false;
        }
        vector<int> leftMin(n);
        leftMin[0] = elements[0];
    
        for (int i = 1; i < n; i++) {
            leftMin[i] = min(leftMin[i - 1], elements[i]);
        }
    
        for (int j = n - 1, k = n; j > 0; j--) {
            if (elements[j] <= leftMin[j]) continue;
            while (k < n && elements[k] <= leftMin[j]) k++;
            if (k < n && elements[k] < elements[j]) {
                return true;
            }
            elements[--k] = elements[j];
        }
        return false;
    }
};