1065. Latest Clock From Digits
A retro station sign shows the time as HH:MM on a 24-hour clock, from 00:00 up to 23:59. In the workshop there is a drawer of loose number tiles, and digits[i] is the digit printed on tile i. To light the sign you must use exactly four different tiles, each tile at most once, laid out in the order H H M M so the result is a valid time.
Return the latest valid time you can display, formatted as "HH:MM", or the empty string if no valid time can be made. The drawer can be large, so trying every ordered choice of four tiles is far too slow; target O(n + 1440) time and O(1) extra space.
Example 1
- Input:
- digits = [1,3,3,7,2]
- Output:
- "23:37"
- Explanation:
Hour 23 is possible from tiles 2 and 3, and the remaining tiles 1, 3, 7 give the largest valid minutes 37.
Example 2
- Input:
- digits = [6,6,7,8]
- Output:
- ""
- Explanation:
Every tile is larger than 2, so no valid hour can be formed and the result is empty.
Example 3
- Input:
- digits = [0,0,0,0]
- Output:
- "00:00"
- Explanation:
The only valid arrangement is all zeros, giving midnight.
Constraints
4 ≤ digits.length ≤ 105
0 ≤ digits[i] ≤ 9
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)