122. 132 Pattern
🔗 LeetCode Problem: 456. 132 Pattern
📊 Difficulty: Medium
🏷️ Topics: Array, Stack, Monotonic Stack, Binary Search
Problem Statement
Given an array of n integers nums, a 132 pattern is a subsequence of three integers nums[i], nums[j], 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 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].
Example 3:
Input: nums = [-1,3,2,0]
Output: true
Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].
Constraints:
- n == nums.length
- 1 <= n <= 2 × 10^5
- -10^9 <= nums[i] <= 10^9
🌟 Understanding the Problem
What Are We Really Asking?
Find if there exists i < j < k where:
nums[i] < nums[k] < nums[j]
In simple terms:
Position: i j k
Value: 1 3 2
↑ ↑ ↑
small big middle
The pattern: small, BIG, middle
(132 because 1 < 3 and 2 < 3 but 1 < 2)
Visual Example:
Array: [3, 1, 4, 2]
Is [3, 1, 4] a 132 pattern?
3 < 2? NO (need i < k)
Is [3, 4, 2] a 132 pattern?
3 < 2? NO
Is [1, 4, 2] a 132 pattern?
i=1, j=2, k=3
1 < 2? YES ✓
2 < 4? YES ✓
1 < 4? YES ✓
Found 132 pattern! ✓
Key Insight: We need to find three positions where the middle position has the LARGEST value!
💡 How to DISCOVER the Solution (Teacher Mode: ON)
Let me show you the natural thought process - how to go from knowing nothing to discovering the stack solution yourself.
🎯 STEP 1: Understanding What We're Looking For
The Problem:
Find three indices i < j < k where:
nums[i] < nums[k] < nums[j]
In simple words: Find [small, BIG, medium]
↑ ↑ ↑
1 3 2 (that's why "132")
Example:
Array: [3, 1, 4, 2]
Is there a 132 pattern?
Let me try different combinations:
[3, 1, 4]: 3 < 4? NO (need first < third)
[3, 1, 2]: 3 < 2? NO
[3, 4, 2]: 3 < 2? NO
[1, 4, 2]: 1 < 2 < 4? YES! ✓✓✓
Found it!
🎯 STEP 2: First Attempt - How Would YOU Solve This?
Natural thinking:
"Let me try all possible triplets!"
for i in 0 to n-3:
for j in i+1 to n-2:
for k in j+1 to n-1:
if nums[i] < nums[k] < nums[j]:
return true
This works! But it's O(n³) - too slow!
Question: Can we do better?
🎯 STEP 3: Observation - What Are We Really Searching For?
Let's think differently. For a 132 pattern:
nums[i] < nums[k] < nums[j]
↑ ↑
small BIG
Key observation: nums[j] is the LARGEST of the three!
New thinking:
"What if I fix nums[j] (the peak) and search for i and k?"
For each position j:
- Find smallest nums[i] to the LEFT (i < j)
- Find any nums[k] to the RIGHT where nums[i] < nums[k] < nums[j]
Why is this better?
If I know the MINIMUM to the left of j,
I maximize my chances of finding a valid nums[k]!
Example: nums = [5, 3, 1, 4, 2]
At j=3 (value 4):
- Minimum to left = 1
- Need to find k where 1 < nums[k] < 4
- Check k=4: nums[4]=2, and 1 < 2 < 4? YES!
This gives us the O(n²) solution!
🎯 STEP 4: Can We Do Even Better? (The Critical Question!)
Current bottleneck:
For each j, we scan ALL positions k to the right
→ This is O(n) for each j
→ Total: O(n²)
The million-dollar question:
"For a given j, do I REALLY need to check ALL k positions?"
Think about this:
If I'm at position j with value 10,
and minimum to my left is 2,
I need to find ANY value between 2 and 10 to my right.
Do I care about ALL such values?
Or just SOME special values?
Insight:
I don't need all values!
I just need to know: "Is there ANY value in range (2, 10)?"
But wait... how do I know the range efficiently?
🎯 STEP 5: The Breakthrough - Reverse Your Thinking!
Current approach (LEFT to RIGHT):
At position j:
- Look LEFT for minimum (i)
- Look RIGHT for middle value (k)
- Problem: Don't know what's coming on the right!
What if we REVERSE direction? (RIGHT to LEFT)
At position i:
- We've ALREADY seen everything to the right!
- We already know all possible j and k values!
- Question becomes: "Can I be the '1' in a 132 pattern?"
This is HUGE! Let me show you why:
Scanning LEFT to RIGHT:
Position i: "I wonder what's ahead..."
Position j: "Let me check both sides..."
Position k: "I need to remember what I saw..."
→ Complicated!
Scanning RIGHT to LEFT:
Process from right first: "I know all peaks and valleys"
At any position: "Am I smaller than any valley I've seen?"
→ Simple!
🎯 STEP 6: What Information Do We Need? (The Data Structure Question)
When scanning RIGHT to LEFT, what do we need to track?
Let's trace through: [3, 1, 4, 2]
At position 3 (value=2):
"I could be a peak (the '3' in 132)"
Store: 2
At position 2 (value=4):
"I'm bigger than 2, so I'm a BETTER peak!"
"What happens to 2? It becomes a VALLEY!"
Store: 4 is new peak, 2 is a valley
At position 1 (value=1):
"Am I smaller than any valley?"
"Is 1 < 2? YES! Found pattern!"
What do we need to store?
1. All potential PEAKS (larger values)
2. The best VALLEY value (from smaller values we've seen)
Wait... this sounds like we need:
- A collection for peaks
- A single variable for valley
🎯 STEP 7: Why STACK? (The Natural Discovery!)
Question: How should we store peaks?
Let's think about the peaks we see:
Scenario 1: [2, 3, 4, 5] (from right)
All peaks: 2, 3, 4, 5
Do we need all of them?
NO! If we have 5, we don't care about 2,3,4
Because 5 is the BIGGEST!
Scenario 2: [5, 4, 3, 2] (from right)
First see: 2
Then see: 3 (bigger than 2)
Then see: 4 (bigger than 3)
Then see: 5 (bigger than 4)
Pattern: Each new value is BIGGER than previous!
Scenario 3: [4, 2, 5, 3] (from right)
See 3: potential peak
See 5: BIGGER peak! (3 becomes valley)
See 2: smaller than 5, keep both (2 and 5)
See 4: bigger than 2, pop 2
The pattern emerges:
We need to:
1. Add new values
2. Remove smaller values when bigger ones appear
3. Keep track in SOME ORDER
This is exactly what a STACK does!
Why STACK specifically?
1. We process from right to left
2. Recent values matter more (Last In, First Out)
3. When we see a bigger value, we remove smaller ones
→ LIFO structure perfect for this!
4. Stack naturally maintains an ORDER
🎯 STEP 8: The Final Picture (How Everything Connects)
The complete logic:
Stack purpose: Store potential PEAKS in DECREASING order
[Biggest peak, Second biggest, Third biggest, ...]
Why decreasing?
Because when we pop smaller ones, they become valleys!
middle purpose: Track the BEST VALLEY
= The largest value we've popped so far
Why largest popped?
If middle = 5 (popped), stack has something > 5
Any element < 5 will satisfy: element < 5 < stack.top
That's the 132 pattern!
Visual walkthrough:
Array: [3, 1, 4, 2] (scanning right to left)
Position 3 (value=2):
stack = [2] ← 2 is a potential peak
middle = -∞
Position 2 (value=4):
4 > 2 in stack
→ Pop 2, it becomes valley!
stack = [4] ← 4 is the peak
middle = 2 ← 2 is the valley
Interpretation: We have a (peak=4, valley=2) pair!
If we find anything < 2, we're done!
Position 1 (value=1):
Check: Is 1 < middle(2)? YES!
Found: 1 < 2 < 4
↑ ↑ ↑
i k j
🎯 STEP 9: Why This Solution is BRILLIANT
It solves multiple problems at once:
Problem 1: "How to track multiple peaks?"
Solution: Stack (LIFO, ordered, easy to update)
Problem 2: "How to find the valley?"
Solution: Popped values! (They're smaller than new peak)
Problem 3: "How to check efficiently?"
Solution: One comparison! (current < middle)
Problem 4: "What about position ordering?"
Solution: Right-to-left scan ensures positions are correct!
Time complexity:
Each element:
- Pushed to stack: once
- Popped from stack: once
Total operations: 2n = O(n) ✓
🎯 STEP 10: The "Aha!" Moment (Why It Finally Clicks)
The genius insight:
Don't search for "1, 3, 2" separately!
Instead:
1. Build (3, 2) pairs as you scan right-to-left
→ Stack = peaks (3)
→ middle = valleys (2)
2. For each position, ask: "Can I be the 1?"
→ Just check: current < middle
3. Position constraint automatically satisfied
→ Because we're scanning right-to-left!
Why stack is NOT random:
❌ "Use stack because it's a stack problem"
✓ "Use stack because we need LIFO for peaks in order"
❌ "Pop when bigger comes"
✓ "Pop smaller values - they become valleys!"
❌ "Middle tracks popped values"
✓ "Middle is the best valley, creating (peak,valley) pair"
🎪 Summary: The Natural Discovery Process
Step 1: Brute force (try all triplets) → O(n³)
Step 2: Fix the peak, find min left → O(n²)
Step 3: "Can we avoid scanning right every time?"
Step 4: "What if we scan right-to-left?"
Step 5: "We've already seen everything! Just check!"
Step 6: "What do we need to store?"
Step 7: "Peaks in order + valley → Stack + variable!"
Step 8: "When bigger comes, smaller becomes valley!"
Step 9: "Check current < valley → Done!"
Step 10: O(n) solution discovered! ✓
This is how you DERIVE the solution, not just memorize it!
🎯 Approach 1: Brute Force (Try All Triplets)
The Idea
Try all possible combinations of i, j, k.
Check if they form 132 pattern.
Implementation
public boolean find132pattern(int[] nums) {
int n = nums.length;
// Try all triplets
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++) {
// Check if nums[i] < nums[k] < nums[j]
if (nums[i] < nums[k] && nums[k] < nums[j]) {
return true;
}
}
}
}
return false;
}
Complexity Analysis
⏰ Time: O(n³) - Three nested loops
💾 Space: O(1) - No extra space
The Problem
For n = 10,000:
10,000³ = 1,000,000,000,000 operations!
Way too slow!
🎯 Approach 2: Smart Optimization (Better Understanding)
The Lightbulb Moment 💡
Observation:
For 132 pattern: nums[i] < nums[k] < nums[j]
Key insight: For any middle position j,
- nums[i] should be the MINIMUM to the LEFT of j
- nums[k] should be anything to the RIGHT that's between min and nums[j]
Why?
If we pick the MINIMUM as nums[i]:
- We maximize our chances of finding nums[k]
- Because more values will be > minimum
Example: [5, 3, 1, 4, 2]
At j=3 (nums[j]=4):
minimum to left = 1 (at index 2)
Can we find k where 1 < nums[k] < 4?
k=4: nums[4]=2, and 1 < 2 < 4? YES! ✓
The Strategy
Step 1: Pre-compute minimum array
min[i] = smallest element from index 0 to i
Step 2: For each position j (potential peak):
For each position k > j:
Check if min[j-1] < nums[k] < nums[j]
Implementation
public boolean find132pattern(int[] nums) {
int n = nums.length;
if (n < 3) return false;
// Step 1: Build minimum array
// min[i] = minimum from index 0 to i
int[] min = new int[n];
min[0] = nums[0];
for (int i = 1; i < n; i++) {
min[i] = Math.min(min[i - 1], nums[i]);
}
// Step 2: For each j, find k where min[j-1] < nums[k] < nums[j]
for (int j = 1; j < n - 1; j++) {
for (int k = j + 1; k < n; k++) {
// min[j-1] is our nums[i] (smallest to left of j)
// nums[j] is our peak
// nums[k] is our middle
if (min[j - 1] < nums[k] && nums[k] < nums[j]) {
return true;
}
}
}
return false;
}
Step-by-Step Dry Run
Input: nums = [3, 1, 4, 2]
═══════════════════════════════════════════════════════════
Step 1: Build min array
═══════════════════════════════════════════════════════════
i=0: min[0] = nums[0] = 3
i=1: min[1] = min(3, 1) = 1
i=2: min[2] = min(1, 4) = 1
i=3: min[3] = min(1, 2) = 1
Result: min = [3, 1, 1, 1]
Meaning:
min[1] = 1 → smallest element from 0 to 1 is 1
min[2] = 1 → smallest element from 0 to 2 is 1
min[3] = 1 → smallest element from 0 to 3 is 1
═══════════════════════════════════════════════════════════
Step 2: Find pattern
═══════════════════════════════════════════════════════════
j=1, nums[j]=1:
Try k=2: min[0] < nums[2] < nums[1]?
3 < 4 < 1? NO (3 is not < 4 in the right way)
Try k=3: min[0] < nums[3] < nums[1]?
3 < 2 < 1? NO
j=2, nums[j]=4:
Try k=3: min[1] < nums[3] < nums[2]?
1 < 2 < 4?
✓ 1 < 2? YES
✓ 2 < 4? YES
FOUND! ✓✓✓
Pattern found: [1, 4, 2]
nums[i] = 1 (at index 1, from min[1])
nums[j] = 4 (at index 2, the peak)
nums[k] = 2 (at index 3, the middle)
Return true
Why This Works
Think about it simply:
For pattern [1, 3, 2]:
- "1" should be as SMALL as possible (use minimum)
- "3" is any element (try each position as j)
- "2" is between "1" and "3" (search to the right)
By using minimum array:
✓ We don't need to search for "1"
✓ We just use the smallest seen so far
✓ Reduces one dimension of search
Complexity Analysis
⏰ Time: O(n²) - Two nested loops for j and k
💾 Space: O(n) - Min array
The Limitation
Still O(n²) time complexity.
Can we do better?
YES! → Monotonic Stack approach is O(n)
🎯 Approach 3: Monotonic Stack - The OPTIMAL Solution ⚡
🧠 Before We Code: Why These Choices?
Q1: Why not just use an array to store peaks?
Array problems:
- Need to track "which peaks to keep"
- Need to shift elements when removing
- No natural LIFO behavior
Stack advantage:
✓ LIFO matches our right-to-left scan
✓ Easy to add/remove from one end
✓ Represents "most recent values" naturally
Q2: Why not use a queue?
Queue = FIFO (First In, First Out)
But we need LIFO (Last In, First Out)
Example: See [2, 3, 4] from right
- Most recent (4) is most relevant
- Queue would give us 2 first (wrong!)
Q3: Why not just track maximum instead of stack?
Maximum alone isn't enough!
Example: [5, 2, 6, 3] from right
See 3: max=3
See 6: max=6, pop 3 → middle=3
See 2: 2 < max(6) but 2 < 3? NO!
See 5: Need to check against 3, not 6!
We need to maintain MULTIPLE potential peaks,
not just the maximum!
Q4: Why variable 'middle' and not an array of valleys?
We only need ONE best valley!
Why? Because:
- We check: current < middle
- If TRUE, we found pattern immediately
- We don't need multiple valleys
The LARGEST popped value is the best valley because:
- It gives us the widest range
- More elements can be < it
🎯 The Complete Algorithm (With Reasoning)
Initialize:
stack = empty stack
middle = Integer.MIN_VALUE (no valley yet)
Scan from RIGHT to LEFT:
For each nums[i]:
Step 1: Check if we found pattern
if nums[i] < middle:
return true
Why? We have:
- nums[i] is "1" (current)
- middle is "2" (valley from earlier)
- stack.top is "3" (peak > middle)
Step 2: Update our (peak, valley) pairs
while stack not empty AND nums[i] > stack.top:
middle = stack.pop()
Why pop?
- nums[i] is a BIGGER peak
- Smaller peaks become valleys
- Track the LARGEST popped as best valley
Step 3: Store current as potential peak
stack.push(nums[i])
Why?
- Could be a peak for future elements
- Maintains decreasing order in stack
📊 Visual Step-by-Step (Understanding Each Decision)
Input: [3, 1, 4, 2]
═══════════════════════════════════════════════════════════
Position 3: nums[3] = 2
═══════════════════════════════════════════════════════════
Step 1: Check pattern
Is 2 < middle(-∞)? NO
Step 2: Update peaks/valleys
Stack empty, nothing to pop
Step 3: Store as peak
stack.push(2)
State:
stack = [2]
middle = -∞
Thinking:
"2 is a potential peak for future elements"
═══════════════════════════════════════════════════════════
Position 2: nums[2] = 4
═══════════════════════════════════════════════════════════
Step 1: Check pattern
Is 4 < middle(-∞)? NO
Step 2: Update peaks/valleys
Is stack empty? NO
Is 4 > stack.top(2)? YES!
Action: Pop 2
Why? 4 is a BIGGER peak than 2
What happens to 2? Becomes a valley!
middle = 2 (the popped value)
Continue loop? Stack empty, stop
Step 3: Store as peak
stack.push(4)
State:
stack = [4] ← The peak
middle = 2 ← The valley
Thinking:
"I have a (peak=4, valley=2) pair!"
"If I find anything < 2, I'm done!"
Why this works:
- 4 is in stack (potential "3")
- 2 is middle (the "2" in 132)
- Any element < 2 will be "1"
- Pattern: element < 2 < 4 ✓
═══════════════════════════════════════════════════════════
Position 1: nums[1] = 1
═══════════════════════════════════════════════════════════
Step 1: Check pattern
Is 1 < middle(2)? YES! ✓✓✓
FOUND THE PATTERN!
Verification:
nums[i] = 1 (position 1) ← The "1"
middle = 2 (was position 3) ← The "2"
stack = [4] (position 2) ← The "3"
Check: 1 < 2 < 4? YES! ✓
Positions: 1 < 2 < 3? YES! ✓
Return true
💡 Why Stack Maintains DECREASING Order
This is important to understand!
When we pop smaller elements:
- They become valleys
- We update middle
What remains in stack?
- Only elements BIGGER than middle
- In DECREASING order (newest to oldest)
Example sequence:
Process 2: stack = [2]
Process 5: 5 > 2, pop 2
stack = [5], middle = 2
Process 3: 3 < 5, don't pop
stack = [5, 3], middle = 2
Process 4: 4 > 3, pop 3 → middle = 3
4 < 5, don't pop 5
stack = [5, 4], middle = 3
Notice: stack is [5, 4] (decreasing!)
middle = 3 (largest popped)
Why decreasing order matters:
When we check nums[i] < middle:
- middle came from popped values
- Stack top > middle (otherwise would be popped)
- So: nums[i] < middle < stack.top
- That's the 132 pattern!
The decreasing order ensures:
✓ Correct relationships
✓ Easy to maintain (pop smaller, keep bigger)
✓ Efficient checking (just peek at top)
Implementation (Every Line Explained)
public boolean find132pattern(int[] nums) {
int n = nums.length;
// Need at least 3 elements for pattern
if (n < 3) return false;
// Stack: stores potential peaks in decreasing order
// Why Stack? LIFO matches right-to-left processing
Stack<Integer> stack = new Stack<>();
// middle: best valley value from popped elements
// Why MIN_VALUE? No valley found yet, need smallest possible
int middle = Integer.MIN_VALUE;
// Scan from RIGHT to LEFT
// Why? We build (peak,valley) pairs BEFORE checking for "1"
for (int i = n - 1; i >= 0; i--) {
// Step 1: Check if current can be "1" in 132
// If yes, we have: nums[i] < middle < stack.top
if (nums[i] < middle) {
return true;
}
// Step 2: Update peaks and valleys
// Pop elements smaller than current
// Why? Current is a BIGGER peak, smaller ones become valleys
while (!stack.isEmpty() && nums[i] > stack.peek()) {
// Update middle to popped value
// Why? It's a valley now (smaller than current peak)
middle = stack.pop();
// Note: We keep updating, so middle = LARGEST popped
}
// Step 3: Push current as potential peak
// It could be "3" for future elements
stack.push(nums[i]);
}
// No pattern found
return false;
}
🔍 Detailed Dry Run (Every Decision Explained)
Input: nums = [-1, 3, 2, 0]
═══════════════════════════════════════════════════════════
i=3, nums[3]=0
═══════════════════════════════════════════════════════════
Check: 0 < middle(-∞)? NO
Why NO? -∞ is smaller than everything
While: stack.isEmpty()? YES
Why skip? No peaks to compare
Push: stack.push(0)
Why? 0 could be a peak for future elements
State: stack=[0], middle=-∞
═══════════════════════════════════════════════════════════
i=2, nums[2]=2
═══════════════════════════════════════════════════════════
Check: 2 < middle(-∞)? NO
While: !stack.isEmpty() && 2 > stack.peek(0)?
TRUE && TRUE = ENTER LOOP
Why enter? 2 is BIGGER than 0
Iteration 1:
middle = stack.pop() = 0
Why? 0 is now a valley (2 is bigger peak)
stack = []
Loop check: stack.isEmpty()? YES, EXIT
Why exit? No more elements to pop
Push: stack.push(2)
Why? 2 is now the peak
State: stack=[2], middle=0
Interpretation:
- Peak = 2 (in stack)
- Valley = 0 (middle)
- Looking for element < 0
═══════════════════════════════════════════════════════════
i=1, nums[1]=3
═══════════════════════════════════════════════════════════
Check: 3 < middle(0)? NO
Why NO? 3 > 0
While: !stack.isEmpty() && 3 > stack.peek(2)?
TRUE && TRUE = ENTER LOOP
Why enter? 3 is BIGGER than 2
Iteration 1:
middle = stack.pop() = 2
Why update? 2 is now valley (3 is bigger)
Note: middle was 0, now updated to 2 (LARGER valley!)
stack = []
Loop check: stack.isEmpty()? YES, EXIT
Push: stack.push(3)
State: stack=[3], middle=2
Interpretation:
- Peak = 3 (in stack)
- Valley = 2 (middle, updated from 0)
- Looking for element < 2
Why middle = 2 not 0?
Because 2 is LARGER, gives wider range for "1"
═══════════════════════════════════════════════════════════
i=0, nums[0]=-1
═══════════════════════════════════════════════════════════
Check: -1 < middle(2)? YES! ✓✓✓
FOUND!
Pattern breakdown:
nums[i] = -1 (position 0) ← "1" in 132
middle = 2 (from position 2) ← "2" in 132
stack = [3] (position 1) ← "3" in 132
Verification:
Values: -1 < 2 < 3? ✓
Positions: 0 < 1 < 2? ✓
(Note: middle came from pos 2, stack from pos 1)
Return true
Complexity Analysis (With Reasoning)
⏰ Time: O(n)
Why?
- Each element visited once: O(n)
- Each element pushed to stack: once
- Each element popped from stack: at most once
Total stack operations: 2n = O(n)
Overall: O(n) + O(n) = O(n) ✓
Why "at most once" for pop?
Once an element is popped, it's gone!
Can't be popped again.
💾 Space: O(n)
Why?
Worst case: array is strictly decreasing
Example: [5, 4, 3, 2, 1]
Stack will have: [5, 4, 3, 2, 1]
All n elements stored!
Best case: O(1)
Example: [1, 2, 3, 4, 5]
Stack will have: [5] at most
Everything else gets popped!
🎯 The Key Insights (Memorize These!)
1. Direction matters
Right-to-left = Know all (peak, valley) pairs first
Left-to-right = Must predict future
2. Stack role
Stores potential PEAKS in DECREASING order
Why decreasing? Smaller ones get popped (become valleys)
3. Middle role
Best VALLEY value = LARGEST popped value
Why largest? Wider range means more chances to find "1"
4. The check
current < middle means:
current < middle < stack.top
1 2 3
Found 132 pattern!
5. Why it works
Stack always has: values > middle
Middle always has: largest popped value
Check ensures: current < middle < stack.top
This is exactly: "1" < "2" < "3"
📊 Approach Comparison
┌────────────────────────────────────────────────────────────┐
│ Approach 1 Approach 2 Approach 3 │
│ (Brute) (Min Array) (Stack) │
├────────────────────────────────────────────────────────────┤
│ Core Idea Try every Fix smallest Fix (peak, │
│ triplet value first valley) first │
│ │
│ Direction Left→Right Left→Right Right→Left ✓ │
│ │
│ Time O(n³) O(n²) O(n) ✓ │
│ │
│ Space O(1) ✓ O(n) O(n) │
│ │
│ Interview Never OK for BEST ✓ │
│ use discussion │
└────────────────────────────────────────────────────────────┘
🎯 Which to Use in Interview?
Start with Approach 2 (if stuck):
✓ Easy to explain
✓ Shows optimization thinking
✓ Natural progression to Approach 3
Master Approach 3:
✓ Optimal O(n) solution
✓ Shows advanced DS knowledge
✓ Demonstrates pattern recognition
✓ What top companies expect
🧠 The Learning Progression
Step 1: Understand the problem
→ "Find i < j < k where nums[i] < nums[k] < nums[j]"
Step 2: Realize the insight
→ "Fix (peak, valley) pair first, then find small value"
Step 3: Apply the technique
→ "RIGHT to LEFT scan with monotonic stack"
Step 4: Master the pattern
→ "This works for many similar problems!"
🧪 Edge Cases
Edge Case 1: Strictly Increasing
Input: nums = [1, 2, 3, 4, 5]
Output: false
No peaks to form 132 pattern ✓
Stack: [5, 4, 3, 2, 1]
middle: -∞
No element < middle
Edge Case 2: Strictly Decreasing
Input: nums = [5, 4, 3, 2, 1]
Output: false
Process from right:
i=4: stack=[1], middle=-∞
i=3: 2>1, pop→middle=1, stack=[2]
i=2: 3>2, pop→middle=2, stack=[3]
i=1: 4>3, pop→middle=3, stack=[4]
i=0: 5>4, pop→middle=4, stack=[5]
No element < middle (all elements keep updating middle)
Edge Case 3: All Same
Input: nums = [3, 3, 3, 3]
Output: false
All elements equal
Can't satisfy nums[i] < nums[k] < nums[j]
Edge Case 4: Length < 3
Input: nums = [1, 2]
Output: false
Need at least 3 elements ✓
Edge Case 5: Negative Numbers
Input: nums = [-1, 3, 2, 0]
Output: true
Pattern: [-1, 3, 2]
-1 < 2 < 3? YES ✓
Or: [-1, 3, 0]
-1 < 0 < 3? YES ✓
Edge Case 6: Pattern at End
Input: nums = [1, 0, 1, -4, -3]
Output: false
From right:
i=4: stack=[-3], middle=-∞
i=3: -4<-3, no pop, stack=[-3,-4], middle=-∞
i=2: 1>-3, pop all, middle=-4, stack=[1]
i=1: 0<-4? NO
i=0: 1<-4? NO
No 132 pattern ✓
⚠️ Common Mistakes
Mistake 1: Scanning left to right
// ❌ WRONG - Hard to track middle value
for (int i = 0; i < n; i++) {
// Difficult to know future k values
}
// ✓ CORRECT - Scan right to left
for (int i = n - 1; i >= 0; i--) {
// We've already seen all j, k to the right
}
Mistake 2: Wrong middle update
// ❌ WRONG - Updates middle with each pop
while (!stack.isEmpty() && nums[i] > stack.peek()) {
middle = Math.max(middle, stack.pop()); // ❌
}
// ✓ CORRECT - Middle IS the popped value
while (!stack.isEmpty() && nums[i] > stack.peek()) {
middle = stack.pop(); // ✓ Keep updating to latest pop
}
Mistake 3: Forgetting to push current
// ❌ WRONG - Missing push
while (!stack.isEmpty() && nums[i] > stack.peek()) {
middle = stack.pop();
}
// Forgot to push nums[i]!
// ✓ CORRECT - Always push current
while (!stack.isEmpty() && nums[i] > stack.peek()) {
middle = stack.pop();
}
stack.push(nums[i]); // ✓
Mistake 4: Wrong initial middle value
// ❌ WRONG - Could miss negative patterns
int middle = 0;
// ✓ CORRECT - Use MIN_VALUE
int middle = Integer.MIN_VALUE;
Mistake 5: Not handling empty stack
// ❌ WRONG - Could throw exception
while (nums[i] > stack.peek()) { // ❌ Empty check missing!
middle = stack.pop();
}
// ✓ CORRECT - Check isEmpty first
while (!stack.isEmpty() && nums[i] > stack.peek()) {
middle = stack.pop();
}
🎯 Pattern Recognition
When you see:
- "find pattern in subsequence"
- "i < j < k with value constraints"
- "need to track relationships across positions"
- "looking for specific ordering pattern"
Think:
"Can I use monotonic stack?"
"Should I scan right to left?"
"What invariant should stack maintain?"
Similar Problems: - Next Greater Element (LC 496) - Largest Rectangle in Histogram (LC 84) - Daily Temperatures (LC 739) - Remove K Digits (LC 402) - Trapping Rain Water (LC 42)
📝 Quick Revision Notes
🎯 The ONE Thing to Remember
Scan RIGHT to LEFT:
- Stack = potential peaks (decreasing)
- middle = best valley found
- If current < middle → FOUND!
⚡ Quick Implementation (Memorize This!)
import java.util.Arrays;
import java.util.Stack;
class Solution {
public boolean find132pattern(int[] a) {
int len = a.length;
if(len < 3) {
return false;
}
// // Approach 1 - use min array.
// // step 1: construct min array
// // Element at index i in min array is so far the min element of the array.
// int[] min = new int[len];
// min[0] = a[0];
// for(int i = 1; i < len; i++) {
// min[i] = Math.min(a[i], min[i - 1]); // min between curr and min_so_far
// }
// // System.out.println(Arrays.toString(min));
// // Step 2:
// // For a = [3, 1, 4, 2], we got min as [3, 1, 1, 1]
// // We should get 1 < 3 < 2, for which 1 is min of all 3 elements (1, 2 and 3)
// // We already have 1 out of (1, 3, 2). We now need to find 3 and 2.
// for(int i = 1; i < len; i++) { // tbh, i should be < len -1. Just for understanding, kept like this.
// for(int j = i + 1; j < len; j++) {
// // we are checking for every (i, j) assuming a[i] is peak element (like 3 in 132)
// // j would be next element which is i + 1.
// // Now, it should be min[i - 1] (mn_so_far) < a[j] (middle) and peak (a[i]) > middle (a[j])
// if(min[i - 1] < a[j] && a[i] > a[j]) {
// return true;
// }
// }
// }
// return false;
// Approach 2 - using monotonic stack
// This is actually very simple. All notes made it looking HARD.
// Lets assume you have a monotonic decreasing stack [5, 3, 1] where stack top is 5.
// Next pop element would be always lesser than stack top.
// Our problem is 132. Assume if stack always maintain a decreasing order, we can find
// 3 (peak element) and 2 (middle element) easily. Now, while traversing if we find any
// element 1, we got our 132 pattern found.
// Why separate middle variable? if we pop 2 times, it would not be nice.
Stack<Integer> stack = new Stack<>();
int middleElement = Integer.MIN_VALUE; // 2 in 132 as 1 < 2 < 3
for(int i = len - 1; i >= 0; i--) {
int num = a[i];
if(stack.isEmpty()) {
stack.push(num);
continue;
}
// check for the result.
// GOTCHA: checking against middleElement is enough
// why middleElement < stack.peek()?
// At the end of while loop, actually irrespective of while loop execution, we are
// pushing to stack and actual removal happens only in the next loop. So, that time, there
// happens a situation, where stack top would be less than middleElement. Hence, not check.
// The moment middleElement changes from -INFINITE, there is already a value > middleElement
// Hence, no need to check.
if(num < middleElement) {
return true;
}
// Always maintain a monotonicly decreasing stack (check against the incoming number).
while (!stack.isEmpty() && stack.peek() < num) {
// when popped, middle element needs to replaced - WHY?
// Always numbers in positions of 2 and 3 in 132 should be maximized so that there
// would be maximum chances of getting 1. If we get a popped elemnt (4) which will not
// replace middle element (2) and if there comes an incoming number 3, which is < 2, but actually < 4.
middleElement = stack.pop();
}
stack.push(num);
}
return false;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.find132pattern(new int[] {3,1,4,2}) == true);
System.out.println(s.find132pattern(new int[] {1,2,3,4}) == false);
System.out.println(s.find132pattern(new int[] {-2,1,2,-2,1,2}) == false);
}
}
🔑 Key Insights (Burn Into Memory!)
The Strategy:
1. Fix the (peak, valley) pair FIRST (from right)
2. Then look for the small value (from left)
3. This is why we scan RIGHT to LEFT!
What Stack Stores:
Potential peaks in DECREASING order
[Biggest, Second Biggest, Third Biggest, ...]
What Middle Stores:
The best valley = largest value popped so far
This creates the (peak, valley) pair
The Check:
If current < middle:
current < middle < stack.top
1 2 3
↑ ↑ ↑
Found! (valley) (peak)
🎪 The Magic Visualization
When you pop from stack:
Before: After pop:
stack: [5] stack: []
middle: -∞ middle: 3 ← VALLEY!
Now we have (5, 3) as (peak, valley) pair!
Just need to find value < 3!
💡 Interview Talking Points
"The key insight is scanning right to left because..."
→ "We can build (peak, valley) pairs as we go"
"Stack maintains decreasing sequence because..."
→ "These are potential peaks in order"
"When we pop smaller elements, they become..."
→ "Our valley value, creating the (peak, valley) pair"
"Time is O(n) because..."
→ "Each element pushed/popped exactly once"
⚠️ Critical Don'ts
❌ Don't scan left to right
❌ Don't use >= when comparing (use >)
❌ Don't forget isEmpty() check
❌ Don't use 0 for middle (use MIN_VALUE)
❌ Don't forget to push after popping
✅ Critical Do's
✓ Scan RIGHT to LEFT
✓ Check current < middle FIRST
✓ Pop ALL smaller elements
✓ Update middle with each pop
✓ Push current element last
🎯 Pattern Recognition
This pattern works when:
- Finding relationships across 3+ positions
- Need to track peak/valley patterns
- Looking for "sandwich" patterns (1-3-2)
- Subsequence problems with ordering
Similar Problems:
- Next Greater Element (LC 496)
- Largest Rectangle in Histogram (LC 84)
- Daily Temperatures (LC 739)
- Trapping Rain Water (LC 42)
🧠 Memory Techniques
Acronym: "RPS-MC"
R - RIGHT to left scan
P - Pop smaller elements
S - Stack stores peaks
M - Middle stores valley
C - Check: current < middle?
Visual Mnemonic:
╱╲ ← Peak (stack)
╱ ╲
╱ ╲
? ← ╲ ← Valley (middle)
Find: ? < valley < peak
🎪 The Mental Model
Think: "I'm building mountain ranges from right"
Each new mountain can:
1. Be smaller → Just add to stack
2. Be bigger → Previous mountains become valleys!
When I find a valley, I search left for
anything lower than that valley.
⚡ 30-Second Recap
1. Scan RIGHT to LEFT (this is KEY!)
2. Stack = peaks (decreasing)
3. middle = best valley (from pops)
4. Check: current < middle? → FOUND!
5. Pop smaller → update middle
6. Push current
7. Time: O(n), Space: O(n)
Happy practicing! 🎯
Note: This is a classic monotonic stack problem! The right-to-left scan is the key insight. Very popular at Amazon, Meta, Google! Master this pattern! 💪✨