3296. Minimum Number of Seconds to Make Mountain Height Zero

The 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 takes workerTimes[i] + workerTimes[i] * 2 + ... + workerTimes[i] * x seconds. 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] * 2 seconds, and so on.

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] = 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⁵
1 <= workerTimes.length <= 10⁴
1 <= workerTimes[i] <= 10⁶

Approach overview

Problem Overview: You are given a mountain of height H and multiple workers. The j-th unit removed by worker i takes time[i] * j seconds, so the total time for k units becomes time[i] * (k * (k + 1) / 2). The goal is to determine the minimum number of seconds required for all workers combined to reduce the mountain height to zero.

Approach 1: Greedy Simulation with Heap (Priority Queue) (Time: O(H log n), Space: O(n))

Simulate the process of assigning work units to workers in chronological order. Each worker’s next completion time follows an arithmetic pattern: t, 3t, 6t, ... because every additional unit costs j * t seconds. Use a min-heap to track the next available completion event across all workers. Pop the earliest event, assign one unit of work, then push the worker back with the updated completion time. Repeat until H units are removed. This greedy strategy always processes the earliest finishing task first, which mirrors how the real timeline progresses. Useful for understanding the process but becomes slow when H is large.

Approach 2: Binary Search on Time (Optimal) (Time: O(n log T), Space: O(1))

Instead of simulating every unit removal, search for the smallest time T such that workers can remove at least H units in that time. For each worker with base time t, solve the inequality t * (k * (k + 1) / 2) ≤ T to determine the maximum units k they can remove. This comes from the triangular sum of increasing work costs. Rearranging gives a quadratic equation that can be solved using math or binary search per worker. Sum all workers' contributions and check if the total reaches H. Because feasibility is monotonic with respect to time, binary search efficiently finds the minimum valid T.

This approach combines mathematical reasoning with monotonic search. Each feasibility check iterates through workers and computes their maximum removable units in constant time.

Approach 3: Dynamic Programming (Time: O(n * H), Space: O(H))

Dynamic programming can model the problem as distributing H units among workers while minimizing total time. Let dp[h] represent the minimum time needed to remove h units. For each worker, iterate possible units they could remove and update the DP state using the triangular time cost t * (k * (k + 1) / 2). While this approach clearly models the incremental cost structure, its complexity grows quickly with large heights. It is mainly useful for understanding the cost relationship rather than as a production solution.

Recommended for interviews: The binary search approach is what interviewers typically expect. A brute-force or heap simulation shows you understand the timeline of work distribution, but recognizing the monotonic property and converting the worker cost into a mathematical constraint demonstrates stronger algorithmic insight. Mentioning the greedy simulation or heap idea before optimizing to binary search often earns extra credit in interviews.

Approach 1: Binary Search on Max Time

This approach utilizes binary search to find the minimum possible time required by any worker to reduce the mountain's height to zero. We assume an upper bound on the time as the sum of individual times required if one worker does all the work. We binary search this time and check if it's feasible for all workers to collectively bring down the mountain within this time frame.

Python

def canReduce(mountainHeight, workerTimes, maxTime):
    currentHeight = 0
    for time in workerTimes:
        max_reduce = 0
        seconds = 0
        while max_reduce <= mountainHeight and seconds + time * (max_reduce + 1) <= maxTime:
            max_reduce += 1
            seconds += time * max_reduce
        currentHeight += max_reduce
        if currentHeight >= mountainHeight:
            return True
    return currentHeight >= mountainHeight


def minSecondsToReduce(mountainHeight, workerTimes):
    left, right = 0, sum(workerTimes) * mountainHeight
    while left < right:
        mid = left + (right - left) // 2
        if canReduce(mountainHeight, workerTimes, mid):
            right = mid
        else:
            left = mid + 1
    return left

# Example usage
mountainHeight = 10
workerTimes = [3, 2, 2, 4]
print(minSecondsToReduce(mountainHeight, workerTimes))  # Output: 12

JavaScript

function canReduce(mountainHeight, workerTimes, maxTime) {
    let currentHeight = 0;
    for (const time of workerTimes) {
        let maxReduce = 0;
        let seconds = 0;
        while (maxReduce <= mountainHeight && seconds + time * (maxReduce + 1) <= maxTime) {
            maxReduce++;
            seconds += time * maxReduce;
        }
        currentHeight += maxReduce;
        if (currentHeight >= mountainHeight) {
            return true;
        }
    }
    return currentHeight >= mountainHeight;
}

