Next Closest Time - Leetcode Solution

Problem:

Given a time represented in the format "HH:MM", form the next closest time by reusing the current digits. There is no limit on how many times a digit can be reused.

You may assume the given input string is always valid. For example, "01:34", "12:09" are all valid. "1:34", "12:9" are all invalid.

Solution:

Our approach to solving this problem is to convert the input string to an array of integers representing hours and minutes. We then increment the time (in minutes) by 1 until we find a valid time that reuses the current digits.

Step 1: Convert input string to an array of integers

We split the input string at the colon to get the hours and minutes as separate strings. We then convert these strings to integers using the parseInt() function and store them in an array.

// Split input string at colon and convert strings to integers const [hours, minutes] = time.split(":").map(str => parseInt(str));

Step 2: Increment time by 1 minute until valid time is found

We start by incrementing the minutes by 1 and checking if the new time is valid. If the minutes increment past 59, we reset them to 0 and increment the hours by 1. If the hours increment past 23, we reset them to 0.

We continue this process until we find a valid time. To check if a time is valid, we convert the hours and minutes back to a string and pad them with leading zeros if necessary. We then compare these strings to the original input string to make sure they reuse the current digits.

let newMinutes = minutes + 1; // Increment minutes by 1

while (true) { // Reset minutes to 0 and increment hours if necessary if (newMinutes > 59) { newMinutes = 0; hours += 1; }

// Reset hours to 0 if necessary if (hours > 23) { hours = 0; }

// Check if new time reuses current digits const newTime = ${hours.toString().padStart(2, "0")}:${newMinutes.toString().padStart(2, "0")}; if (newTime.split("").every(digit => time.includes(digit))) { return newTime; }

// Increment minutes by 1 and try again newMinutes += 1; }

Step 3: Return the next closest valid time

If we successfully find a valid time, we return it from the while loop.

Full Solution:

function nextClosestTime(time) { // Split input string at colon and convert strings to integers const [hours, minutes] = time.split(":").map(str => parseInt(str));

let newMinutes = minutes + 1; // Increment minutes by 1

while (true) { // Reset minutes to 0 and increment hours if necessary if (newMinutes > 59) { newMinutes = 0; hours += 1; }

// Reset hours to 0 if necessary
if (hours > 23) {
  hours = 0;
}

// Check if new time reuses current digits
const newTime = `${hours.toString().padStart(2, "0")}:${newMinutes.toString().padStart(2, "0")}`;
if (newTime.split("").every(digit => time.includes(digit))) {
  return newTime;
}

// Increment minutes by 1 and try again
newMinutes += 1;

} }

Time Complexity: O(1)

Since we are only checking a finite number of possible times (1440), the time complexity of our solution is O(1).

Space Complexity: O(1)

Our solution has a constant space complexity since we are only storing a fixed number of variables (hours, minutes, newMinutes).

1