Binary Search the Result

Summary

In this post, I will introduce some problems which could binary search the best result.

The problems in this category usually ask for a best value. The value could fall into the range of [min, max]. Another important property is that if the value at the middle is not achievable, we could eliminate a half the range.

A possible solution is that we binary search this best value, and check if it is achievable or not. Repeat until we get a single answer.

OJ

	Trick	Difficulty
LC 644 Maximum Average Subarray II	Binary Search Result + Greedy + Maximum Subarray Sum	6 points
LC 410 Split Array Largest Sum	Binary Search Result + Greedy	6-7 points

Details

LC 410 Split Array Largest Sum

Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.

The DP solution is not difficult.

// alg[n][M] = 0
alg[i][m] = 
   min{max(alg[j + 1][m - 1], sum[i, ..., j]), for j in [i, ..., n - 1]}

The problem could be solved via binary searching the result.

1. The minimum value possible is min_element(nums); the maximum value possible is sum(nums)
2. If a value mid is not possible, it is not possible for values smaller than mid;
3. check could be done in O(n) by greedily dividing groups: from left to right, as long as current sum is smaller than mid, insert it into the current group. If finally count <= K, we know mid is possible, since we could further divide some groups but not increase the largest sum. The tricky part is if count > K, we know all smaller values are not possible. This could be proved by contradiction. If a smaller value is possible, the first subarray would be smaller, so is the second array, which causes the number of subarrays will be not smaller than count, which causes the contradiction.