Minimum Cost to Set Cooking Time - Video Solutions
2162. Minimum Cost to Set Cooking Time || LeetCode 2162 || Biweekly LeetCode 71
Minimum Cost to Set Cooking Time - Video Solution
Watch 6 video solutions for Minimum Cost to Set Cooking Time, a medium level problem involving Math, Enumeration. This walkthrough by Bro Coders has 1,828 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
A generic microwave supports cooking times for:
- at least
1second. - at most
99minutes and99seconds.
To set the cooking time, you push at most four digits. The microwave normalizes what you push as four digits by prepending zeroes. It interprets the first two digits as the minutes and the last two digits as the seconds. It then adds them up as the cooking time. For example,
- You push
954(three digits). It is normalized as0954and interpreted as9minutes and54seconds. - You push
0008(four digits). It is interpreted as0minutes and8seconds. - You push
8090. It is interpreted as80minutes and90seconds. - You push
8130. It is interpreted as81minutes and30seconds.
You are given integers startAt, moveCost, pushCost, and targetSeconds. Initially, your finger is on the digit startAt. Moving the finger above any specific digit costs moveCost units of fatigue. Pushing the digit below the finger once costs pushCost units of fatigue.
There can be multiple ways to set the microwave to cook for targetSeconds seconds but you are interested in the way with the minimum cost.
Return the minimum cost to set targetSeconds seconds of cooking time.
Remember that one minute consists of 60 seconds.
Example 1:
Input: startAt = 1, moveCost = 2, pushCost = 1, targetSeconds = 600 Output: 6 Explanation: The following are the possible ways to set the cooking time. - 1 0 0 0, interpreted as 10 minutes and 0 seconds. The finger is already on digit 1, pushes 1 (with cost 1), moves to 0 (with cost 2), pushes 0 (with cost 1), pushes 0 (with cost 1), and pushes 0 (with cost 1). The cost is: 1 + 2 + 1 + 1 + 1 = 6. This is the minimum cost. - 0 9 6 0, interpreted as 9 minutes and 60 seconds. That is also 600 seconds. The finger moves to 0 (with cost 2), pushes 0 (with cost 1), moves to 9 (with cost 2), pushes 9 (with cost 1), moves to 6 (with cost 2), pushes 6 (with cost 1), moves to 0 (with cost 2), and pushes 0 (with cost 1). The cost is: 2 + 1 + 2 + 1 + 2 + 1 + 2 + 1 = 12. - 9 6 0, normalized as 0960 and interpreted as 9 minutes and 60 seconds. The finger moves to 9 (with cost 2), pushes 9 (with cost 1), moves to 6 (with cost 2), pushes 6 (with cost 1), moves to 0 (with cost 2), and pushes 0 (with cost 1). The cost is: 2 + 1 + 2 + 1 + 2 + 1 = 9.
Example 2:
Input: startAt = 0, moveCost = 1, pushCost = 2, targetSeconds = 76 Output: 6 Explanation: The optimal way is to push two digits: 7 6, interpreted as 76 seconds. The finger moves to 7 (with cost 1), pushes 7 (with cost 2), moves to 6 (with cost 1), and pushes 6 (with cost 2). The total cost is: 1 + 2 + 1 + 2 = 6 Note other possible ways are 0076, 076, 0116, and 116, but none of them produces the minimum cost.
Constraints:
0 <= startAt <= 91 <= moveCost, pushCost <= 1051 <= targetSeconds <= 6039
Approach Overview
Problem Overview: You control a microwave where entering digits sets cooking time in MM:SS format, but digits are typed sequentially on a keypad. Moving the finger between digits costs moveCost and pressing a digit costs pushCost. Given a starting finger position and a target cooking time in seconds, the goal is to compute the minimum cost required to input the time.
The key constraint is that the microwave only accepts up to four digits. That means the time must be represented as a valid minutes and seconds combination where seconds < 60. Multiple representations can exist for the same total time, so you must evaluate all valid encodings and choose the cheapest keypad sequence.
Approach 1: Using Sorting (Enumeration of Valid Times) (Time: O(1), Space: O(1))
The core idea is to enumerate all valid (minutes, seconds) pairs that produce the target seconds. For each candidate, build the digit sequence that would be typed on the keypad. Remove leading zeros where appropriate because the microwave ignores unnecessary prefix digits. For every sequence, simulate typing: track the current finger position, add moveCost whenever the digit changes, and add pushCost for every press.
Sorting can be used to prioritize shorter digit sequences or lower-cost candidates first, though the candidate set is extremely small (at most two valid representations). Each candidate sequence is evaluated independently, and the minimum total cost is returned. Since the number of possible representations is constant, the overall complexity stays O(1). This approach mainly relies on arithmetic reasoning from Math and controlled Enumeration.
Approach 2: Using a Hash Map (Digit Cost Tracking) (Time: O(1), Space: O(1))
This variation focuses on reducing repeated keypad cost calculations. A hash map stores the cost of moving from one digit to another or the previously computed typing cost for certain transitions. As each candidate time representation is evaluated, digit transitions are checked using constant-time hash lookups rather than recomputing movement logic every time.
The algorithm still enumerates valid (minutes, seconds) pairs but optimizes the cost simulation. For each digit in the sequence, the hash map determines whether a movement cost applies and retrieves the stored transition cost instantly. This keeps the simulation simple and avoids repeated condition checks. The method relies on a lightweight hash table to streamline the keypad simulation while maintaining constant time complexity.
Recommended for interviews: The enumeration approach is what interviewers typically expect. It shows that you recognize multiple valid time representations and can simulate the keypad precisely. The hash map variation is a small optimization and demonstrates awareness of reducing repeated operations, but the main signal of skill is correctly enumerating candidates and computing the typing cost.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Enumeration with Sorting | O(1) | O(1) | General solution. Enumerates all valid minute-second combinations and simulates keypad typing. |
| Hash Map Cost Tracking | O(1) | O(1) | Useful when optimizing repeated digit transition cost calculations during simulation. |