Minimum Cost to Set Cooking Time - Solution & Explanation

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.