Minimize Maximum of Array - Practice Coding Problems

Minimize Maximum of Array - Problem

Array Binary Search Dynamic Programming Greedy Prefix Sum Medium

You are given a 0-indexed array nums comprising of n non-negative integers.

In one operation, you must:

Choose an integer i such that 1 <= i < n and nums[i] > 0.
Decrease nums[i] by 1.
Increase nums[i - 1] by 1.

Return the minimum possible value of the maximum integer of nums after performing any number of operations.

Input & Output

Example 1 — Basic Case

$ Input: nums = [3,7,1,6]

› Output: 5

💡 Note: We can move values leftward: 7→6 (move 1 left), then distribute optimally to get maximum of 5

Example 2 — Already Optimal

$ Input: nums = [10,1]

› Output: 10

💡 Note: Cannot reduce the maximum since we can only move from right to left, and leftmost is already maximum

Example 3 — Equal Distribution

$ Input: nums = [4,9,7,4]

› Output: 6

💡 Note: Optimal redistribution gives us [6,6,6,6] with maximum 6

Constraints

n == nums.length
2 ≤ n ≤ 10⁵
0 ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Array

Original array with varying values

Leftward Operations

Move values from right to left to balance

Minimized Maximum

Find the smallest possible maximum value

Key Takeaway

🎯 Key Insight: Binary search on the minimum achievable maximum value, since we can only redistribute leftward

Asked in

G Google 25 f Meta 18 a Amazon 15

The key insight is that we can only move values leftward, so we binary search on the minimum achievable maximum value. For each candidate maximum, we simulate the redistribution process to check feasibility. The optimal approach uses binary search on the answer space with O(n log(sum)) time complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Prefix Sum Approach	O(n²)	O(n)	Calculate prefix sums and find optimal distribution using averages
Brute Force Simulation	O(n × sum²)	O(1)	Try all possible operations until no more improvements can be made
Binary Search on Answer	O(n × log(sum))	O(1)	Binary search on the possible maximum value, check if achievable

Prefix Sum Approach — Algorithm Steps

Calculate prefix sums
For each position, find optimal average
Determine maximum needed at each position
Return overall maximum

Visualization

Tap to expand

Step-by-Step Walkthrough

Prefix Sums

Calculate cumulative sums at each position

Average Distribution

Find average value that can be achieved

Find Maximum

Determine minimum possible maximum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long long max(long long a, long long b) {
    return a > b ? a : b;
}

int solution(int* nums, int size) {
    long long* prefix = (long long*)calloc(size + 1, sizeof(long long));
    for (int i = 0; i < size; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    
    long long maxVal = nums[0];
    for (int i = 0; i < size; i++) {
        long long avg = prefix[i + 1] / (i + 1);
        long long remainder = prefix[i + 1] % (i + 1);
        
        long long currentMax;
        if (i < remainder) {
            currentMax = avg + 1;
        } else {
            currentMax = avg;
        }
        
        maxVal = max(maxVal, currentMax);
    }
    
    free(prefix);
    return (int)maxVal;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000], size = 0;
    char* token = strtok(line + 1, ",]");
    while (token) {
        nums[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(nums, size));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Single pass through array but complex calculations at each step

⚠ Quadratic Growth

Space Complexity

O(n)

Array to store prefix sums

⚡ Linearithmic Space

32.4K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Prefix Sum Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler