Compute longest increasing subsequence length
Company: Pinduoduo
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Coding Question
You are given an integer array `nums`.
Return the **length** of the **longest strictly increasing subsequence** (not necessarily contiguous).
A subsequence is obtained by deleting zero or more elements without changing the order of the remaining elements.
### Examples
- Input: `nums = [10,9,2,5,3,7,101,18]` → Output: `4` (one LIS is `[2,3,7,101]`)
- Input: `nums = [0,1,0,3,2,3]` → Output: `4`
- Input: `nums = [7,7,7,7]` → Output: `1`
### Constraints
- `1 <= nums.length <= 2 * 10^5`
- `-10^9 <= nums[i] <= 10^9`
### Notes
A straightforward dynamic programming solution is `O(n^2)`. Can you derive an optimized approach (commonly described as greedy with binary search) that runs in about `O(n log n)`?
Quick Answer: This question evaluates understanding of sequence analysis and algorithmic problem solving, assessing competency with subsequences, reasoning about complexity, and algorithmic optimization.
Return the length of the longest strictly increasing subsequence using greedy tails and binary search.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([10,9,2,5,3,7,101,18],)
Expected Output: 4
Explanation: Prompt example 1.
Input: ([0,1,0,3,2,3],)
Expected Output: 4
Explanation: Prompt example 2.
Input: ([7,7,7,7],)
Expected Output: 1
Explanation: Strictly increasing rejects equals.
Hints
- Choose a representation that makes the requested operation direct.
- Handle empty inputs and boundary cases first.