The original article is available at https://dawnmagnet.top/leetcode/2022/01/18/.

Given a list of times in 24-hour format ("HH:MM"), find the minimum difference between any two times in the list, expressed in minutes.

Example 1:

**Input:** timePoints = ["23:59","00:00"]
**Output:** 1

Example 2:

**Input:** timePoints = ["00:00","23:59","00:00"]
**Output:** 0

Constraints:

• 2 <= timePoints <= 2 * 104
• timePoints[i] has the format "HH:MM".

Source: LeetCode Link: https://leetcode-cn.com/problems/minimum-time-difference Copyright belongs to LeetCode. For commercial use, contact the official copyright holder; for non-commercial use, cite the source as required.

Analysis

#

First, convert each time into its corresponding number of minutes. Mark that minute in a Boolean array of length 1440 (24*60), then enumerate the occupied positions. Sorting the times would also work, but the domain is so small (only 1440 minutes) that sorting is unnecessary.

After placing the times in the array, there are two kinds of gaps to consider: the gap between two consecutive occupied positions, and the wraparound gap between the first and last occupied positions. The latter needs special attention when computing the answer.

Rust Code

#

pub fn parse(s: &str) -> usize {
    let mut res = 0;
    let b: Vec<usize> = s.as_bytes().iter().map(|&x| x as usize - 48).collect();
    (b[0] * 10 + b[1]) * 60 + b[3] * 10 + b[4]
}
impl Solution {
    pub fn find_min_difference(time_points: Vec<String>) -> i32 {
        let mut c = [false; 1440];
        for item in &time_points {
            let pos = parse(item);
            if c[pos] {
                return 0;
            } else {
                c[parse(item)] = true;
            }
        }
        let mut cur = usize::MAX;
        let mut res = 10000;
        let mut first = 0;
        for time in 0..1440 {
            if c[time] {
                if cur == usize::MAX {
                    cur = time;
                    first = time + 1440;
                } else {
                    res = res.min(time - cur);
                    cur = time;
                }
            }
        }
        res = res.min(first - cur);
        res as i32
    }
}