You are given a string time in the form of hh:mm, where some of the digits in the string are hidden (represented by ?).
The valid times are those inclusively between 00:00 and 23:59.
Return the latest valid time you can get from time by replacing the hidden digits.
Example 1:
Input: time = "2?:?0" Output: "23:50" Explanation: The latest hour beginning with the digit '2' is 23 and the latest minute ending with the digit '0' is 50.
Example 2:
Input: time = "0?:3?" Output: "09:39"
Example 3:
Input: time = "1?:22" Output: "19:22"
Constraints:
time is in the format hh:mm.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.
This approach uses conditional checks to replace each '?' in the time string with the highest possible digit while maintaining valid time format constraints. We'll replace '?' in hours and minutes step-by-step, ensuring the output is valid. This direct manipulation approach ensures we get the latest possible time.
This C solution replaces each '?' with the maximum allowable digit for a valid time. We handle each component of the time format (hh:mm) pragmatically. First, by checking the hour's digits, we ensure they form a valid hour considering the placement constraints. If the first digit of the hour is '?' and the second digit (or '?' assumed as number below 4) is valid, we assign '2'. Otherwise, we assign '1'. For minutes, '5' and '9' are chosen since they can represent any valid minute.
Time Complexity: O(1), since the operations are fixed in number.
Space Complexity: O(1), as we alter the given string in place.
This approach divides the replacement operations into two distinct passes. First, it replaces the hours based on possible constraints, then finalizes the replacements for minutes, ensuring all components align with valid time rules.
The two-pass method in C uses initial conditional checks to determine possible replacements for hour digits before moving to adjusting minute digits, ensuring each part of the time string is optimally replaced for maximizing the time value.
Time Complexity: O(1)
Space Complexity: O(1)
We process each digit of the string in order, following these rules:
[4, 9], then the first digit can only be 1. Otherwise, the first digit can be up to 2.2, then the second digit can be up to 3. Otherwise, the second digit can be up to 9.5.9.The time complexity is O(1), and the space complexity is O(1).
Python
Java
C++
Go
JavaScript
| Approach | Complexity |
|---|---|
| Use Conditional Replacement | Time Complexity: O(1), since the operations are fixed in number. |
| Two-Pass Approach with Conditions | Time Complexity: O(1) |
| Greedy | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Conditional Greedy Replacement | O(1) | O(1) | Best general solution. Directly computes the maximum valid time using digit constraints. |
| Two-Pass Approach with Conditions | O(1) | O(1) | Useful when you want clearer separation between hour and minute logic for readability. |
Leetcode Weekly Contest 225 | PROBLEM 1736 , 1737 | BITS PILANI • code Explainer • 1,018 views views
Watch 1 more video solutions →Practice Latest Time by Replacing Hidden Digits with our built-in code editor and test cases.
Practice on FleetCode