🌱 Keegan's Digital Garden

456. 132 Pattern

2 min read

📝 Problem Details

💭What Were My Initial Thoughts?

rules:
i < j < k
nums[i] < nums[k] < nums[j]

~ originally thought a sliding window approach could work (does not work since the input array is not sorted and the order of elements matters for the context of the problem)

----------------------------------------------------------
- To identify the 132 pattern:
    - nums[k]: The middle value should be tracked dynamically.
    - nums[j]: Should always be larger than nums[k].
    - nums[i]: Should always be smaller than nums[k].

- Traversing the array in reverse allows us to use a stack to efficiently track potential nums[k] values.

🤔What Did I Struggle With?

~ dont think I was able to come up with an optimal solution for this problem during the mock interview

💡 Explanation of Solution

- traverse the array from right to left
- use a stack to keep track of potential nums[k] values (elements that are smaller than the current nums[j])
- keep track of the current maximum nums[k] found so far
- for each element nums[i] during the traversal
	- If nums[i] < nums[k], the 132 pattern is found
	- Push nums[i] onto the stack if it might serve as a potential nums[k] for future iterations.

⌛ Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n) due to the use of the monotonic stack to store lesser elements

💻 Implementation of Solution

bool find132pattern(vector<int>& nums) {
    int n = nums.size();
    if (n < 3) return false; // Not enough elements for a pattern
 
    stack<int> stk; // Monotonic stack to track potential nums[k]
    int second = INT_MIN; // nums[k], the second-largest in the pattern
 
    for (int i = n - 1; i >= 0; --i) {
        if (nums[i] < second) {
            return true; // nums[i] < nums[k]
        }
 
        while (!stk.empty() && nums[i] > stk.top()) {
            second = stk.top(); // Update nums[k]
            stk.pop();
        }
 
        stk.push(nums[i]); // Push current element as a potential nums[j]
    }
 
    return false;
}

Graph View