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]. Return true if there is a 132 pattern in nums, otherwise, return false.

Example

Clarifying Questions

  1. What is the range of values in the array nums?
  2. What is the length of the array?
  3. Are there any duplicate values in the array?
  4. Are there any specific constraints related to time & space complexity we need to consider for the solution?

If there are no specific constraints provided, we should aim for an efficient solution with a good balance between time and space complexity.

Strategy

To find the 132 pattern, we need to track three values such that nums[i] < nums[k] < nums[j] with i < j < k. Here’s a strategy to solve it efficiently:

  1. Maintain a Stack and Auxiliary Array:
    • Use a stack to keep track of possible candidates for nums[k] (the middle value).
    • Use an auxiliary array min_array to keep track of the minimum value up to the current index (potential nums[i]).
  2. Traverse the Array Backwards:
    • Traverse the array from right to left. This helps in efficiently maintaining potential candidates for nums[k] (since they need to be smaller than the preceding numbers as we look for a valid nums[j]).
  3. Find Potential k values while ensuring constraints:
    • While iterating, for each nums[j], we check if there’s a valid nums[k] in the stack such that nums[k] is greater than min_array[j] but less than nums[j].
    • Update the stack accordingly.

This approach ensures that we check each element multiple times in a controlled manner, leading to an efficient solution.

Code

#include <iostream>
#include <vector>
#include <stack>
#include <climits>

using namespace std;

bool find132pattern(vector<int>& nums) {
    int n = nums.size();
    if (n < 3) return false;
    
    // Create min_array to track the minimum value up to the current index
    vector<int> min_array(n);
    min_array[0] = nums[0];
    for (int i = 1; i < n; i++) {
        min_array[i] = min(min_array[i - 1], nums[i]);
    }
    
    // Use a stack to keep track of potential nums[k] candidates
    stack<int> stk;
    
    for (int j = n - 1; j >= 0; j--) {
        // Find a valid nums[k] that is greater than min_array[j] but less than nums[j]
        while (!stk.empty() && stk.top() <= min_array[j]) {
            stk.pop();
        }
        if (!stk.empty() && stk.top() < nums[j]) {
            return true;
        }
        // Add the current element nums[j] as a potential nums[k]
        stk.push(nums[j]);
    }
    
    return false;
}

Time Complexity

The overall time complexity of the solution is O(n), where n is the number of elements in the input array. This complexity arises because:

Space complexity is also O(n) due to the auxiliary space used for min_array and the stack.

With these details, the solution should efficiently determine if a 132 pattern exists in the given array.

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