Leetcode | Compare Version Numbers

I decided to do an easy one today, but it still had a few good tricks! Here is the prompt:

Ok, seems straightforward enough. Let’s think this through. How are we comparing version numbers? Well, the left-most number has the most priority, one to the right the second most priority, etc… we should just be able to compare these version numbers in order from left to right. Right?

Well, one caveat we need to consider is what happens if one version number is longer than another. We could check the lengths and return the longer one… but there is an edge case there that doesn’t work out (consider 1.0 and 1). So what else can we do?

Simply, just make them the same length! Zero-pad the shorter entry on the right so that they’re the same length. Then we can simply compare. Take a look:

I could clean up my padd function a bit, but it gets the job done. And that’s it!

Complexity Analysis

Let’s see, we may have to pad one of the numbers with zeros, which will take O(d) time where d is the difference in length between the two strings. Then we have to go through the length of the split version numbers once. This is O(n). This term will dominate the zero padding so I think it’s safe to ignore it. Therefore the time complexity is O(n) where n is the size of the longest version number after splitting.

For space, we save two split version numbers which is by definition O(n) as well. Therefore the space complexity is O(n) as well.

I think if we didn’t split into arrays and instead just did the comparisons on the original strings we could get this to constant space, but this speedup doesn’t really seem worth it to me in this problem.

Leave a Reply

Your email address will not be published. Required fields are marked *

*