Minimize Maximum of Array
Medium · Binary Search · Array · Binary Search · Greedy · Prefix Sum
Problem
You are given an array nums of n non-negative integers. One operation picks an index i with 1 0, takes one unit from nums[i] and adds it to nums[i - 1]. Units can only move one step to the left, never to the right.
After any number of operations, return the smallest possible value of the largest element of nums.
Examples
Input: nums = [2,8,2,6] Output: 5
Moving units left reaches [5, 5, 4, 4]. The first two hold 10 between them, so their maximum cannot go below 5.
Input: nums = [9,0,3] Output: 9
Nothing moves right, so the leading 9 stays.
Input: nums = [0,0,7] Output: 3
Spread over three slots, 7 needs a maximum of at least 3.
Constraints
- 2 <= n <= 10^5
- 0 <= nums[i] <= 10^9
Approaches
- Binary search the answer — time O(n log M), space O(1)
Follow-up
The prefix-average bound gives the answer in one pass. The binary search is the general tool when no closed form is known. The use cases mirror the direction of the moves and ask only the yes/no question for a given limit.
Related problems
Start free on Cariara · Coding problems · System design studio
