Katkat
Back

Maximize minimum after K decrements

MathWorksSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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.