539. Minimum Time Difference
https://leetcode.com/problems/minimum-time-difference/
Given a list of 24-hour clock time points in "Hour:Minutes" format, find the minimum minutes difference between any two time points in the list.
---
Example 1:
Input: ["23:59","00:00"] Output: 1
Note:
- The number of time points in the given list is at least 2 and won't exceed 20000.
- The input time is legal and ranges from 00:00 to 23:59.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public int findMinDifference(List<String> timePoints) { | |
| // bucket sort for linear runtime | |
| boolean[] buckets = new boolean[24 * 60]; | |
| for (String time: timePoints) { | |
| int minute = Integer.parseInt(time.substring(0, 2), 10) * 60 + Integer.parseInt(time.substring(3), 10); | |
| if (buckets[minute]) { | |
| return 0; | |
| } | |
| buckets[minute] = true; | |
| } | |
| int ans = Integer.MAX_VALUE, first = -1, current = -1, prev = -1; | |
| for (int i = 0; i < buckets.length; i++) { | |
| if (buckets[i]) { | |
| if (first == -1) { | |
| first = i; | |
| } else { | |
| current = i; | |
| ans = Math.min(ans, current - prev); | |
| } | |
| prev = i; | |
| } | |
| } | |
| // Check for wrap around, consider distance between first, and last | |
| return Math.min(ans, buckets.length - current + first); | |
| } | |
| } |