function minSecondsToReduce(mountainHeight, workerTimes) {
    let left = 0, right = workerTimes.reduce((a, b) => a + b, 0) * mountainHeight;
    while (left < right) {
        const mid = Math.floor(left + (right - left) / 2);
        if (canReduce(mountainHeight, workerTimes, mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

// Example usage
const mountainHeight = 10;
const workerTimes = [3, 2, 2, 4];
console.log(minSecondsToReduce(mountainHeight, workerTimes));  // Output: 12

The solution defines a helper function, canReduce(), that checks if the mountain can be reduced within a given maximum time per worker using a greedy approach. The primary function minSecondsToReduce() performs binary search on the time to find this minimum feasible time.

Complexity

Time Complexity: O(n * log(m * h)) where n is the number of workers, m is the maximum worker time, and h is the mountain height.

Space Complexity: O(1), as it uses a constant amount of space.

Try this approach in the editor

Approach 2: Dynamic Programming

In this approach, a dynamic programming table is used to compute the minimum time required to reduce a mountain of a certain height using previous calculations. We iteratively build up the solution by considering each worker up to a given height.

Java

import java.util.Arrays;

public class Solution {
    public int minSecondsToReduce(int mountainHeight, int[] workerTimes) {
        int[] dp = new int[mountainHeight + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int time : workerTimes) {
            for (int h = 0; h <= mountainHeight; ++h) {
                if (dp[h] != Integer.MAX_VALUE) {
                    int currentTime = 0;
                    int height = h;
                    for (int i = 1; height + i <= mountainHeight; ++i) {
                        currentTime += time * i;
                        dp[height + i] = Math.min(dp[height + i], dp[h] + currentTime);
                    }
                }
            }
        }
        return dp[mountainHeight];
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int mountainHeight = 10;
        int[] workerTimes = {3, 2, 2, 4};
        System.out.println(solution.minSecondsToReduce(mountainHeight, workerTimes)); // Output: 12
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

int minSecondsToReduce(int mountainHeight, std::vector<int>& workerTimes) {
    std::vector<int> dp(mountainHeight + 1, INT_MAX);
    dp[0] = 0;
    for (int time : workerTimes) {
        for (int h = 0; h <= mountainHeight; ++h) {
            if (dp[h] != INT_MAX) {
                int currentTime = 0;
                int height = h;
                for (int i = 1; height + i <= mountainHeight; ++i) {
                    currentTime += time * i;
                    dp[height + i] = std::min(dp[height + i], dp[h] + currentTime);
                }
            }
        }
    }
    return dp[mountainHeight];
}

int main() {
    int mountainHeight = 10;
    std::vector<int> workerTimes = {3, 2, 2, 4};
    std::cout << minSecondsToReduce(mountainHeight, workerTimes) << std::endl; // Output: 12
    return 0;
}

This Java solution uses a similar DP table approach. Here, we start with each worker's time and calculate valid height reductions, updating the minimum seconds required for each height incrementally in the DP table.

Complexity

Time Complexity: O(n * h^2), where n is the number of workers, and h is the mountain height. This is not optimal for high mountain heights.

Space Complexity: O(h), where h is the mountain height.

Try this approach in the editor

Approach 3: Binary Search

We notice that if all workers can reduce the mountain height to 0 in t seconds, then for any t' > t, the workers can also reduce the mountain height to 0 in t' seconds. Therefore, we can use binary search to find the minimum t such that the workers can reduce the mountain height to 0 in t seconds.

We define a function check(t), which indicates whether the workers can reduce the mountain height to 0 in t seconds. Specifically, we iterate through each worker. For the current worker workerTimes[i], assuming they reduce the height by h' in t seconds, we can derive the inequality:

$\left(1 + h'\right) cdot \frac{h'}{2} cdot workerTimes[i] leq t

Solving the inequality, we get:

h' leq \left\lfloor \sqrt{\frac{2t}{workerTimes[i]} + \frac{1}{4}} - \frac{1}{2} \right\rfloor

We can sum up all the h' values for the workers to get the total reduced height h. If h geq mountainHeight, it means the workers can reduce the mountain height to 0 in t seconds.

Next, we determine the left boundary of the binary search l = 1. Since there is at least one worker, and each worker's working time does not exceed 10^6, to reduce the mountain height to 0, it takes at least (1 + mountainHeight) cdot mountainHeight / 2 cdot workerTimes[i] leq 10^{16} seconds. Therefore, we can set the right boundary of the binary search to r = 10^{16}. Then, we continuously halve the interval [l, r] until l = r. At this point, l is the answer.

The time complexity is O(n times log M), where n is the number of workers, and M is the right boundary of the binary search, which is 10^{16} in this problem. The space complexity is O(1)$.

TypeScript

function minNumberOfSeconds(mountainHeight: number, workerTimes: number[]): number {
    const check = (t: bigint): boolean => {
        let h = BigInt(0);
        for (const wt of workerTimes) {
            h += BigInt(Math.floor(Math.sqrt((Number(t) * 2.0) / wt + 0.25) - 0.5));
        }
        return h >= BigInt(mountainHeight);
    };

    let l = BigInt(1);
    let r = BigInt(1e16);

    while (l < r) {
        const mid = (l + r) >> BigInt(1);
        if (check(mid)) {
            r = mid;
        } else {
            l = mid + 1n;
        }
    }

    return Number(l);
}

public class Solution {
    public long MinNumberOfSeconds(int mountainHeight, int[] workerTimes) {
        long l = 1, r = (long)1e16;

        bool Check(long t) {
            long h = 0;
            foreach (int wt in workerTimes) {
                long val = (long)(Math.Sqrt(t * 2.0 / wt + 0.25) - 0.5);
                h += val;
                if (h >= mountainHeight) {
                    return true;
                }
            }
            return h >= mountainHeight;
        }

        while (l < r) {
            long mid = (l + r) >> 1;
            if (Check(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }

        return l;
    }
}

func minNumberOfSeconds(mountainHeight int, workerTimes []int) int64 {
	return int64(sort.Search(1e16, func(t int) bool {
		var h int64
		for _, wt := range workerTimes {
			h += int64(math.Sqrt(float64(t)*2.0/float64(wt)+0.25) - 0.5)
		}
		return h >= int64(mountainHeight)
	}))
}

Rust

impl Solution {
    pub fn min_number_of_seconds(mountain_height: i32, worker_times: Vec<i32>) -> i64 {
        let mut l: i64 = 1;
        let mut r: i64 = 10_i64.pow(16);

        let check = |t: i64| -> bool {
            let mut h: i64 = 0;
            for &wt in &worker_times {
                let wt = wt as f64;
                let t_f = t as f64;
                let val = ((t_f * 2.0 / wt + 0.25).sqrt() - 0.5).floor() as i64;
                h += val;
                if h >= mountain_height as i64 {
                    return true;
                }
            }
            h >= mountain_height as i64
        };

        while l < r {
            let mid = (l + r) >> 1;
            if check(mid) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }

        l
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Binary Search on Max Time	Time Complexity: O(n * log(m * h)) where n is the number of workers, m is the maximum worker time, and h is the mountain height. Space Complexity: O(1), as it uses a constant amount of space.
Dynamic Programming	Time Complexity: O(n * h^2), where n is the number of workers, and h is the mountain height. This is not optimal for high mountain heights. Space Complexity: O(h), where h is the mountain height.
Binary Search	–

Approach

Complexity

Binary Search on Max Time

Time Complexity: O(n * log(m * h)) where n is the number of workers, m is the maximum worker time, and h is the mountain height.

Space Complexity: O(1), as it uses a constant amount of space.

Dynamic Programming

Time Complexity: O(n * h^2), where n is the number of workers, and h is the mountain height. This is not optimal for high mountain heights.

Space Complexity: O(h), where h is the mountain height.

Binary Search

–

Complexity analysis

Approach	Time	Space	When to Use
Greedy Simulation with Heap	O(H log n)	O(n)	When height is small and you want a direct timeline simulation
Binary Search on Time	O(n log T)	O(1)	Optimal solution for large constraints with monotonic feasibility
Dynamic Programming	O(n * H)	O(H)	Useful for conceptual understanding of cost distribution

Frequently asked questions

Is Minimum Number of Seconds to Make Mountain Height Zero easy or hard?

This problem is generally considered medium difficulty. The main challenge is recognizing that worker costs form a triangular sequence and that the answer can be found using binary search on time instead of simulating every unit removal.

Minimum Number of Seconds to Make Mountain Height Zero Python/Java solution

Python and Java implementations typically follow the binary search approach. The algorithm repeatedly checks if a given time allows workers to remove enough units by solving the triangular inequality per worker. This keeps the complexity O(n log T) and avoids explicit simulation.

How to solve Minimum Number of Seconds to Make Mountain Height Zero in O(n log T)?

Use binary search over the answer (time). For a candidate time T, compute how many units each worker can remove by solving t * (k * (k + 1) / 2) ≤ T. Add the contributions from all workers and check if the total is at least the mountain height. Adjust the search range until the minimum valid time is found.

What is the best approach for Minimum Number of Seconds to Make Mountain Height Zero?

Binary search on time is the most efficient approach. The idea is to guess a time T and check how many units each worker can remove within that time using the formula t * (k * (k + 1) / 2). Summing the units across workers determines if the mountain height can reach zero. This method runs in O(n log T) time and O(1) space.

Is Minimum Number of Seconds to Make Mountain Height Zero asked at Google/Amazon/Meta?

Problems combining binary search with mathematical feasibility checks frequently appear in interviews at companies like Google, Amazon, and Meta. Variants involving worker scheduling, monotonic constraints, and triangular cost patterns are common in system-style algorithm questions.

What data structure is used in Minimum Number of Seconds to Make Mountain Height Zero?

The optimal solution mainly relies on binary search and mathematical computation. A priority queue (min-heap) can also simulate the process greedily by always selecting the next worker who finishes earliest, though this approach is less efficient for large inputs.

What is the time complexity of Minimum Number of Seconds to Make Mountain Height Zero?

The optimal solution runs in O(n log T) time where n is the number of workers and T is the search range for time. Each binary search step evaluates how many units each worker can remove using a mathematical formula derived from triangular numbers. Space complexity remains O(1).

Minimum Number of Seconds to Make Mountain Height Zero solution and explanation

The problem

Approach overview

Approach 1: Binary Search on Max Time

Approach 2: Dynamic Programming

Approach 3: Binary Search

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Minimum Number of Seconds to Make Mountain Height Zero solution and explanation

The problem

Approach overview

Approach 1: Binary Search on Max Time

Approach 2: Dynamic Programming

Approach 3: Binary Search

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems