Minimum Number of Operations to Convert Time - Solution & Explanation

Problem Overview: You are given two time strings current and correct in HH:MM format. In one operation you can add 1, 5, 15, or 60 minutes to the current time. The goal is to reach the correct time using the minimum number of operations.

Approach 1: Greedy with Minutes Conversion (Time: O(1), Space: O(1))

Convert both times into total minutes from midnight. Compute the difference diff = correctMinutes - currentMinutes. The allowed operations are fixed increments: 60, 15, 5, and 1. Apply a greedy strategy by repeatedly taking the largest possible increment that does not exceed the remaining difference. For example, use as many 60-minute operations as possible, then 15, then 5, and finally 1. Because these increments form a canonical system, the greedy choice always produces the minimum number of operations. The computation involves a few integer divisions and remainders, so runtime is constant.

The key insight: minimizing operations is equivalent to minimizing the number of increments used to build the minute difference. With fixed step sizes, greedy selection works the same way as making change with standard coin denominations. You simply reduce the remaining minutes with the largest step first.

Relevant concepts appear frequently in greedy algorithms and basic string parsing problems.

Approach 2: Dynamic Programming (Time: O(D * 4), Space: O(D))

Dynamic programming treats the problem like a small coin change variant. Let D be the minute difference. Build a DP array where dp[i] represents the minimum operations needed to reach exactly i minutes. For each minute value, check transitions using the allowed operations {1, 5, 15, 60}. The recurrence is dp[i] = 1 + min(dp[i - step]) for valid steps.

This guarantees an optimal answer for every intermediate value and works even if the operation set changes. However, it requires iterating through all minute values up to D, so it is slower and uses extra memory. For this problem the difference is at most 1439 minutes, so it still runs fast in practice. This approach connects to classic dynamic programming patterns used in coin change problems.

Recommended for interviews: The greedy minutes-conversion approach is what interviewers expect. It shows you recognized the fixed increments and reduced the problem to a simple arithmetic strategy. The DP method demonstrates problem generalization, but greedy is the clean, optimal solution with constant time and space.