# LeetCode 539: Minimum Time Difference

## Problem Restatement

We are given a list of time points in 24-hour `"HH:MM"` format.

We need to return the minimum difference in minutes between any two time points. The clock wraps around after midnight, so the difference between `"23:59"` and `"00:00"` is `1`, not `1439`.

The input contains at least two time points. Each time point is formatted as `"HH:MM"`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A list of strings `timePoints` |
| Output | The minimum difference in minutes |
| Format | `"HH:MM"` |
| Clock range | `00:00` through `23:59` |
| Wrap-around | Difference across midnight must be considered |

Function shape:

```python
def findMinDifference(timePoints: list[str]) -> int:
    ...
```

## Examples

Consider:

```python
timePoints = ["23:59", "00:00"]
```

The difference across midnight is:

```python
1
```

So the answer is:

```python
1
```

Another example:

```python
timePoints = ["00:00", "23:59", "00:00"]
```

The time `"00:00"` appears twice.

Two identical time points have difference:

```python
0
```

So the answer is:

```python
0
```

## First Thought: Compare Every Pair

A direct solution is to compare every pair of time points.

For each pair, convert both times to minutes and compute the circular difference.

For times `a` and `b`, the direct difference is:

```python
abs(a - b)
```

But because the clock wraps around, the circular difference is:

```python
min(abs(a - b), 1440 - abs(a - b))
```

This works, but it takes `O(n^2)` time.

Since the number of time points can be large, we should avoid comparing every pair.

## Key Insight

There are only:

```python
24 * 60 = 1440
```

possible time values in one day.

Also, after converting times to minutes and sorting them, the minimum difference must occur between two adjacent values in sorted order, including the circular pair between the last and first time.

For example:

```python
["00:00", "00:30", "23:59"]
```

converts to:

```python
[0, 30, 1439]
```

Adjacent differences are:

```python
30 - 0 = 30
1439 - 30 = 1409
```

But we must also compare the wrap-around difference:

```python
1440 - 1439 + 0 = 1
```

So the answer is `1`.

## Algorithm

1. If there are more than `1440` time points, return `0`.

   By the pigeonhole principle, at least two time points must be equal.

2. Convert each time string to minutes since midnight.

   For `"HH:MM"`:

```python
hours * 60 + minutes
```

3. Sort the minute values.

4. Compare every adjacent pair.

5. Compare the circular pair: last time to first time across midnight.

6. Return the smallest difference.

## Correctness

After converting each time point to minutes since midnight, every time becomes an integer from `0` to `1439`.

Sorting these values places them in chronological order within the same day.

For any two non-adjacent times in sorted order, there is at least one time between them. Therefore, the gap between the non-adjacent pair cannot be smaller than all gaps among adjacent times inside that interval.

So the minimum non-circular difference must occur between adjacent sorted values.

The only pair not represented by normal adjacency is the pair across midnight: the largest time of the day and the smallest time of the day. The algorithm explicitly checks this wrap-around gap.

Therefore, the algorithm examines every possible candidate for the minimum circular time difference and returns the correct answer.

## Complexity

Let `n = len(timePoints)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n log n)` | Sorting the converted minute values |
| Space | `O(n)` | Store converted minute values |

The early duplicate rule can return `0` immediately when `n > 1440`.

## Implementation

```python
class Solution:
    def findMinDifference(self, timePoints: list[str]) -> int:
        if len(timePoints) > 1440:
            return 0

        minutes = []

        for time in timePoints:
            hour = int(time[:2])
            minute = int(time[3:])
            minutes.append(hour * 60 + minute)

        minutes.sort()

        answer = 1440

        for i in range(1, len(minutes)):
            answer = min(answer, minutes[i] - minutes[i - 1])

        wrap_difference = 1440 - minutes[-1] + minutes[0]
        answer = min(answer, wrap_difference)

        return answer
```

## Code Explanation

There are only `1440` possible minute values in a day:

```python
if len(timePoints) > 1440:
    return 0
```

If the input has more than `1440` values, at least two are equal, so the minimum difference is `0`.

Each time string is converted to minutes:

```python
hour = int(time[:2])
minute = int(time[3:])
minutes.append(hour * 60 + minute)
```

For example:

```python
"23:59" -> 23 * 60 + 59 = 1439
```

After sorting:

```python
minutes.sort()
```

we compare adjacent values:

```python
for i in range(1, len(minutes)):
    answer = min(answer, minutes[i] - minutes[i - 1])
```

Then we check the midnight wrap-around case:

```python
wrap_difference = 1440 - minutes[-1] + minutes[0]
```

For `"23:59"` and `"00:00"`, this gives:

```python
1440 - 1439 + 0 = 1
```

## Bucket Version

Because there are only `1440` possible times, we can avoid sorting by using a boolean bucket array.

```python
class Solution:
    def findMinDifference(self, timePoints: list[str]) -> int:
        if len(timePoints) > 1440:
            return 0

        seen = [False] * 1440

        for time in timePoints:
            hour = int(time[:2])
            minute = int(time[3:])
            value = hour * 60 + minute

            if seen[value]:
                return 0

            seen[value] = True

        first = None
        prev = None
        answer = 1440

        for value in range(1440):
            if not seen[value]:
                continue

            if first is None:
                first = value

            if prev is not None:
                answer = min(answer, value - prev)

            prev = value

        answer = min(answer, 1440 - prev + first)
        return answer
```

This version runs in `O(n + 1440)` time and uses `O(1440)` space.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.findMinDifference(["23:59", "00:00"]) == 1
    assert s.findMinDifference(["00:00", "23:59", "00:00"]) == 0
    assert s.findMinDifference(["01:01", "02:01", "03:00"]) == 59
    assert s.findMinDifference(["00:00", "12:00"]) == 720
    assert s.findMinDifference(["23:50", "00:10"]) == 20

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `["23:59", "00:00"]` | Checks wrap-around difference |
| Duplicate time | Minimum must be `0` |
| Nearby daytime values | Checks adjacent sorted difference |
| Opposite sides of day | Checks large equal split |
| Cross-midnight pair | Checks circular clock behavior |