Minimum Number of Seconds to Make Mountain Height Zero
MediumUpdated: Aug 2, 2025
Practice on:
Problem
You are given an integer mountainHeight denoting the height of a mountain.
You are also given an integer array workerTimes representing the work time of workers in seconds.
The workers work simultaneously to reduce the height of the mountain.
For worker i:
- To decrease the mountain's height by
x, it takesworkerTimes[i] + workerTimes[i] * 2 + ... + workerTimes[i] * xseconds. For example: - To reduce the height of the mountain by 1, it takes
workerTimes[i]seconds. - To reduce the height of the mountain by 2, it takes
workerTimes[i] + workerTimes[i] * 2seconds, and so on.
Return an integer representing the minimum number of seconds required for the workers to make the height of the mountain 0.
Examples
Example 1
Input: mountainHeight = 4, workerTimes = [2,1,1]
Output: 3
Explanation:
One way the height of the mountain can be reduced to 0 is:
* Worker 0 reduces the height by 1, taking `workerTimes[0] = 2` seconds.
* Worker 1 reduces the height by 2, taking `workerTimes[1] + workerTimes[1] * 2 = 3` seconds.
* Worker 2 reduces the height by 1, taking `workerTimes[2] = 1` second.
Since they work simultaneously, the minimum time needed is `max(2, 3, 1) = 3`
seconds.
Example 2
Input: mountainHeight = 10, workerTimes = [3,2,2,4]
Output: 12
Explanation:
* Worker 0 reduces the height by 2, taking `workerTimes[0] + workerTimes[0] * 2 = 9` seconds.
* Worker 1 reduces the height by 3, taking `workerTimes[1] + workerTimes[1] * 2 + workerTimes[1] * 3 = 12` seconds.
* Worker 2 reduces the height by 3, taking `workerTimes[2] + workerTimes[2] * 2 + workerTimes[2] * 3 = 12` seconds.
* Worker 3 reduces the height by 2, taking `workerTimes[3] + workerTimes[3] * 2 = 12` seconds.
The number of seconds needed is `max(9, 12, 12, 12) = 12` seconds.
Example 3
Input: mountainHeight = 5, workerTimes = [1]
Output: 15
Explanation:
There is only one worker in this example, so the answer is `workerTimes[0] +
workerTimes[0] * 2 + workerTimes[0] * 3 + workerTimes[0] * 4 + workerTimes[0]
* 5 = 15`.
Constraints
1 <= mountainHeight <= 10^51 <= workerTimes.length <= 10^41 <= workerTimes[i] <= 10^6
Solution
Method 1 – Greedy + Binary Search (Partitioning)
Intuition
Each worker can reduce some part of the mountain, and the time for each is the sum of an arithmetic progression. We want to partition the mountainHeight among workers so that the maximum time among all workers is minimized. This is a classic load balancing problem solved by binary search.
Approach
- Use binary search for the answer: the minimum possible max time.
- For each candidate time, check if it's possible to partition the mountainHeight among workers so that no worker exceeds the time.
- For each worker, compute the max height they can reduce in the given time.
- Sum up all max heights; if >= mountainHeight, it's feasible.
- Return the minimum feasible time.
Code
C++
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int minSeconds(int mountainHeight, vector<int>& workerTimes) {
int left = 1, right = 1e15, ans = right;
while (left <= right) {
long long mid = left + (right - left) / 2;
long long total = 0;
for (int wt : workerTimes) {
long long l = 0, r = mountainHeight;
while (l < r) {
long long m = (l + r + 1) / 2;
long long t = wt * m * (m + 1) / 2;
if (t <= mid) l = m;
else r = m - 1;
}
total += l;
}
if (total >= mountainHeight) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
}
};
Go
func minSeconds(mountainHeight int, workerTimes []int) int64 {
left, right := int64(1), int64(1e15)
ans := right
for left <= right {
mid := (left + right) / 2
total := int64(0)
for _, wt := range workerTimes {
l, r := int64(0), int64(mountainHeight)
for l < r {
m := (l + r + 1) / 2
t := int64(wt) * m * (m + 1) / 2
if t <= mid {
l = m
} else {
r = m - 1
}
}
total += l
}
if total >= int64(mountainHeight) {
ans = mid
right = mid - 1
} else {
left = mid + 1
}
}
return ans
}
Java
class Solution {
public long minSeconds(int mountainHeight, int[] workerTimes) {
long left = 1, right = (long)1e15, ans = right;
while (left <= right) {
long mid = left + (right - left) / 2;
long total = 0;
for (int wt : workerTimes) {
long l = 0, r = mountainHeight;
while (l < r) {
long m = (l + r + 1) / 2;
long t = wt * m * (m + 1) / 2;
if (t <= mid) l = m;
else r = m - 1;
}
total += l;
}
if (total >= mountainHeight) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
}
}
Kotlin
class Solution {
fun minSeconds(mountainHeight: Int, workerTimes: IntArray): Long {
var left = 1L; var right = 1_000_000_000_000_000L; var ans = right
while (left <= right) {
val mid = (left + right) / 2
var total = 0L
for (wt in workerTimes) {
var l = 0L; var r = mountainHeight.toLong()
while (l < r) {
val m = (l + r + 1) / 2
val t = wt * m * (m + 1) / 2
if (t <= mid) l = m else r = m - 1
}
total += l
}
if (total >= mountainHeight) {
ans = mid
right = mid - 1
} else {
left = mid + 1
}
}
return ans
}
}
Python
class Solution:
def minSeconds(self, mountainHeight: int, workerTimes: list[int]) -> int:
left, right = 1, 10**15
ans = right
while left <= right:
mid = (left + right) // 2
total = 0
for wt in workerTimes:
l, r = 0, mountainHeight
while l < r:
m = (l + r + 1) // 2
t = wt * m * (m + 1) // 2
if t <= mid:
l = m
else:
r = m - 1
total += l
if total >= mountainHeight:
ans = mid
right = mid - 1
else:
left = mid + 1
return ans
Rust
impl Solution {
pub fn min_seconds(mountain_height: i32, worker_times: Vec<i32>) -> i64 {
let (mut left, mut right) = (1i64, 1e15 as i64);
let mut ans = right;
while left <= right {
let mid = (left + right) / 2;
let mut total = 0i64;
for &wt in &worker_times {
let (mut l, mut r) = (0i64, mountain_height as i64);
while l < r {
let m = (l + r + 1) / 2;
let t = wt as i64 * m * (m + 1) / 2;
if t <= mid { l = m; } else { r = m - 1; }
}
total += l;
}
if total >= mountain_height as i64 {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
ans
}
}
TypeScript
class Solution {
minSeconds(mountainHeight: number, workerTimes: number[]): number {
let left = 1, right = 1e15, ans = right;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
let total = 0;
for (const wt of workerTimes) {
let l = 0, r = mountainHeight;
while (l < r) {
let m = Math.floor((l + r + 1) / 2);
let t = wt * m * (m + 1) / 2;
if (t <= mid) l = m;
else r = m - 1;
}
total += l;
}
if (total >= mountainHeight) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
}
}
Complexity
- ⏰ Time complexity:
O(W * log(H) * log(T))— W = number of workers, H = mountainHeight, T = max seconds. - 🧺 Space complexity:
O(1)— constant extra space.