Next Closest Time: Simulation & Modulo Math

[!NOTE] This module explores the core principles of Next Closest Time: Simulation & Modulo Math, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. Problem Definition

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.

Example 1:

Input: time = "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.

Example 2:

Input: time = "23:59"
Output: "22:22"
Explanation: The next closest time choosing from digits 2, 3, 5, 9, is 22:22 (Next Day).

---

2. Interactive Analysis

Click “Find Next” to generate valid permutations and pinpoint the closest future time.

Input Time (HH:MM):

Allowed Digits

-

Valid Combos

0 / 256

Start

Next

--:--

→

--:--

---

3. Intuition: Bounded Brute Force

Because there are exactly 4 slots (HH:MM), and each slot can hold one of up to 4 unique numbers, the maximum number of possible combinations you can dial is 4^4 = 256.

The search space is tiny. We apply “Bounded Brute Force”:

1. Generate all 256 possible times.
2. Filter out invalid times (like “25:99”).
3. Calculate the minutes elapsed since the starting time.
4. Keep the one with the smallest positive elapsed time.

Mathematical Anchor: Modular Arithmetic

To handle the “Tomorrow” wrap-around without excessive branching:

int delta = (curr - start + 24 * 60) % (24 * 60);

If curr is smaller than start (next day), curr - start is negative. Adding 1440 (24*60) ensures the result is positive, effectively simulating the clock cycle.

---

4. Solutions

Java

Go

class Solution {
  public String nextClosestTime(String time) {
    int start = 60 * Integer.parseInt(time.substring(0, 2)) + Integer.parseInt(time.substring(3));
    int ans = start;
    int diff = 24 * 60;

    Set<Integer> digits = new HashSet<>();
    for (char c : time.toCharArray()) {
      if (c != ':') {
        digits.add(c - '0');
      }
    }

    // Bounded O(1) Search Space (Max 256 iterations)
    for (int h1 : digits) {
      for (int h2 : digits) {
        int hour = h1 * 10 + h2;
        if (hour < 24) {
          for (int m1 : digits) {
            for (int m2 : digits) {
              int min = m1 * 10 + m2;
              if (min < 60) {
                int curr = hour * 60 + min;

                // Modular arithmetic directly handles midnight wrapping
                int delta = (curr - start + 24 * 60) % (24 * 60);
                if (delta == 0) delta = 24 * 60; // Same time maps to 24 hours later

                if (delta < diff) {
                  ans = curr;
                  diff = delta;
                }
              }
            }
          }
        }
      }
    }

    return String.format("%02d:%02d", ans / 60, ans % 60);
  }
}

package main

import "fmt"

func nextClosestTime(time string) string {
	start := 60*(int(time[0]-'0')*10+int(time[1]-'0')) + (int(time[3]-'0')*10 + int(time[4]-'0'))
	ans := start
	diff := 24 * 60

	digits := make(map[int]bool)
	for i := 0; i < len(time); i++ {
		if time[i] != ':' {
			digits[int(time[i]-'0')] = true
		}
	}

	for h1 := range digits {
		for h2 := range digits {
			hour := h1*10 + h2
			if hour < 24 {
				for m1 := range digits {
					for m2 := range digits {
						min := m1*10 + m2
						if min < 60 {
							curr := hour*60 + min

							// Time wrapping math
							delta := (curr - start + 24*60) % (24 * 60)
							if delta == 0 {
								delta = 24 * 60
							}

							if delta < diff {
								ans = curr
								diff = delta
							}
						}
					}
				}
			}
		}
	}

	return fmt.Sprintf("%02d:%02d", ans/60, ans%60)
}

---

5. Complexity Analysis

Strategy	Time	Space	Notes
Bounded Brute Force	O(1)	O(1)	Max 4^4 = 256 iterations. Fits in L1 Cache.