Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 2439 with 18 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 2439 # by problem number
lcpy gen -s minimize_maximum_of_array # by problem name
nums comprising of n non-negative integers.
In one operation, you must:
i such that 1 <= i < n and nums[i] > 0.nums[i] by 1.nums[i - 1] by 1.nums after performing any number of operations.
Input: nums = [3,7,1,6]
Output: 5
Explanation:
One set of optimal operations is as follows:
1. Choose i = 1, and nums becomes [4,6,1,6].
2. Choose i = 3, and nums becomes [4,6,2,5].
3. Choose i = 1, and nums becomes [5,5,2,5].
The maximum integer of nums is 5. It can be shown that the maximum number cannot be less than 5.
Therefore, we return 5.
Input: nums = [10,1]
Output: 10
Explanation:
It is optimal to leave nums as is, and since 10 is the maximum value, we return 10.
class Solution:
# Time: O(n)
# Space: O(1)
def minimize_array_value(self, nums: list[int]) -> int:
# Operations never change a prefix sum, so every prefix must be levelable
# under the answer: prefix sum <= answer * prefix length. The answer is the
# largest such ceil(prefix_sum / length) over all prefixes.
ans = 0
prefix = 0
for i, num in enumerate(nums):
prefix += num
ans = max(ans, -(-prefix // (i + 1)))
return ans
| Time | Space |
|---|---|
| O(n) | O(1) |