Sponsored
Convert the time into minutes from "00:00", sort, then find the smallest difference between any two adjacent times while also considering the difference across midnight.
Time Complexity: O(n log n) due to sorting where n is the number of time points. Space Complexity: O(n) since we store the times in minutes.
1import java.util.*;
2
3public class MinimumTimeDifference {
4 private static int timeToMinutes(String time) {
5 int hours = Integer.parseInt(time.substring(0, 2));
6 int minutes = Integer.parseInt(time.substring(3, 5));
7 return hours * 60 + minutes;
8 }
9
10 public static int findMinDifference(List<String> timePoints) {
11 List<Integer> minutes = new ArrayList<>();
12 for (String time : timePoints) {
13 minutes.add(timeToMinutes(time));
14 }
15
16 Collections.sort(minutes);
17
18 int minDiff = Integer.MAX_VALUE;
19 for (int i = 1; i < minutes.size(); ++i) {
20 minDiff = Math.min(minDiff, minutes.get(i) - minutes.get(i - 1));
21 }
22
23 int wrapAroundDiff = minutes.get(0) + 1440 - minutes.get(minutes.size() - 1);
24 minDiff = Math.min(minDiff, wrapAroundDiff);
25
26 return minDiff;
27 }
28
29 public static void main(String[] args) {
30 List<String> timePoints = Arrays.asList("23:59", "00:00");
31 System.out.println(findMinDifference(timePoints));
32 }
33}
In Java, we use a list to convert and store the time points in minutes. We sort the list and calculate the minimum difference, considering sorted differences and the difference around midnight.
Mark each minute of the day in a boolean array once any time point corresponds to it. Then traverse the array to find the smallest gap between marked minutes, considering wrap-around. This is efficient because it eliminates the need for sorting.
Time Complexity: O(n + M), where M is 1440, the number of minutes in a day, n is the length of list.
Space Complexity: O(M), M = 1440, fixed.
1
Here, a boolean array representing each minute of the day is used to track time points. The algorithm finds the smallest gap between the marked minutes, ensuring wrap-around difference is checked at the end.