Skip to content

539. Minimum Time Difference 👍

  • Time: $O(n)$
  • Space: $O(24 \cdot 60)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
 public:
  int findMinDifference(vector<string>& timePoints) {
    int ans = 24 * 60;
    int first = 24 * 60;
    vector<bool> bucket(24 * 60);

    for (const string& time : timePoints) {
      const int num = stoi(time.substr(0, 2)) * 60 + stoi(time.substr(3));
      first = min(first, num);
      if (bucket[num])
        return 0;
      bucket[num] = true;
    }

    int prev = first;

    for (int i = first + 1; i < bucket.size(); ++i)
      if (bucket[i]) {
        ans = min(ans, i - prev);
        prev = i;
      }

    return min(ans, 24 * 60 - prev + first);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
  public int findMinDifference(List<String> timePoints) {
    int ans = 24 * 60;
    int first = 24 * 60;
    boolean[] bucket = new boolean[24 * 60];

    for (final String timePoint : timePoints) {
      final int num =
          Integer.valueOf(timePoint.substring(0, 2)) * 60 + Integer.valueOf(timePoint.substring(3));
      first = Math.min(first, num);
      if (bucket[num])
        return 0;
      bucket[num] = true;
    }

    int prev = first;

    for (int i = first + 1; i < bucket.length; ++i)
      if (bucket[i]) {
        ans = Math.min(ans, i - prev);
        prev = i;
      }

    return Math.min(ans, 24 * 60 - prev + first);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
  def findMinDifference(self, timePoints: list[str]) -> int:
    ans = 24 * 60
    nums = sorted([int(timePoint[:2]) * 60 + int(timePoint[3:])
                   for timePoint in timePoints])

    for a, b in zip(nums, nums[1:]):
      ans = min(ans, b - a)

    return min(ans, 24 * 60 - nums[-1] + nums[0])