Answer: Thoughtworks OA Question 2024 August | DP | on-campus

Solution: Longest Increasing Subsequence — Binary Search + Patience Sort Approach The classic O(N²) DP works but we can achieve O(N log N) using a Patience Sort inspired approach with Binary Search. We maintain a tails array where tails[i] is the smallest tail element of all increasing subsequences of length i+1. For each number: use binary search to find the first element in tails that is >= the current number. Replace it with the current number (keeping tails as small ...