How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at TikTok.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at TikTok during technical interviews.

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.

Input: ([42],)

Expected Output: (1, [42])

Explanation: Single element: the LIS is the element itself.

Input: ([7, 7, 7],)

Expected Output: (1, [7])

Explanation: All equal: a strictly increasing subsequence can use only one of them, so length 1. (bisect_left keeps overwriting slot 0.)

Input: ([5, 4, 3, 2, 1],)

Expected Output: (1, [5])

Explanation: Strictly decreasing: best LIS has length 1. The algorithm reports the first index that reached the max length, value 5; [1] would be equally valid.

Input: ([1, 2, 3, 4, 5],)

Expected Output: (5, [1, 2, 3, 4, 5])

Explanation: Already strictly increasing: the whole array is the LIS.

Input: ([3, -1, -1, 0, 5],)

Expected Output: (3, [-1, 0, 5])

Explanation: Negatives and duplicates: strict LIS is [-1,0,5]; only one of the two -1 values can be used.

Input: ([0, 1, 0, 3, 2, 3],)

Expected Output: (4, [0, 1, 2, 3])

Explanation: Multiple length-4 LIS exist (e.g. [0,1,3,3] is NOT strict; [0,1,2,3] is). The predecessor-pointer reconstruction returns a genuinely strictly increasing one.

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.

Quick Overview

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.