We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Next Closest Time

Number: 681

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

Given a time in "HH:MM" format, find the next closest time using only the digits present in the given time. The next closest time can be interpreted as the smallest time greater than the given time using only those digits and wrapping around to the next day if necessary.

Key Insights

  • Only the digits present in the input can be used to form the new time.
  • We can generate all 4-digit combinations using the provided digits.
  • Validate each combination to ensure the hours are less than 24 and minutes are less than 60.
  • Calculate the time difference (handle the wrap-around by taking modulo 24*60).
  • Choose the valid time with the smallest positive time difference.

Space and Time Complexity

Time Complexity: O(1) - The total number of combinations is at most 4^4 (256), which is constant. Space Complexity: O(1) - Only constant extra space is used.

Solution

The approach is to extract the unique digits from the given time and generate all possible 4-digit combinations to form candidate times. For each candidate, check if it forms a valid time (0<=hour<24 and 0<=minute<60). Convert the candidate time to minutes and calculate the time difference from the original time with proper modulo arithmetic to account for wrap-around at midnight. Track the candidate with the smallest positive time difference and return it in "HH:MM" format. The algorithm uses enumeration (via backtracking or nested loops) and simple arithmetic on time values.

Code Solutions

# Python solution for Next Closest Time

def nextClosestTime(time: str) -> str:
    # Extract digits from input time (ignoring the colon)
    allowed = {char for char in time if char != ':'}
    
    # Convert current time to minutes
    current_minutes = int(time[:2]) * 60 + int(time[3:])
    
    result = None
    min_delta = 24 * 60  # maximum possible difference in minutes (24 hours)
    
    # Generate all possible 4-digit times from allowed digits
    for h1 in allowed:
        for h2 in allowed:
            hour = int(h1 + h2)
            if hour >= 24:
                continue  # invalid hour
            for m1 in allowed:
                for m2 in allowed:
                    minute = int(m1 + m2)
                    if minute >= 60:
                        continue  # invalid minute
                    candidate_minutes = hour * 60 + minute
                    # Calculate time difference accounting for wrap-around
                    delta = (candidate_minutes - current_minutes) % (24 * 60)
                    if delta == 0:
                        continue  # Skip the current time itself
                    if delta < min_delta:
                        min_delta = delta
                        result = f"{hour:02d}:{minute:02d}"
    # If no valid candidate is found (all are same as current), return the current time
    return result if result is not None else time

# Example usage:
print(nextClosestTime("19:34"))
print(nextClosestTime("23:59"))
← Back to All Questions