The O(n) Club: Increasing Triplet Subsequence—When Two Bouncers Are All You Need

The O(n) Club: Increasing Triplet Subsequence—When Two Bouncers Are All You Need

⚡ TL;DR

You want to know if there’s an increasing subsequence of length three somewhere in your array—anywhere, not just shoulder-to-shoulder. Drop the DP, skip the LIS fanfare, and let two variables (your bouncer team) handle it.

// O(n) Java handshake for triplet
public boolean increasingTriplet(int[] nums) {
    int first = Integer.MAX_VALUE, second = Integer.MAX_VALUE;
    for (int n : nums) {
        if (n <= first) first = n;
        else if (n <= second) second = n;
        else return true;
    }
    return false;
}

🧠 How Devs Usually Mess This Up

If you’re hunting for three-in-a-row, like some algorithmic Hopscotch, you’re already in trouble. Common rookie maneuvers:

• Looking for adjacent numbers: Order matters, not proximity. Spread out, just don’t step backward in indices or value.
• Nested loops: O(n²) = O(nope).
• Packing out the Longest Increasing Subsequence (LIS): You don’t need to haul a chainsaw to cut cheese. LIS is great, but it’s so overkill here it hurts.
• Building long lists of candidates: Minimal state is the name of this game. One bouncer for ‘smallest’, one for ‘mid’, that’s all.

🔍 What’s Actually Going On

Imagine your array is a club, and every number wants in. At the front: first and second, the bouncers. When a new number appears:

• If it’s “littler” than first, first is replaced (that’s a demotion, pal).
• If it beats first but not second, second is replaced. (Middle management problems…)
• If it beats both, congrats, you’ve found your VIP triple. The club’s open. Return true and go home early.

No need for guest lists or security tapes. Just two variables on the lookout. 

🛠️ PseudoCode

• Set first and second to Integer.MAX_VALUE (aka, infinity’s understudy).
• For each num in nums:
  • If num <= first: first = num; (new small fry)
  • Else if num <= second: second = num; (mid-tier fresh meat)
  • Else: return true; (found a triplet in the wild!)
• If you reach the end without tripping the alarm, return false.

💻 The Code

public class IncreasingTriplet {
    public boolean increasingTriplet(int[] nums) {
        int first = Integer.MAX_VALUE;
        int second = Integer.MAX_VALUE;
        for (int n : nums) {
            if (n <= first) {
                first = n;
            } else if (n <= second) {
                second = n;
            } else {
                return true;
            }
        }
        return false;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Triplet does NOT mean next to each other—think “in order,” not “in line.”
• Duplicate values? Totally fine. The bouncers use <= so you don’t get tricked by folks wearing the same shoes.
• Handles negatives, zeros, highs, and lows—if there’s a triplet rising, you’ll spot it.
• Arrays shorter than three? Sorry, you’re not even on the guest list. Return false.
• Time: O(n), Space: O(1). (Yes, your interviewer loves this bit.)

🧠 Interviewer Brain-Tattoo

“If you’re reaching for DP here, you’re solving Rubik’s Cube with a hammer. Two variables, one pass—club policy.”