Cross the Threshold

Problem Overview

• Find the maximum integer barrier so the sum of final energies max(initialEnergy[i] − barrier, 0) is ≥ th.
• Input: initialEnergy[n], th. Output: the maximum barrier. Constraints: 2≤n≤1e5, 1≤initialEnergy[i]≤1e9, 1≤th≤1e14; a non-negative barrier exists.
• Domain: particles losing energy to a uniform barrier, ensuring total energy meets a threshold.
• From Snowflake interviews; a coding interview problem and interview question.