Last active
May 28, 2021 07:40
-
-
Save deedee47/a8e3741ace291b1de884db73ac995a48 to your computer and use it in GitHub Desktop.
Returns minimum time difference from a given list of HH:mm time entries
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public long getMinDifferenceInMinutes(String[] journal){ | |
if(journal == null) return 0; | |
if(journal.length == 0) return 0; | |
//Using a set to store unique and valid entries | |
//if any entry is duplicated, it will auto break because that will be the minimum time difference | |
//TreeSet stores data in natural order - O(Log N) time complexity - better than sorting array with NLogN | |
//sorting keeps times close together and will eliminate comparing each entry with all other elements | |
//Tradeoff extra space for faster sort process | |
Set<Long> validEntries = new TreeSet<>(); | |
//based on requirement, journal entries are in HH:MM - 24hr format | |
SimpleDateFormat dateFormat = new SimpleDateFormat("HH:mm"); | |
//strip out invalid entries and put the rest in the tree set - O(N) | |
for(int index = 0; index < journal.length; index++){ | |
try { | |
long timeInMs = dateFormat.parse(journal[index]).getTime(); | |
if(validEntries.contains(timeInMs)) return 0; | |
validEntries.add(timeInMs); | |
} catch (ParseException e) { | |
//String is in a wrong format - ignore | |
continue; | |
} | |
} | |
//no valid entries after the filter | |
if(validEntries.size() == 0) return 0; | |
//find difference - O(N) worst case | |
long prev = Long.MIN_VALUE; | |
long diff = Long.MIN_VALUE; | |
for(long entry : validEntries){ | |
if(prev != Long.MIN_VALUE){ | |
long timeDiff = Math.abs(entry - prev); | |
diff = (diff != Long.MIN_VALUE) ? Math.min(timeDiff, diff) : timeDiff; | |
} | |
prev = entry; | |
} | |
return (diff!=Long.MIN_VALUE) ? TimeUnit.MILLISECONDS.toMinutes(diff) : TimeUnit.MILLISECONDS.toMinutes(prev); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Hello @deedee47, congratulations 🎉 your solution has been selected as one of the winning solutions in Week 7 of #AlgorithmFridays. Your solution is clean and readable and passed the test cases.
One feedback for you is, when submitting your solution, please endeavor to add the
import
statement for all the packages your solution uses.Out of the many winning solutions, only 3 will be selected for the $20 prize in a raffle draw. The raffle draw will hold today, Friday May 28 at 3.00pm WAT (7.00 am PST)
If you are interested in being a part of the raffle draw, please send me a DM on Twitter @meekg33k so I can share the event invite with you.
NB: Only solutions of participants who indicated interest in the raffle draw will be considered.
Thanks once again for participating and see you later today for Week 8 of #AlgorithmFridays.