LeetCode 1870: Minimum Speed to Arrive on Time Solution
Master LeetCode problem 1870 (Minimum Speed to Arrive on Time), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
1870. Minimum Speed to Arrive on Time
Problem Explanation
Explanation
To solve this problem, we can use binary search to find the minimum positive integer speed required for all the trains to reach the office on time. We can perform a binary search on the possible speeds and check if it is possible to reach the office on time with that speed. If it is possible, we update our lower bound, else we update our upper bound.
We start with a lower bound of 1 and an upper bound of 10^7 (as given in the problem constraints). At each iteration of the binary search, we calculate the total time required to travel all distances at the current speed. If the total time is less than or equal to the given hour, we update our lower bound to the mid speed. Otherwise, we update our upper bound.
The binary search continues until the lower bound becomes greater than the upper bound, at which point we return the lower bound as the minimum speed required to arrive on time. If after the binary search the lower bound exceeds the upper bound, we return -1 as it is impossible to arrive on time.
Time Complexity
The time complexity of this approach is O(n * log(10^7)), where n is the number of trains, as we perform a binary search on the possible speeds.
Space Complexity
The space complexity of this approach is O(1) as we are not using any extra space other than a few variables.
Solution Code
class Solution {
public int minSpeedOnTime(int[] dist, double hour) {
int n = dist.length;
int left = 1, right = (int)1e7, res = -1;
while(left <= right) {
int mid = left + (right - left) / 2;
double totalHours = 0;
for(int i = 0; i < n - 1; i++) {
totalHours += Math.ceil((double)dist[i] / mid);
}
totalHours += (double)dist[n - 1] / mid;
if(totalHours <= hour) {
res = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return res;
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 1870 (Minimum Speed to Arrive on Time)?
This page provides optimized solutions for LeetCode problem 1870 (Minimum Speed to Arrive on Time) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 1870 (Minimum Speed to Arrive on Time)?
The time complexity for LeetCode 1870 (Minimum Speed to Arrive on Time) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 1870 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1870 in Java, C++, or Python.