Katkat
Back

Compute length of longest increasing subsequence

TikTokSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates understanding of subsequences, dynamic programming and algorithmic optimization for array processing, and is categorized under Coding & Algorithms; it emphasizes practical application of algorithm design and complexity analysis rather than purely theoretical knowledge.

You are given an integer array nums of length n.

A subsequence of nums is a sequence that can be derived from nums by deleting zero or more elements without changing the order of the remaining elements. The elements of the subsequence do not need to be contiguous in the original array.

A subsequence is called strictly increasing if every element is strictly greater than the previous one.

Task: Return the length of the longest strictly increasing subsequence of nums.

Example 1

Input:

nums = [10, 9, 2, 5, 3, 7, 101, 18]

One longest strictly increasing subsequence is [2, 3, 7, 101], so the answer is 4.

Output:

4

Example 2

Input:

nums = [0, 1, 0, 3, 2, 3]

One longest strictly increasing subsequence is [0, 1, 2, 3], so the answer is 4.

Output:

4

Example 3

Input:

nums = [7, 7, 7, 7]

Every strictly increasing subsequence has length 1 (any single element), so the answer is 1.

Output:

1

Constraints & Assumptions

  • 1 <= n <= 2 * 10^5, so an $O(n^2)$ solution (~$4 \times 10^{10}$ operations worst case) is too slow; aim for $O(n \log n)$.
  • -10^9 <= nums[i] <= 10^9 — values fit in a 32-bit signed integer, but be mindful of language-specific overflow if you do arithmetic on them (here you only compare, so no overflow risk).
  • "Increasing" means strictly increasing; equal adjacent values do not extend a subsequence.
  • The array is non-empty, so the answer is always at least 1.
  • You are asked only for the length, not the subsequence itself (though reconstruction is a natural follow-up).

Clarifying Questions to Ask

  • Is the required ordering strictly increasing or non-decreasing? (This changes the binary-search bound from lower-bound to upper-bound.)
  • Do I need to return the actual subsequence, or just its length?
  • Can the array be empty, and if so what should I return?
  • Are there constraints on memory (e.g. is $O(n)$ extra space acceptable), and is the input mutable?
  • Could there be duplicate values, and how should ties be handled? (Confirms the strict-vs-non-decreasing decision.)

Hints

Hint 1

Start with the brute force: There is an obvious $O(n^2)$ dynamic program: let $dp[i]$ be the length of the longest strictly increasing subsequence that **ends at index $i$**. Then $dp[i] = 1 + \max(dp[j])$ over all $j < i$ with $nums[j] < nums[i]$. The answer is $\max_i dp[i]$. Getting this right first clarifies the recurrence before you optimize.

Hint 2

Beating O(n^2) — the key insight: To hit $O(n \log n)$, maintain an array `tails`, where `tails[k]` is the **smallest possible tail value** of any strictly increasing subsequence of length $k+1$ seen so far. This array is always sorted, which lets you binary-search it. Keeping tails as small as possible greedily maximizes the room for future extensions.

Hint 3

The per-element update: For each `x = nums[i]`, binary-search `tails` for the **leftmost** position whose value is `>= x` (a lower-bound search). If found, overwrite it with `x` (you found a length-$k+1$ subsequence ending in a smaller tail). If `x` is larger than every tail, append it (you extended the longest run by one). The answer is the final length of `tails`. Note: lower-bound (`>= x`) enforces *strict* increase; an upper-bound (`> x`) would instead count non-decreasing subsequences — a classic off-by-one trap.

Hint 4

Edge cases to confirm: A single-element array returns `1`. An all-equal array (Example 3) returns `1` because each repeat overwrites `tails[0]` rather than appending. Negative numbers and the full $[-10^9, 10^9]$ range need no special handling if comparisons use the raw integers.

Follow-up questions

  • Modify your solution to return the **actual** longest increasing subsequence, not just its length. (Hint: track predecessor indices.)
  • How would you adapt the algorithm to count **non-decreasing** subsequences instead of strictly increasing ones?
  • If the array arrives as a stream and you must report the current LIS length after each new element, what is the per-element cost of your approach?
  • Can you do better than $O(n \log n)$ in any restricted setting (e.g. when values are a permutation of $1..n$, or bounded to a small range)?
  • How would you parallelize or shard this if `n` were $10^9$ and the data did not fit in memory?