This program was created to help Esther (our fictitious client) to find the minimum time difference between any two of her wake up times recorded in her journal

minTimeDifference.py

from itertools import combinations

def minDifference(wakeTimes):
    # if wakeTimes is an empty array
    if not wakeTimes:
        return 0
    
    # creates an array of wakeTimes in minute
    wakeTimesInMins = list(map( lambda x: int(x[0]) * 60 + int(x[1]), [ time.split(":") for time in wakeTimes ]))

    # ignores all invalid input i.e. any time entry that exceeds 23:59 === 1439
    wakeTimesInMins = list(filter( lambda y: y <= 1439 , wakeTimesInMins ))

    # if wakeTimes has only one time entry and it is invalid
    if not wakeTimesInMins:
        return "Wrong time entry. Please enter a time between 00:00 to 23:59."

    # if wakeTimes has only one time entry and it is valid
    if len(wakeTimesInMins) == 1:
        return wakeTimesInMins[0]

    
    # else if wakeTimes has more than one valid time entry
    else:
        minDiff = 1439
        for t1,t2 in tuple(combinations(wakeTimesInMins, 2)):
            if abs(t1 - t2) < minDiff:
                minDiff = abs(t1 - t2)
        return minDiff

if __name__ == "__main__":
    print(minDifference([]))                        # return 0
    print(minDifference(['24:00']))                 # return "Wrong time entry. Please enter a time between 00:00 to 23:59."
    print(minDifference(['2:30']))                  # return 150
    print(minDifference(['16:15','16:00','12:20'])) # return 15

Hello @IEdiong, thank you for participating in Week 7 of #AlgorithmFridays.

Your solution to help Esther get better at time management passes the test cases, so in terms of correctness, your solution works! Good job!

However, I noticed that you made use of the inbuilt combinations method which explores all possible combinations of a given set of times (in this case). By using that, what do you think the complexity of your solution now becomes?

Do you think there's a more optimal way you could have solved this problem without having to explore all the combinations of the times? By optimal I mean, O(1) space and O(N log N) time complexity?

I'd love to hear you thoughts.

Hello @meekg33k, thank you for taking the time to review and give feedback.

• I think by using the inbuilt combinations method my solution has a complexity of O(1) and O(N log N) for space and time complexity respectively.

• A more optimal way of solving this problem without exploring all the combinations would be:

else:
    minDiff = 1439
    wakeTimesInMins.sort()
    for i in range(len(wakeTimesInMins)-1):
        min = wakeTimesInMins[i+1] - wakeTimesInMins[i]
        if minDiff > min:
            minDiff = min
    return minDiff