Next Closest Time

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.

Example 1:

Input: "19:34"
Output: "19:39"
Explanation: The next closest time choosing from digits 1, 9, 3, 4, is 19:39, which occurs 5 minutes later.  

Remember there is no limit on how many times a digit can be reused. so from  1, 9, 3, the digit 9 is used twice to form 19:39, and 4 is never being used to get the output.

Example 2:

Input: "23:59"
Output: "22:22"
Explanation: The next closest time choosing from digits 2, 3, 5, 9, is 22:22. It may be assumed that the returned time is the next day's time since it is smaller than the input time numerically.

Intuition and Algorithm

  • Convert the time in minutes of the day. Get the hours and minutes from the input time. Then calculate currentTimeInMinutes = (60 * hours) + minutes.
  • Now simulate the clock going forward by one minute. Each time it moves forward, if all the digits are allowed, then return the current time. 
  • The natural way to represent the time is as an integer t in the range 0 <= t < 24 * 60. Then the hours are t / 60, the minutes are t % 60, and each digit of the hours and minutes can be found by hours / 10, hours % 10 etc.
class NextClosestTimeSolution {

    public String nextClosestTime(String time) {
        int hours = Integer.parseInt(time.substring(0, 2));
        int minutes = Integer.parseInt(time.substring(3));
        int currentTimeInMinutes = 60 * hours + minutes;
        Set<Integer> allowed = new HashSet<>();
        for (char c : time.toCharArray()) {
            if (c != ':') {
                allowed.add(c - '0');
            }
        }

        while (true) {
            currentTimeInMinutes = (currentTimeInMinutes + 1) % (24 * 60);
            int[] digits = new int[]{
                    currentTimeInMinutes / 60 / 10,
                    currentTimeInMinutes / 60 % 10,
                    currentTimeInMinutes % 60 / 10,
                    currentTimeInMinutes % 60 % 10
            };

            if (isValid(allowed, digits)) {
                StringBuffer buffer = new StringBuffer();
                buffer.append(digits[0]).append(digits[1]);
                buffer.append(":");
                buffer.append(digits[2]).append(digits[3]);
                return buffer.toString();
            }
        }
    }

    private boolean isValid(Set<Integer> allowed, int[] digits) {
        for (int d : digits) {
            if (!allowed.contains(d)) {
                return false;
            }
        }
        return true;
    }
}

public class NextClosestTime {
    public static void main(String[] args) {
        String time = "23:59";
        NextClosestTimeSolution nextClosestTimeSolution = new NextClosestTimeSolution();
        System.out.println(nextClosestTimeSolution.nextClosestTime(time));
    }
}

Complexity Analysis

  • Time Complexity: O(1). We try up to 24 * 60 possible times until we find the correct time.
  • Space Complexity: O(1).

Categories: String

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s