LeetCode 2224 - Minimum Number of Operations to Convert Time

LeetCode Problem 2224

Difficulty: 🟢 Easy
Topics: String, Greedy

Solution

Problem Understanding

The problem asks us to calculate the minimum number of operations to convert one 24-hour time string, current, into another, correct. Both inputs are formatted as "HH:MM", where HH is hours from 00 to 23 and MM is minutes from 00 to 59. Each operation allows us to increase the current time by 1, 5, 15, or 60 minutes, and we can perform these operations as many times as needed. The goal is to find the minimum number of operations required.

The input constraints guarantee that current is less than or equal to correct, so we never have to handle negative time differences or wrap-around past midnight. The maximum possible difference in minutes is therefore 23*60 + 59 = 1439 minutes. Important edge cases include when current equals correct (requiring zero operations), when the difference is small (1-4 minutes), and when the difference is large (requiring multiple 60-minute increments).

Approaches

A brute-force approach would repeatedly try each operation in all possible sequences until reaching correct. While this would eventually produce the correct result, it is highly inefficient and unnecessary, especially because the number of sequences grows exponentially with the difference in time.

The key insight for an optimal solution is greedy selection of the largest possible operation at each step. By always applying the largest increment that does not overshoot the remaining difference, we minimize the number of operations. This works because all allowed operations are divisors or factors of each other, ensuring that breaking a larger difference into smaller steps always matches the allowed operations.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(4^n)	O(n)	Explore all sequences of operations recursively
Optimal	O(1)	O(1)	Greedy subtraction of largest operations works due to divisibility

Algorithm Walkthrough

1. Convert time strings to minutes: Transform both current and correct from "HH:MM" to integer minutes since midnight. This simplifies arithmetic for differences.
2. Calculate the difference: Subtract the total minutes of current from correct. This gives the total number of minutes we need to cover with operations.
3. Apply greedy operations: Define the operations array [60, 15, 5, 1]. For each operation:

• Divide the remaining difference by the operation to find how many times it can be applied.
• Increment the operation count by this quotient.
• Reduce the remaining difference using modulo with the operation.

4. Return the total operations: After processing all operations, the sum is the minimum number of steps to reach correct.

Why it works: At each step, we consume as much of the remaining difference as possible using the largest available increment. Because the operations are multiples of smaller ones, this greedy approach guarantees minimal steps.

Python Solution

class Solution:
    def convertTime(self, current: str, correct: str) -> int:
        def time_to_minutes(t: str) -> int:
            hours, minutes = map(int, t.split(':'))
            return hours * 60 + minutes
        
        current_minutes = time_to_minutes(current)
        correct_minutes = time_to_minutes(correct)
        diff = correct_minutes - current_minutes
        operations = 0
        for op in [60, 15, 5, 1]:
            operations += diff // op
            diff %= op
        return operations

This implementation first converts the times into minutes for easier calculation. Then it calculates the difference, iterates over the allowed increments in descending order, counts how many times each can be applied, and reduces the difference. Finally, it returns the total number of operations.

Go Solution

func convertTime(current string, correct string) int {
    timeToMinutes := func(t string) int {
        hours := (int(t[0]-'0')*10 + int(t[1]-'0'))
        minutes := (int(t[3]-'0')*10 + int(t[4]-'0'))
        return hours*60 + minutes
    }

    diff := timeToMinutes(correct) - timeToMinutes(current)
    operations := 0
    for _, op := range []int{60, 15, 5, 1} {
        operations += diff / op
        diff %= op
    }
    return operations
}

In Go, we handle string-to-integer conversion manually using ASCII arithmetic, which avoids importing extra libraries. Otherwise, the logic mirrors Python exactly. The slice of operations is iterated in descending order, applying the greedy strategy.

Worked Examples

Example 1: current = "02:30", correct = "04:35"

Step	diff	op=60	op=15	op=5	op=1	operations
Initial	125	2	0	1	0	3

Explanation: 125 minutes difference. Use 2x60 (120 min), then 1x5 (5 min). Total operations = 3.

Example 2: current = "11:00", correct = "11:01"

Step	diff	op=60	op=15	op=5	op=1	operations
Initial	1	0	0	0	1	1

Explanation: Only 1 minute difference, so 1 operation of 1 minute.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	The algorithm always processes 4 operations; independent of input size
Space	O(1)	Only a few integer variables are used; no extra data structures

The time complexity is constant because the operations array has a fixed size, and string-to-integer conversion is linear in the small, fixed-length input (length 5).

Test Cases

# Provided examples
assert Solution().convertTime("02:30", "04:35") == 3  # multiple large steps
assert Solution().convertTime("11:00", "11:01") == 1  # single minute step

# Boundary cases
assert Solution().convertTime("00:00", "00:00") == 0  # no operations needed
assert Solution().convertTime("23:59", "23:59") == 0  # no operations needed at the end of day

# Edge differences
assert Solution().convertTime("00:00", "01:00") == 1  # exactly one hour
assert Solution().convertTime("12:00", "12:59") == 5  # combination of 15+15+15+15+1

# Increment combinations
assert Solution().convertTime("01:20", "03:40") == 4  # 2*60 + 1*15 + 1*5

Test	Why
"02:30" -> "04:35"	Checks multiple operations with mixed increments
"11:00" -> "11:01"	Smallest non-zero increment
"00:00" -> "00:00"	Zero difference edge case
"23:59" -> "23:59"	Maximum time boundary, zero difference
"00:00" -> "01:00"	Exact hour increment, single operation
"12:00" -> "12:59"	Uses multiple smaller operations
"01:20" -> "03:40"	Combination of multiple operations

Edge Cases

One important edge case is when current equals correct. Here, the difference is zero, and the algorithm correctly returns zero operations without entering the loop. Another edge case occurs when the difference is less than the smallest operation increment, such as 1-4 minutes. The greedy algorithm handles this because the 1-minute operation ensures any small remainder is covered. A third edge case is when the difference is exactly a multiple of 60 minutes, which should only use the hour operation. The algorithm naturally handles this by dividing by 60 and having zero remainder. All these edge cases are correctly handled by the conversion to minutes and the descending greedy application of operations.