algoadvance

Leetcode 539. Minimum Time Difference

Problem Statement

Given a list of 24-hour clock time points in “HH:MM” format, return the minimum minutes difference between any two time points in the list.

Clarifying Questions

  1. Input Constraints:
    • What is the maximum size of the input list?
    • Should the list always contain valid time points in “HH:MM” format?
  2. Output Requirements:
    • What should be returned if the input list is empty or contains only one time point?

After assuming or asking for these clarifications, let’s proceed with the solution.

Strategy

  1. Convert Time Points to Minutes:
    • Convert each time point from “HH:MM” to the total minutes elapsed since “00:00” (midnight).
  2. Sort the Minutes:
    • Sort the array of minutes.
  3. Compute Minimum Difference:
    • Compute the differences between each consecutive time point in the sorted list.
    • Also consider the wrap-around difference between the last time point of the day and the first time point of the day.
  4. Return Minimum Difference:
    • Return the smallest of these differences.

Code

Here is the Java solution for the problem:

import java.util.*;

public class Solution {

    public int findMinDifference(List<String> timePoints) {
        int n = timePoints.size();
        int[] minutes = new int[n];
        
        // Convert each timePoint to minutes since 00:00
        for (int i = 0; i < n; i++) {
            String time = timePoints.get(i);
            String[] parts = time.split(":");
            int hours = Integer.parseInt(parts[0]);
            int mins = Integer.parseInt(parts[1]);
            minutes[i] = hours * 60 + mins;
        }
        
        // Sort the array of minutes
        Arrays.sort(minutes);
        
        // Compute the minimum difference
        int minDiff = Integer.MAX_VALUE;
        for (int i = 1; i < minutes.length; i++) {
            int diff = minutes[i] - minutes[i - 1];
            minDiff = Math.min(minDiff, diff);
        }
        
        // Wrap-around difference (last and first time point)
        int wrapAroundDiff = (1440 + minutes[0] - minutes[n - 1]) % 1440;  // ensuring non-negative difference
        minDiff = Math.min(minDiff, wrapAroundDiff);
        
        return minDiff;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        List<String> timePoints = Arrays.asList("23:59", "00:00");

        int result = solution.findMinDifference(timePoints);
        System.out.println(result);  // Should print 1
    }
}

Time Complexity

Hence, the overall time complexity is O(n log n), where n is the number of time points.

This solution is optimal and works efficiently within the permissible bounds of typical input sizes for such interview problems.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI