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.
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; }}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.