300. Longest Increasing Subsequence
Description
Given an unsorted array of integers, find the length of longest increasing subsequence.
For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length. Your algorithm should run in O(n2) complexity.
Solution
- O(n^2): save length in a second list
- O(nlogn): Binary search. We maintain a list, which contains the longest sublist. For each step, we do binary search on the left if current num is smaller than the right most element of the list.
Russian Doll Envelopes
Descripton
You have a number of envelopes with widths and heights given as a pair of integers (w, h). One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope.
What is the maximum number of envelopes can you Russian doll? (put one inside other)
Solution
- Similar to 300, there are two ways to solve the problem. An O(n^2) brute force one and O(nlogn). O(n^2) solution is simple.
- O(nlogn) solution needs binary search as well as special sort for sequences. We need to sort in ascending width and decreasing height. Then redo the