algoadvance

Leetcode 456. 132 Pattern

Problem Statement

Given an array of n integers nums, a 132 pattern is a subsequence of three integers nums[i], nums[j], and nums[k] such that i < j < k and nums[i] < nums[k] < nums[j]. Find whether any 132 pattern exists in nums.

Clarifying Questions

  1. Input Size: What is the range of values for n (the length of the array)?
  2. Value Range: What are the possible values for the integers in the array nums?
  3. Output: Should the function return a boolean indicating the presence of the pattern?

For the sake of this problem, we will assume:

Strategy

To find the 132 pattern, we need to find three indices i, j, and k such that:

A straightforward solution with three nested loops would be too slow (O(n^3) time complexity). Instead, we can use a more efficient approach with a combination of arrays/stacks to keep track of potential candidates for the 132 pattern.

Efficient Approach:

  1. Min Array: First, create an array minArray where minArray[i] stores the minimum value in nums from index 0 to i. This helps us keep track of the smallest value (candidate for nums[i]) before the current element.
  2. Traverse Backwards: Use a stack to keep track of potential nums[k] values (which must be less than the current nums[j] but greater than the minimum value up to that point).

Here’s a step-by-step outline:

  1. Create minArray such that minArray[i] is the minimum value in nums[0:i+1]
  2. Traverse the array from right to left (for j), maintaining a stack for possible values of nums[k]
  3. For each nums[j], ensure that we pop elements from the stack that are less than minArray[j] (as they cannot satisfy the 132 pattern condition)
  4. If we find a value in the stack which is greater than minArray[j] and less than nums[j], then we have found a valid 132 pattern.

Code

Here’s the Java code to implement this strategy:

import java.util.Stack;

public class Solution {
    public boolean find132pattern(int[] nums) {
        if (nums.length < 3) return false;

        // Step 1: Create minArray
        int[] minArray = new int[nums.length];
        minArray[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            minArray[i] = Math.min(minArray[i-1], nums[i]);
        }

        // Step 2: Traverse from right to left to find 132 pattern
        Stack<Integer> stack = new Stack<>();
        for (int j = nums.length - 1; j >= 0; j--) {
            if (nums[j] > minArray[j]) {
                while (!stack.isEmpty() && stack.peek() <= minArray[j]) {
                    stack.pop();
                }
                if (!stack.isEmpty() && stack.peek() < nums[j]) {
                    return true;
                }
                stack.push(nums[j]);
            }
        }

        return false;
    }
}

Time Complexity

This solution is efficient and should perform well for the given problem constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI