Minimum Number of Seconds to Make Mountain Height Zero
MedPrompt
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.
- To reduce the height of the mountain by 1, it takes
Return an integer representing the minimum number of seconds required for the workers to make the height of the mountain 0.
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] = 2seconds. - Worker 1 reduces the height by 2, taking
workerTimes[1] + workerTimes[1] * 2 = 3seconds. - Worker 2 reduces the height by 1, taking
workerTimes[2] = 1second.
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 = 9seconds. - Worker 1 reduces the height by 3, taking
workerTimes[1] + workerTimes[1] * 2 + workerTimes[1] * 3 = 12seconds. - Worker 2 reduces the height by 3, taking
workerTimes[2] + workerTimes[2] * 2 + workerTimes[2] * 3 = 12seconds. - Worker 3 reduces the height by 2, taking
workerTimes[3] + workerTimes[3] * 2 = 12seconds.
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 <= 1051 <= workerTimes.length <= 1041 <= workerTimes[i] <= 106
Approaches
3 approaches with complexity analysis and trade-offs.
This approach iterates through time, second by second, starting from 1. For each second t, it checks if it's possible for the workers to collectively reduce the mountain's height to zero within that time. The first time t for which this is possible is the minimum time required.
Algorithm
- Initialize
time = 1. - Start an infinite loop.
- Inside the loop, calculate the total height that can be reduced by all workers within the current
time.- Initialize
totalHeightReduced = 0. - For each
workerTimeinworkerTimes:- Find the maximum height
hthis worker can reduce. This can be done by solvingworkerTime * h * (h + 1) / 2 <= timefor the largest integerh. A simple way is to iteratehfrom 1 upwards until the time taken exceeds the currenttime. - Add this
htototalHeightReduced.
- Find the maximum height
- Initialize
- Check if
totalHeightReduced >= mountainHeight. - If it is,
timeis the minimum time required. Returntime. - If not, increment
timeand continue the loop.
Walkthrough
The core idea is to test every possible time value t starting from 1. For a given time t, we need a helper function, let's call it canReduce(t), to determine if the total work done can meet or exceed mountainHeight. Inside canReduce(t), for each worker, we calculate the maximum height they can reduce. The time taken for a worker i to reduce height by h is workerTimes[i] * h * (h + 1) / 2. We need to find the largest integer h such that this time is less than or equal to t. We can find this h by iterating from h=1 upwards until the time exceeds t. Summing up the maximum possible height reduction for all workers gives the total reduction possible within time t. If this total reduction is at least mountainHeight, canReduce(t) returns true. The main function starts a loop t = 1, 2, 3, ... and calls canReduce(t). The first t that returns true is our answer.
class Solution { // This approach is too slow and will time out. public long minSeconds(int mountainHeight, int[] workerTimes) { long time = 1; while (true) { if (canReduce(mountainHeight, workerTimes, time)) { return time; } time++; } } private boolean canReduce(int mountainHeight, int[] workerTimes, long time) { long totalHeightReduced = 0; for (int wt : workerTimes) { long h = 0; while (true) { long nextH = h + 1; // Using long to prevent overflow for timeNeeded long timeNeeded = (long)wt * nextH * (nextH + 1) / 2; if (timeNeeded > time) { break; } h = nextH; } totalHeightReduced += h; if (totalHeightReduced >= mountainHeight) { return true; } } return totalHeightReduced >= mountainHeight; }}Complexity
Time
O(T_opt * N * H), where `T_opt` is the optimal time, `N` is the number of workers, and `H` is the mountain height. This is infeasible as `T_opt` can be very large.
Space
O(1) extra space.
Trade-offs
Pros
Simple to understand and implement.
Cons
Extremely inefficient. The minimum time can be very large (up to ~10^16), leading to a Time Limit Exceeded (TLE) error on most platforms.
Solutions
Solution
class Solution {private int mountainHeight;private int[] workerTimes;public long minNumberOfSeconds(int mountainHeight, int[] workerTimes) { this.mountainHeight = mountainHeight; this.workerTimes = workerTimes; long l = 1, r = (long)1 e16; while (l < r) { long mid = (l + r) >> 1; if (check(mid)) { r = mid; } else { l = mid + 1; } } return l; }private boolean check(long t) { long h = 0; for (int wt : workerTimes) { h += (long)(Math.sqrt(t * 2.0 / wt + 0.25) - 0.5); } return h >= mountainHeight; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.