Maximize minimum after K decrements
Company: MathWorks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
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`.
Quick Answer: 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.
Perform exactly K decrements on array elements and maximize the final minimum value.
Constraints
- 1 <= len(A)
- K >= 0
Examples
Input: ([5, 1, 7], 3)
Expected Output: 1
Explanation: Decrement values above the minimum.
Input: ([1, 1], 1)
Expected Output: 0
Explanation: Once all values equal the minimum, one decrement lowers the minimum.
Hints
- First spend decrements on elements above the current minimum; only extra decrements force the minimum lower.