18 / 75
Medium
Longest Increasing Subsequence
#18dynamic-programmingbinary-searcharray
Find length of longest strictly increasing subsequence using binary search on tails array.
Example:
Input:
[10,9,2,5,3,7,101,18]Output:
4 (subsequence: [2,3,7,101])Common Mistakes:
- Confusing subsequence with subarray (contiguous)
- Not handling binary search negative return value correctly
- Using O(n²) DP when O(n log n) binary search solution exists
Notes:
Patience sorting algorithm. Time O(n log n), Space O(n). DP solution is O(n²) but easier to understand.
💻
Java Solution Hidden
Enable “Show Full Solution” to view the code
Find length of longest strictly increasing subsequence using binary search on tails array.
Example:
Input:
[10,9,2,5,3,7,101,18]Output:
4 (subsequence: [2,3,7,101])Common Mistakes:
- Confusing subsequence with subarray (contiguous)
- Not handling binary search negative return value correctly
- Using O(n²) DP when O(n log n) binary search solution exists
Notes:
Patience sorting algorithm. Time O(n log n), Space O(n). DP solution is O(n²) but easier to understand.
18/75
Longest Increasing Subsequence