Compute longest increasing subsequence
Company: TikTok
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given an integer array nums, compute the length of a longest strictly increasing subsequence and also output one valid subsequence. Aim for an O(n log n) approach; explain the binary-search (patience sorting) technique, how to reconstruct the subsequence, and analyze time/space complexity. Follow-ups: adapt to non-decreasing subsequences, handle duplicates carefully, and discuss how to count how many LIS exist.
Quick Answer: This question evaluates understanding of sequence algorithms, dynamic programming concepts, and algorithmic optimization for the longest increasing subsequence problem, including subsequence reconstruction and complexity analysis.
Given an integer array `nums`, return a pair `(length, subsequence)` where `length` is the length of a longest STRICTLY increasing subsequence (LIS), and `subsequence` is one concrete LIS of that length (its actual values, in order).
A subsequence is formed by deleting zero or more elements without changing the relative order of the rest. 'Strictly increasing' means each chosen value is strictly greater than the previous one.
If several LIS exist, returning any one of them is acceptable. Aim for an O(n log n) approach using the patience-sorting / binary-search technique, augmented with predecessor pointers so you can reconstruct an actual subsequence (not just its length).
Return convention by language:
- Python: return a tuple `(length, subsequence_list)`.
- Java: return `int[]` whose first element is the length, followed by the subsequence values (length 1 + L).
- C++: return `vector<int>` whose first element is the length, followed by the subsequence values.
- JavaScript: return an array `[length, ...subsequence]`.
For the empty input, return length 0 with an empty subsequence.
Constraints
- 0 <= n <= 10^5 (designed for large n so the O(n log n) method is justified)
- Values fit in a 32-bit signed integer and may be negative
- Duplicates may appear; the LIS must be STRICTLY increasing
- Returning any one valid LIS is acceptable when several exist
Examples
Input: ([10, 9, 2, 5, 3, 7, 101, 18],)
Expected Output: (4, [2, 3, 7, 101])
Explanation: LIS length is 4; [2,3,7,101] is one valid longest strictly increasing subsequence (so is [2,3,7,18]).
Input: ([],)
Expected Output: (0, [])
Explanation: Empty array: length 0 and an empty subsequence.
Hints
- Start with the O(n^2) DP: dp[i] = length of the longest strictly increasing subsequence ending at index i. Then ask what is redundant about rescanning all earlier elements.
- Maintain an array tails where tails[k] is the smallest possible tail value of any strictly increasing subsequence of length k+1. It stays strictly increasing, so you can binary-search it; len(tails) is the LIS length.
- For a STRICT LIS use bisect_left (leftmost tail >= x): overwrite that slot, or append if x exceeds every tail. (For the non-decreasing variant you'd switch to bisect_right.)
- tails is not itself a valid subsequence. To reconstruct, also record a predecessor pointer per index (the index occupying tails[pos-1] at write time) and backtrack from the index that achieved the maximum length.