LeetMotion
Given an integer array nums, return the length of the longest strictly increasing subsequence.
Example 1:
Input: nums = [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Example 2:
Input: nums = [0,1,0,3,2,3] Output: 4
Example 3:
Input: nums = [7,7,7,7,7,7,7] Output: 1
Constraints:
1 <= nums.length <= 2500-104 <= nums[i] <= 104
Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?
Why this is a Binary Search problem
Binary search maintains a [lo, hi] search boundary and repeatedly narrows it by half. At each step, it computes mid and decides — based on a monotonic condition — whether the answer lies in the left half or right half. It works on any problem where the answer space is monotonic.
Maintain lo and hi as the valid answer range. At each mid, ask: "Is this too small or too large?" Then eliminate the dead half.
Think of a number guessing game: "Is your number higher or lower?" Each answer eliminates half the possibilities. Binary search applies this to arrays — but also to abstract answer spaces like "minimum capacity", "minimum days", or "k-th smallest element".
From brute force to optimal — understand every step of the journey
The real power of binary search is not just searching sorted arrays — it's "binary search on the answer". Whenever you have a monotonic decision function ("can I achieve X with capacity Y?"), you can binary search over Y. This turns many hard problems into "check feasibility" + binary search. The hardest part is defining lo, hi, and the feasibility check correctly.