Trick is often “verification” being easier vs finding the value. Monotonicity of course is needed ^ on the answer space.
Maximum Average Subarray II ( Really good problem )
Bin search over the answer space. Transform array to be a(i) -= average
Now only need to check if a subarray of size >= k exists with sum >= 0 Can just keep a min prefix sum at the k window start.