Coding questions · MathWorks

Maximize minimum after K decrements

This Coding & Algorithms question evaluates algorithmic problem-solving skills in array manipulation and constrained optimization, testing competency in reasoning about value distribution, large numeric bounds, and performance under tight complexity limits.

You are given an integer array A of length N and an integer K.

You must perform exactly K operations. In each operation, choose any index i and do A[i] = A[i] - 1.

After all K operations, let min(A) be the minimum value in the array. Your goal is to choose the operations to maximize min(A).

Return the maximum possible value of min(A) after exactly K operations.

Input

A: array of N integers
K: non-negative integer

Output

An integer: the maximum achievable minimum value.

Notes / Constraints (reasonable for interviews)

1 <= N <= 2e5
-1e9 <= A[i] <= 1e9
0 <= K <= 1e18

Example

A = [5, 1, 7], K = 3
- One optimal strategy is to decrement 7 three times → [5, 1, 4], so min(A) = 1.
- The answer is 1.

Maximize Minimum After K Decrements

Perform exactly K decrements on array elements and maximize the final minimum value.

Hints

First spend decrements on elements above the current minimum; only extra decrements force the minimum lower.