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: ```text 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: ```text 4 ``` ### Example 2 Input: ```text nums = [0, 1, 0, 3, 2, 3] ``` One longest strictly increasing subsequence is `[0, 1, 2, 3]`, so the answer is `4`. Output: ```text 4 ``` ### Example 3 Input: ```text nums = [7, 7, 7, 7] ``` Every strictly increasing subsequence has length `1` (any single element), so the answer is `1`. Output: ```text 1 ``` ```hint 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 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 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 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. ``` --- ### 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.) ### What a Strong Answer Covers - **Correct recurrence**: states the $O(n^2)$ DP (`dp[i]` = LIS ending at `i`) cleanly, then motivates the patience-sorting / `tails` optimization rather than presenting it as magic. - **Optimal complexity**: arrives at $O(n \log n)$ time and $O(n)$ space, and justifies why $O(n^2)$ fails the $2 \times 10^5$ bound. - **Strictness handled precisely**: uses a lower-bound (`>= x`) search and can explain why upper-bound would compute the non-decreasing variant — and that `tails` is **not** itself a valid subsequence, only a length witness. - **Edge cases**: empty/singleton/all-equal arrays, negatives, large ranges. - **Clean implementation**: correct binary search (no off-by-one), idiomatic use of a standard library bisection (`bisect_left`, `lower_bound`) where available. ### 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?