# Implementation of Patience Sort | Longest Increasing Subsequence in O(n log n) time

**Solution:**

```
class Solution {
public int lengthOfLIS(int[] nums) {
TreeSet<Integer> set = new TreeSet<>();
for(int i=0;i<nums.length;i++)
{
Integer x=set.ceiling(nums[i]);
if(x!=null)
{
set.remove(x);
}
set.add(nums[i]);
}
return set.size();
}
}
```