Searching & Recursion
Mastering advanced searching techniques and the recursive thinking behind backtracking is crucial for solving optimization and combinatorial problems.
This advanced technique involves performing a binary search on the range of possible answers to a problem, rather than on the input data itself. It is applicable when the problem has a monotonic property.
Example Problems:
Split Array Largest SumKoko Eating BananasCapacity To Ship Packages Within D Days
Solution Spotlight: Split Array Largest Sum
This solution binary searches for the minimum possible value of the "largest subarray sum". The
isPossible helper function greedily checks if a given maxSumAllowed is feasible in O(n) time. This transforms the problem into a search over a monotonic answer space.SplitArrayLargestSum.java
Loading code syntax...