binary search

A multi-part favorite at OpenAI-style screens: simple store, then time travel, then deletes that don't actually delete. The append-only insight plus one bisect call solves the whole thing, if you set up the invariant correctly.

Almost everyone reaches the O(n²) DP. The signal interviewers want is the O(n log n) patience-sorting trick, plus the honesty to say the array you build along the way is not itself the answer subsequence.

The O(log(min(m,n))) answer binary-searches a partition on the shorter array so the left halves of both arrays together hold exactly half the elements. The whole problem is one invariant plus careful boundary handling for empty sides and odd versus even totals.

A sorted array got rotated at an unknown pivot and you still have to find a target in O(log n). The trick is deciding which half is sorted at every step. Here's the clean invariant, and the duplicates follow-up that quietly breaks the log-n promise.