We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimize Maximum of Array

Number: 2530

Difficulty: Medium

Paid? No

Companies: Oracle, Paytm

Problem Description

Given a 0-indexed array nums of non-negative integers, you can perform an operation where you choose an index i (1 <= i < n) with nums[i] > 0, then decrease nums[i] by 1 and increase nums[i-1] by 1. The goal is to minimize the maximum value in the array after performing any number of operations.

Key Insights

  • The operations only allow shifting value to the left.
  • The prefix sums of the array remain invariant; only their distribution can be balanced.
  • The minimum possible maximum value is determined by the largest needed average of the prefix, rounded up.
  • For each index i, the achievable maximum value must be at least ceil(prefixSum[0...i] / (i + 1)).

Space and Time Complexity

Time Complexity: O(n) - We iterate through the array once. Space Complexity: O(1) - Only a few variables are used.

Solution

We observe that the operations allow "pushing" excess from right to left. This means that the sum of the first i elements (prefix sum) cannot be reduced by any series of operations, though it can be redistributed. To keep all numbers as balanced as possible, the highest value in the prefix will be determined by the ceiling of (sum of the prefix)/(length of the prefix). Thus, for each index, we compute the running sum and take the maximum of ceil(prefixSum / (i + 1)). This maximum will be the minimum achievable maximum value of the array after redistributions.

Code Solutions

import math

def minimizeArrayValue(nums):
    prefix_sum = 0
    answer = 0
    # Iterate through each number in the array
    for i, num in enumerate(nums):
        prefix_sum += num  # Update the running prefix sum
        # Calculate the minimum possible value at index i after moves:
        # It must be at least the ceiling of the average of the prefix sum.
        answer = max(answer, math.ceil(prefix_sum / (i + 1)))
    return answer

# Example usage:
nums = [3, 7, 1, 6]
print(minimizeArrayValue(nums))  # Expected output: 5
← Back to All Questions