Design Algorithm for Longest Increasing Subsequence Length

Scenario

Programming assessment and infrastructure panel

Question

Design an algorithm to return the length of the Longest Increasing Subsequence of an array.

Seat students so that no two listed friends sit next to each other; provide algorithm and complexity.

How would you sort a file containing 50 numbers? How would your approach change for a 1-million-number file stored on disk?

Hints

Use O(n log n) patience sorting + binary search; graph/constraint satisfaction; external merge-sort for large files.

Length of Longest Increasing Subsequence

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence derived from the array by deleting zero or more elements without changing the order of the remaining elements. The subsequence must be strictly increasing (each chosen element strictly greater than the previous one) but the chosen elements need not be contiguous.

Example 1:

Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4

Explanation: One longest increasing subsequence is [2, 3, 7, 18] (or [2, 3, 7, 101]), which has length 4.

Example 2:

Input: nums = [0, 1, 0, 3, 2, 3]
Output: 4

Explanation: A longest increasing subsequence is [0, 1, 2, 3].

Example 3:

Input: nums = [7, 7, 7, 7, 7, 7, 7]
Output: 1

Explanation: Equal elements are not strictly increasing, so the best length is 1.

Aim for an O(n log n) solution.

Constraints

• 0 <= len(nums) <= 2500
• -10^4 <= nums[i] <= 10^4
• The subsequence must be strictly increasing (duplicates do not extend it).

Hints

1. A patience-sorting approach maintains a list tails, where tails[k] is the smallest possible tail value of any increasing subsequence of length k+1.
2. For each element x, binary-search for the leftmost position in tails whose value is >= x; replace it (or append x if x is larger than all tails). The answer is len(tails).
3. Use bisect_left (not bisect_right) so that equal values overwrite rather than extend, enforcing STRICT increase.