eBay Coding Question: Increasing Triplet Subsequence

Problem summary

You are given an array of integers and must determine whether there exists a strictly increasing subsequence of length three: indices i < j < k with nums[i] < nums[j] < nums[k]. The comparisons are strict and indices must be increasing.

What you'll be asked to do

In an interview you will typically (a) explain a correct approach, (b) implement it (Python signature provided), and (c) analyze time/space complexity and edge cases. A common expectation is an O(n) solution with O(1) extra space using greedy/two-pointer ideas, but you should be able to discuss the O(n log n) LIS approach as well.

High-level solution (what to understand)

Maintain two variables (first, second) representing the smallest possible first and second elements of a candidate increasing pair. Iterate once over nums: update first when you find a smaller value, update second when you find a value larger than first but smaller than second, and return true as soon as you find a value greater than second (the third element). This demonstrates greedy reasoning and careful invariant maintenance.

Interview flow & skill signals

You will be judged on: correct handling of duplicates and edge cases (short arrays), explanation of invariants, time/space trade-offs, and ability to generalize (LIS or length-k subsequences). Expect follow-ups asking for indices, counts, or a streaming variant. Be prepared to walk through example arrays and give complexity: O(n) time, O(1) extra space for the greedy method.

Tips

Explain why the greedy choice keeps opportunities open for a valid triplet, test with arrays that include repeats, decreasing sequences, and large inputs, and mention alternative LIS-based solutions when asked about generalization.