Thread: Understanding the 132 Pattern Problem | Monotonic Stack | N^3 -> N Complexity

1. What Are We Talking About?

The 132 pattern is a problem where we need to find a subsequence of three numbers in an array (nums[i], nums[j], nums[k]) such that:

Indices are in order: i < j < k
Values satisfy: nums[i] < nums[k] < nums[j]

Example 1:

Input: nums = [1,2,3,4]
Output: false
Explanation: There is no 132 pattern in the sequence.

Example 2:

Input: nums = [3,1,4,2]
Output: true
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].

The name "132" comes from the relative order of the three numbers:

1 (smallest): nums[i]

3 (largest): nums[j]

2 (middle): nums[k]

2. Real-World Applications

While the 132 pattern might seem abstract, it has real-world applications in:

1. Stock Market Analysis:

• Identifying patterns in stock prices where a low point (nums[i]) is followed by a high point (nums[j]) and then a middle point (nums[k]).

1. Data Sequence Analysis:

• Detecting specific trends or anomalies in time-series data.

1. Algorithm Design:

• Understanding and solving similar subsequence problems efficiently.

3. Brute-Force Approach

The brute-force approach involves checking all possible triplets (i, j, k) in the array to see if they satisfy the 132 pattern.

1. Use three nested loops:

• Outer loop for i (first number).
• Middle loop for j (second number).
• Inner loop for k (third number).

1. For each triplet (i, j, k), check if:

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

for (let i = 0; i < nums.length; i++) {
  for (let j = i + 1; j < nums.length; j++) {
    for (let k = j + 1; k < nums.length; k++) {
      if (nums[i] < nums[k] && nums[k] < nums[j]) {
        return true; // Found a 132 pattern
      }
    }
  }
}
return false; 

Complexity:

1. Time: O(n3)
2. Space: O(1)

4. Thinking Process for the Optimised Approach

The brute-force approach is too slow for large arrays. To optimize, we need to:

1. Reduce the number of comparisons:

• Avoid checking all possible triplets.

1. Use additional data structures:

• A monotonic stack can help track potential nums[k] values efficiently.

1. Traverse the array strategically:

• Traverse from right to left to keep track of potential nums[k] values.

Why the Monotonic Stack Works

A monotonic stack is a stack where the elements are always in increasing or decreasing order. In this problem, we use a decreasing stack to keep track of potential nums[k] values.

1. Traverse from Right to Left:
2. This allows us to keep track of potential nums[k] values in the stack.
3. Use a Stack:
4. The stack stores potential nums[k] values in increasing order (monotonic stack).
5. Update nums_k:
6. Whenever we find a nums[j] that is greater than the top of the stack, we update nums_k to the top of the stack. This ensures that nums_k is the largest valid nums[k] found so far.
7. Check for the 132 Pattern:
8. If nums[j] < nums_k, it means we have found a valid nums[i] (since nums[i] < nums[k] < nums[j]).

5. Approach to Code:

1. Stack to store potential nums[k] values
2. Variable to store the largest valid nums[k]
3. Traverse the array from right to left
4. If nums[i] < nums_k, we have found a valid 132 pattern
5. While the stack is not empty and the top of the stack is less than nums[i]
6. we are maintaining monotonic stack in decreasing order, we need to maintain an order
7. while (stack.length > 0 && stack[stack.length - 1] < nums[j]) {
8. Update nums_k to the top of the stack (this is a potential nums[k])
9. Push nums[j] onto the stack
10. If no valid pattern is found, return false

var find132pattern = function(nums) {
  const stack = [];
  let nums_k = -Infinity;

  for (let j = nums.length - 1; j >= 0; j--) {
    if (nums[j] < nums_k) {
      return true;
    }
    while (stack.length > 0 && stack[stack.length - 1] <      
         nums[j]) {
      nums_k = stack.pop();
    }
    stack.push(nums[j]);
  }
  return false;
};

Example to Illustrate

Let’s take the array [5, 4, 3, 2, 1, 6] and analyze the operations:

1. Initialize:
2. Stack: []
3. nums_k = -Infinity
4. Traverse from right to left:
5. j = 5, nums[j] = 6:
6. Push 6 onto the stack.
7. Stack: [6]
8. j = 4, nums[j] = 1:
9. Push 1 onto the stack.
10. Stack: [6, 1]
11. j = 3, nums[j] = 2:
12. Pop 1 from the stack (since 1 < 2).
13. Push 2 onto the stack.
14. Stack: [6, 2]
15. j = 2, nums[j] = 3:
16. Pop 2 from the stack (since 2 < 3).
17. Push 3 onto the stack.
18. Stack: [6, 3]
19. j = 1, nums[j] = 4:
20. Pop 3 from the stack (since 3 < 4).
21. Push 4 onto the stack.
22. Stack: [6, 4]
23. j = 0, nums[j] = 5:
24. Pop 4 from the stack (since 4 < 5).
25. Push 5 onto the stack.
26. Stack: [6, 5]
27. Result:
28. No 132 pattern found. Return false.

Time Complexity:

1. For loop takes N times
2. A nested while loop only executes when the stack top is less than current value.Total operation takes O(N)
3. Each element is pushed and popped exactly once.
4. The while loop only processes element that are already in the stack.
5. Once the element is popped it never processes them again.

So the time is for loop run N times i.e O(N), inner while loop total operation is O(N)

thus it runs for linear time of O(N)

Space Complexity:

O(n): The stack can store up to n