Minimum Number of Operations to Convert Time
EasyPrompt
You are given two strings current and correct representing two 24-hour times.
24-hour times are formatted as "HH:MM", where HH is between 00 and 23, and MM is between 00 and 59. The earliest 24-hour time is 00:00, and the latest is 23:59.
In one operation you can increase the time current by 1, 5, 15, or 60 minutes. You can perform this operation any number of times.
Return the minimum number of operations needed to convert current to correct.
Example 1:
Input: current = "02:30", correct = "04:35"
Output: 3
Explanation:
We can convert current to correct in 3 operations as follows:
- Add 60 minutes to current. current becomes "03:30".
- Add 60 minutes to current. current becomes "04:30".
- Add 5 minutes to current. current becomes "04:35".
It can be proven that it is not possible to convert current to correct in fewer than 3 operations.Example 2:
Input: current = "11:00", correct = "11:01"
Output: 1
Explanation: We only have to add one minute to current, so the minimum number of operations needed is 1.
Constraints:
currentandcorrectare in the format"HH:MM"current <= correct
Approaches
2 approaches with complexity analysis and trade-offs.
This approach treats the problem as a variation of the classic "Coin Change" problem. We want to find the minimum number of "coins" (operations of 1, 5, 15, 60 minutes) that sum up to the total difference in minutes between the correct and current time. Dynamic programming provides a systematic way to solve this by building up the solution for all differences from 1 up to the target difference.
Algorithm
- Parse the
currentandcorrecttime strings to get the total minutes from midnight for each, let's call themstartMinutesandendMinutes. - Calculate the total difference in minutes:
diff = endMinutes - startMinutes. - If
diffis 0, no operations are needed, so return 0. - Create a dynamic programming array,
dp, of sizediff + 1.dp[i]will store the minimum number of operations to achieve a time difference ofiminutes. - Initialize
dp[0] = 0and all other elements ofdpto a very large value (representing infinity). - Define the set of possible operations:
ops = {1, 5, 15, 60}. - Iterate from
i = 1todiff:- For each
i, iterate through each operationopinops. - If
iis greater than or equal toop, it's possible to use this operation. Updatedp[i]with the minimum of its current value and1 + dp[i - op].
- For each
- The final answer is the value stored in
dp[diff].
Walkthrough
First, we convert the input time strings (current and correct) from the "HH:MM" format into a single integer representing the total number of minutes from midnight (00:00). Then, we calculate the total difference in minutes, diff = correct_minutes - current_minutes. We create a dynamic programming array, dp, of size diff + 1, where dp[i] will store the minimum number of operations required to achieve a time difference of i minutes. We initialize dp[0] = 0 (0 minutes difference requires 0 operations) and all other dp[i] to a large value. We then iterate from i = 1 to diff. For each i, we calculate dp[i] by considering all possible last operations (1, 5, 15, or 60 minutes). The recurrence relation is dp[i] = 1 + min(dp[i-op]) for each op in {1, 5, 15, 60}, provided i >= op. The final answer is dp[diff].
class Solution { public int convertTime(String current, String correct) { // 1. Convert times to minutes int currentMinutes = Integer.parseInt(current.substring(0, 2)) * 60 + Integer.parseInt(current.substring(3, 5)); int correctMinutes = Integer.parseInt(correct.substring(0, 2)) * 60 + Integer.parseInt(correct.substring(3, 5)); int diff = correctMinutes - currentMinutes; if (diff == 0) { return 0; } // 2. DP setup int[] dp = new int[diff + 1]; java.util.Arrays.fill(dp, Integer.MAX_VALUE); dp[0] = 0; int[] operations = {1, 5, 15, 60}; // 3. Fill DP table for (int i = 1; i <= diff; i++) { for (int op : operations) { if (i >= op && dp[i - op] != Integer.MAX_VALUE) { dp[i] = Math.min(dp[i], 1 + dp[i - op]); } } } // 4. Return result return dp[diff]; }}Complexity
Time
O(D), where D is the total difference in minutes. The outer loop runs D times, and the inner loop is constant (4 iterations), making the complexity linear with respect to the minute difference.
Space
O(D), where D is the total difference in minutes. The maximum possible difference is from "00:00" to "23:59", which is 1439 minutes. This space is required for the DP table.
Trade-offs
Pros
Guaranteed to find the optimal solution for any set of operations (coins).
It's a general and robust method for this type of minimization problem.
Cons
Requires O(D) extra space for the DP array, where D is the minute difference.
Slower than the greedy approach for this specific problem.
It's a more complex solution than necessary given that a greedy approach is optimal.
This problem has a special property that allows for a greedy solution. The set of available operations {60, 15, 5, 1} forms a system where always choosing the largest possible operation to reduce the remaining time difference leads to the minimum total number of operations. This is because each operation value is a multiple of the smaller ones (or can be optimally constructed from them), preventing a situation where using smaller operations would be better. This approach is much more efficient than dynamic programming.
Algorithm
- Parse the
currentandcorrecttime strings to get the total minutes from midnight for each, let's call themstartMinutesandendMinutes. - Calculate the total difference in minutes that needs to be covered:
diff = endMinutes - startMinutes. - Initialize a counter for the number of operations,
operationsCount, to zero. - To minimize the number of operations, greedily use the largest possible increments first. Process the operations in descending order: 60, 15, 5, and 1.
- For the 60-minute operation: add
diff / 60tooperationsCountand updatediffto the remainder,diff %= 60. - For the 15-minute operation: add
diff / 15tooperationsCountand updatedifftodiff %= 15. - For the 5-minute operation: add
diff / 5tooperationsCountand updatedifftodiff %= 5. - For the 1-minute operation: the remaining
diffmust be covered by 1-minute operations. AdddifftooperationsCount. - Return the final
operationsCount.
Walkthrough
The most efficient way to solve this problem is with a greedy algorithm. First, we parse the time strings "HH:MM" into total minutes from midnight. We calculate the difference in minutes, diff, between the correct and current times. The core idea is to satisfy this difference using the fewest operations possible. To do this, we should always use the largest available time increment that is less than or equal to the remaining difference. We start with the 60-minute operation, calculating how many times we can apply it (diff / 60). We add this count to our total operations and update the difference to the remainder (diff % 60). We then repeat this process for the 15-minute, 5-minute, and finally 1-minute operations. This greedy choice is optimal for this specific set of operations.
class Solution { public int convertTime(String current, String correct) { // 1. Convert times to minutes int currentMinutes = Integer.parseInt(current.substring(0, 2)) * 60 + Integer.parseInt(current.substring(3, 5)); int correctMinutes = Integer.parseInt(correct.substring(0, 2)) * 60 + Integer.parseInt(correct.substring(3, 5)); int diff = correctMinutes - currentMinutes; int operationsCount = 0; // 2. Greedily apply operations from largest to smallest operationsCount += diff / 60; diff %= 60; operationsCount += diff / 15; diff %= 15; operationsCount += diff / 5; diff %= 5; operationsCount += diff; // Remaining diff is handled by 1-minute operations return operationsCount; }}Complexity
Time
O(1). The time taken to parse the strings and perform the few arithmetic operations is constant and does not depend on the magnitude of the input times.
Space
O(1). We only use a few variables to store the minutes, difference, and operation count, requiring constant extra space.
Trade-offs
Pros
Extremely fast and efficient.
Simple to understand and implement.
Requires minimal memory (constant space).
Cons
The greedy strategy is not universally applicable to all "coin change" type problems. It works here due to the specific properties of the operation values, but one must be careful to prove its correctness before applying it.
Solutions
Solution
class Solution {public int convertTime(String current, String correct) { int a = Integer.parseInt(current.substring(0, 2)) * 60 + Integer.parseInt(current.substring(3)); int b = Integer.parseInt(correct.substring(0, 2)) * 60 + Integer.parseInt(correct.substring(3)); int ans = 0, d = b - a; for (int i : Arrays.asList(60, 15, 5, 1)) { ans += d / i; d %= i; } return ans; }}class Solution: def convertTime(self, current: str, correct: str) -> int: a = int(current[: 2]) * 60 + int(current[3:]) b = int(correct[: 2]) * 60 + int(correct[3:]) ans, d = 0, b - a for i in [60, 15, 5, 1]: ans += d // i d %= i return ansclass Solution {public: int convertTime(string current, string correct) { int a = stoi(current.substr(0, 2)) * 60 + stoi(current.substr(3, 2)); int b = stoi(correct.substr(0, 2)) * 60 + stoi(correct.substr(3, 2)); int ans = 0, d = b - a; vector<int> inc = {60, 15, 5, 1}; for (int i : inc) { ans += d / i; d %= i; } return ans; }};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.