The O(n) Club: Detecting 132 Patterns Faster Than Your Interviewer Can Blink

The O(n) Club: Detecting 132 Patterns Faster Than Your Interviewer Can Blink

⚡ TL;DR

Find three numbers in an array that say, “Look, I zigged when you expected a zag”—that’s a 132 Pattern. Brute force will give your CPU a meltdown (O(n³)), and your manager an ulcer. Want to pass interviews and impress your cat? Use a stack from the right. Quick peek:

// Please don't brute force this at work
for (int i = 0; i < n - 2; i++)
  for (int j = i + 1; j < n - 1; j++)
    for (int k = j + 1; k < n; k++)
      if (nums[i] < nums[k] && nums[k] < nums[j])
        return true;
// Spoiler: This is how you get fired by runtime.

🧠 How Devs Usually Mess This Up

Most devs try to find the global min, a global max, and something in between. That’s cute, but it won’t find the 132 Pattern unless you get very lucky or very supervised. Some try greedy neighbor checks or treat everything like a subarray. Reminder: the 132 pattern cares about order (not adjacency!) and the middle value must be the highest. Pro tip: Trying this left-to-right with a stack is like using a fork to eat soup—just messy and ineffective.

🔍 What’s Actually Going On

Think of stock prices: you want to spot a low (let’s buy), a rocket-ship high (let’s daydream), then a dip (sell while you’re still ahead). The 132 pattern is catching that sequence—where the “2” is higher than both the first and last in the trio, and everyone is properly ordered in time. The O(n) trick? Walk right-to-left, keep a stack of possible “peaks,” and track the best “third” (the middle value in 132). When you find a number smaller than your “third,” you just landed a 132 pattern. Tada!

🛠️ PseudoCode

• Set up: Let third = Integer.MIN_VALUE, and grab an empty stack.
• Walk backwards: For each number from right to left:
  • If nums[i] < third, the 132 pattern is yours—celebrate and return true.
  • While stack isn’t empty and nums[i] > stack.peek(), pop stack and set third to the popped value.
  • Push nums[i] onto the stack (potential future “2”).
• If you finish the walk empty-handed: Return false, go grab coffee.

// Java pseudocode
int third = Integer.MIN_VALUE;
Stack<Integer> 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;

💻 The Code

public boolean find132pattern(int[] nums) {
  if (nums == null || nums.length < 3) return false;
  int third = Integer.MIN_VALUE;
  Stack<Integer> 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;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Subarray vs. Subsequence: Pattern can skip values—order matters, but no need for everyone to sit next to each other.
• Wrong direction: Going left-to-right with your stack? That’s how you miss patterns and disappoint Chandler.
• Tiny arrays: Fewer than 3 elements? Don’t bother—your pattern can’t even start.
• Complexity: Stack version is O(n) time and O(n) space. Brute force is O(n³) and a practical joke on your processor.

🧠 Interviewer Brain-Tattoo

“You can’t find a zig in a room full of zags unless you walk backwards with a stack. Stack smart, code smarter.”