Solved Subsequence of Size 3 in Single Pass

𝗧𝗵𝗿𝗲𝗲 𝗻𝘂𝗺𝗯𝗲𝗿𝘀. 𝗢𝗻𝗲 𝗽𝗮𝘀𝘀. 𝗢𝗻𝗲 𝗴𝗵𝗼𝘀𝘁 𝘃𝗮𝗿𝗶𝗮𝗯𝗹𝗲. Day 28 of #1000DaysOfLearning Today's problem: 𝗦𝗼𝗿𝘁𝗲𝗱 𝗦𝘂𝗯𝘀𝗲𝗾𝘂𝗲𝗻𝗰𝗲 𝗼𝗳 𝗦𝗶𝘇𝗲 𝟯 (GFG Medium) Find arr[i] < arr[j] < arr[k] where i < j < k — in a single pass. Track the smallest first, then the smallest second after it. The moment you see x > second, you've got your triplet. The tricky part: if first gets updated 𝗮𝗳𝘁𝗲𝗿 second is already set, it's no longer positionally before second. So you keep a prevFirst — 𝘁𝗵𝗲 𝘃𝗮𝗹𝘂𝗲 first 𝗵𝗲𝗹𝗱 𝘄𝗵𝗲𝗻 second 𝘄𝗮𝘀 𝗹𝗮𝘀𝘁 𝘂𝗽𝗱𝗮𝘁𝗲𝗱. Even if first moves to something smaller later, prevFirst still holds the element that actually appeared before second in the array. That's what makes the returned triplet 𝗽𝗼𝘀𝗶𝘁𝗶𝗼𝗻𝗮𝗹𝗹𝘆 𝘃𝗮𝗹𝗶𝗱, not just value-valid. 𝗢(𝗻) time. 𝗢(𝟭) space. #DSA #Python #DataScience #GFG #1000DaysOfLearning #LearningInPublic

  • graphical user interface, text

Huge respect for the daily grind—that consistency is top-tier! 👨💻🔥

See more comments

To view or add a comment, sign in

Explore content categories