132 pattern

XXX. 132 Pattern

Stack

Greedy

Problem Statement:

Given an array of n integers nums, determine if there exists a 132 pattern in the array. A 132 pattern consists of three integers nums[i], nums[j], and nums[k] such that:

• i < j < k
• nums[i] < nums[k] < nums[j]

Return true if there is a 132 pattern, otherwise return false.

Approach 1: Using Min Array and Stack

1. Create an array min to track the smallest element from the start up to each index. This represents the potential nums[i].
2. Iterate backward through the array to evaluate potential nums[j] and nums[k] combinations.
3. Maintain a stack to store potential nums[k] candidates in decreasing order.
4. For each element:
   • Skip it if it's not greater than min[i] (no valid nums[j] possible).
   • Pop elements from the stack that are less than or equal to min[i] since they cannot form valid nums[k].
   • If the stack's top element is smaller than the current value, a valid 132 pattern is found.

Java Implementation (Min Array + Stack):

// Solution using min array and stack
public boolean find132pattern(int[] nums) {
    if (nums.length < 3) return false; // Less than 3 elements cannot form a 132 pattern

    // Min array to store the smallest value from the start up to each index
    int[] min = new int[nums.length];
    min[0] = nums[0]; // Initialize the first element as the smallest
    Stack stack = new Stack<>(); // Stack to store potential nums[k] values

    // Build the min array
    for (int i = 1; i < nums.length; i++) 
        min[i] = Math.min(min[i - 1], nums[i]); // Track the smallest element up to index i

    // Traverse the array backward
    for (int j = nums.length - 1; j >= 0; j--) {
        // Skip if nums[j] <= min[j] because nums[i] < nums[j] must hold
        if (nums[j] <= min[j]) continue;

        // Remove elements from the stack that are <= min[j]
        while (!stack.isEmpty() && stack.peek() <= min[j]) 
            stack.pop();

        // If the stack's top is less than nums[j], we found a valid 132 pattern
        if (!stack.isEmpty() && stack.peek() < nums[j]) 
            return true;

        // Push the current element onto the stack as a potential nums[k]
        stack.push(nums[j]);
    }

    return false; // No valid 132 pattern found
}
        

Approach 2: Greedy with Optimized Stack

1. Iterate backward through the array to ensure all potential nums[k] values are processed before the current index.
2. Maintain a variable third to track the maximum valid value for nums[k].
3. Use a stack to store candidates for nums[j] in decreasing order.
4. For each element:
   • Return true if it's less than third, indicating a valid 132 pattern.
   • Pop elements from the stack and update third if the current element is greater than the stack's top.
   • Push the current element onto the stack as a new candidate for nums[j].

Java Implementation (Greedy + Optimized Stack):

// Optimized greedy solution
public boolean find132pattern(int[] nums) {
    int third = Integer.MIN_VALUE; // Initialize the maximum valid nums[k]
    Stack stack = new Stack<>(); // Stack to store nums[j] candidates

    // Traverse the array backward
    for (int i = nums.length - 1; i >= 0; i--) {
        // If nums[i] is less than the third value, we found a valid 132 pattern
        if (nums[i] < third) return true;

        // Pop elements from the stack that are smaller than nums[i]
        // Update the third value as the largest popped element
        while (!stack.isEmpty() && nums[i] > stack.peek()) 
            third = stack.pop();

        // Push the current element onto the stack as a nums[j] candidate
        stack.push(nums[i]);
    }

    return false; // No valid 132 pattern found
}
        

Key Insights:

• Approach 1: The min array ensures that potential nums[i] values are precomputed, making the logic easier to implement.
• Approach 2: Greedily updating third avoids the need for additional arrays, focusing on reducing unnecessary overhead.
• Both approaches leverage the stack to efficiently find valid nums[j] and nums[k] candidates.

Complexity Analysis:

Time Complexity: O(n) for both solutions.
Space Complexity:

• Approach 1: O(n) for the min array and stack.
• Approach 2: O(n) for the stack.