Latest Time by Replacing Hidden Digits - Video Solutions

Problem Overview: You get a 5‑character time string in the format HH:MM. Some digits are hidden using '?'. Replace every '?' so the final string represents the latest possible valid 24‑hour time.

Approach 1: Use Conditional Replacement (O(1) time, O(1) space)

The time string has a fixed length, so you can directly decide each missing digit using greedy rules. Focus on maximizing the hour first, then the minute. For the first hour digit (H1), choose '2' if the second digit is '?' or ≤ '3'; otherwise use '1'. For the second hour digit (H2), if H1 is '2', the maximum allowed value is '3'; otherwise it can be '9'. Minutes follow simpler constraints: the first minute digit (M1) can be at most '5', and the last digit (M2) can be '9'. Iterate through the characters, apply these rules, and replace each '?' with the highest valid digit. This greedy strategy works because choosing the largest valid digit at each position always leads to the lexicographically largest valid time. The algorithm runs in constant time since the string length never changes. This problem is a straightforward application of greedy reasoning with basic constraints on a string.

Approach 2: Two-Pass Approach with Conditions (O(1) time, O(1) space)

Another clean approach processes the string in two passes: first resolve the hour component, then resolve the minutes. In the first pass, evaluate both hour digits together because their valid range (00–23) creates a dependency. If both are '?', replace them with "23". If only the first digit is missing, choose '2' when the second digit is ≤ '3'; otherwise choose '1'. If only the second digit is missing, check the first digit and assign '3' when it is '2', otherwise '9'. In the second pass, handle the minute portion independently: replace the first minute digit with '5' if missing, and the last with '9'. Separating the logic this way improves readability and mirrors the natural constraint boundaries between hours and minutes. Like the greedy version, this method operates on a constant-sized input, so both time and space complexity remain O(1).

Recommended for interviews: The conditional greedy replacement is what most interviewers expect. It shows you understand the constraints of the 24‑hour clock and can derive the maximum valid digit for each position. The two‑pass variant is equally correct and often easier to reason about during implementation, especially when explaining your logic out loud.