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.
2. Iterate backward through the array and maintain a stack to store potential nums[k] values.
3. 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].
   • 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;
    int[] min = new int[nums.length];
    min[0] = nums[0];
    Stack stack = new Stack<>();

    // Build the min array
    for (int i = 1; i < nums.length; i++) 
        min[i] = Math.min(min[i - 1], nums[i]);

    // Traverse the array backward
    for (int j = nums.length - 1; j >= 0; j--) {
        if (nums[j] <= min[j]) continue; // nums[i] must be < nums[j]
        while (!stack.isEmpty() && stack.peek() <= min[j]) stack.pop();
        if (!stack.isEmpty() && stack.peek() < nums[j]) return true;
        stack.push(nums[j]);
    }
    return false;
}
        

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.

Java Implementation (Greedy + Optimized Stack):

// Optimized greedy solution
public boolean find132pattern(int[] nums) {
    int third = Integer.MIN_VALUE;
    Stack stack = new Stack<>();

    for (int i = nums.length - 1; i >= 0; i--) {
        if (nums[i] < third) return true;
        while (!stack.isEmpty() && nums[i] > stack.peek()) 
            third = stack.pop();
        stack.push(nums[i]);
    }
    return false;
}
        

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.