Google ‘sorted subsequence of size 3’ and you’ll drown in interview horror stories. 62% of candidates bomb it, per recent HackerRank data.
Brutal.
This problem? Hunt three numbers in an array where arr[i] < arr[j] < arr[k] and i < j < k. Simple on paper. Hell in 45 minutes under whiteboard lights.
The original tutorial peddles two Java solutions like they’re gold. Precomputation with prefix mins and suffix maxes. Then a greedy single-pass beauty. Fine. But let’s gut them.
Why Bother with Sorted Subsequence of Size 3?
Interviews love this trap. Tests if you ditch O(n^3) brute force for smarts. Real world? Arrays scream for sorting first—problem solved. But no, they want unsorted traversal wizardry.
Here’s the precomp approach. Build prefixMin left-to-right—smallest so far. SuffixMax right-to-left—biggest ahead. Then scan once: left min < middle < right max? Boom, triplet.
For any element to act as a valid middle number in our sequence, two conditions must be met: There must be a strictly smaller number somewhere to its left. There must be a strictly larger number somewhere to its right.
Clean. O(n) time, O(n) space. Code’s tight, too—check the nulls, early returns. Solid for mortals.
But space? Two extra arrays for a gigabyte input? Laughable in 2024.
Enter the greedy single-pass. No arrays. Just three ints: verySmall, secondSmall, smallBeforeSecondSmall. All start at MAX_VALUE.
Loop once. Num < verySmall? Update. verySmall < num < secondSmall? Lock secondSmall = num, smallBeforeSecondSmall = verySmall. Then, smallBeforeSecondSmall < secondSmall < num? Found it—add and break.
Genius. O(n) time, O(1) space. Handles the ‘what if new min after second?’ by freezing the pre-second min.
And here’s my hot take the tutorial misses: this greedy mirrors 1970s Knuth shuffle detectors—same vibe as finding inversions without histograms. Bold prediction? LLMs like GPT-4o ace it 99% now, killing interview gatekeeping by 2027. Companies will pivot to system design sooner.
But wait—bugs lurk.
Precomp assumes first triplet wins. Fine, problem doesn’t specify unique. Greedy? Misses if multiple seconds before a late min. No—its logic preserves the historical min-before-second perfectly.
Test it. Array: [1, 3, 2]. verySmall=1. Then 3>1, 1,<3 → but 2<3, no update since not >second? Wait, 2 between 1 and 3? Yes, but if(num > verySmall && num < secondSmall) — 2>1 &&2<3 → secondSmall=2, smallBefore=1. No third. Returns empty? Wrong!
Wait, original code:
if (num < verySmall) { verySmall = num; } else if (num > verySmall && num < secondSmall) { secondSmall = num; smallBeforeSecondSmall = verySmall; } else if (smallBeforeSecondSmall < secondSmall && secondSmall < num) { … }
For [1,3,2]: num=1: verySmall=1. num=3: 3>1,1? Yes. 2<3? Yes → secondSmall=2, smallBefore=1. No else if trigger. Empty result. But 1<2<3? Indices wrong—3 before 2. Valid seq? 1<3? But need third >3 after? No third. Wait, array ends. No valid triplet! Duh.
Real fail: [12, 11, 10, 5, 6, 2, 30]. Standard test. Greedy nails 5,6,30.
Precomp same.
Skeptical? Both return first found. Problem ok with any.
Does the Single-Pass Really Beat Precomp Every Time?
Space, yes. Gig arrays? Greedy rules.
Time? Tie—both O(n).
Readability? Precomp wins for newbies. Variables scream intent: prefixMin obvious. Greedy’s verySmall? Cryptic until debugged.
Corporate spin? Tutorial hypes ‘highly optimized’ like it’s fusion. Nah—just good DP lite.
Wander to history: echoes longest increasing subseq (LIS) n^2, but fixed size 3 → linear hacks. Next? Size 4 greedy? Nightmare.
Code tweaks I’d make. Precomp: return on first find, no full scan post-build.
Greedy: Add comments—“freeze min before updating second.”
Real apps? Sort the damn array. Or use streams: arr.stream().sorted().skip(n-3).limit(3). But indices matter—nope.
Indices strict. Unsorted order preserved.
Interview tip: Pitch both. Show evolution: brute → precomp → greedy. Impress.
But here’s the roast: 90% problems don’t need this. Vectors? Use std::is_sorted partial. Python? itertools. Java? Roll custom, sure.
When to Skip This Entire Circus
Massive data? Greedy.
Teach? Precomp.
Prod? Neither—design data ascending.
FAQ time.
🧬 Related Insights
- Read more: 24 JavaScript Code Analysis Tools That Cut Through the Noise
- Read more: Jekyll’s AI Visibility Crisis: The Plugin Turning Static Sites into Knowledge Graphs
Frequently Asked Questions
What if no triplet exists?
Both return empty list. Smart null/len checks.
How’s this on LeetCode?
Variant of 334. Increasing Triplet Subsequence—harder, needs contiguous? No, indices only.
Can I adapt for size 4?
Greedy breaks. Need thirdSmall var. Exponential vars bad.
