Leetcode | Compare Version Numbers

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

Compare two version numbers version1 and version2.
If version1 > version2 return 1; if version1 < version2 return -1;otherwise return 0.

You may assume that the version strings are non-empty and contain only digits and the . character.
The . character does not represent a decimal point and is used to separate number sequences.
For instance, 2.5 is not "two and a half" or "half way to version three", it is the fifth second-level revision of the second first-level revision.

Example 1:
Input: version1 = "0.1", version2 = "1.1" Output: -1
Example 2:
Input: version1 = "1.0.1", version2 = "1" Output: 1
Example 3:
Input: version1 = "7.5.2.4", version2 = "7.5.3" Output: -1

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:

class Solution:
    def compareVersion(self, version1, version2):
        v1 = self.version_to_array(version1)
        v2 = self.version_to_array(version2)
        v1, v2 = self.padd(v1, v2)

        for i in range(min([len(v1), len(v2)])):
            if int(v1[i]) > int(v2[i]):
                return 1
            elif int(v1[i]) < int(v2[i]):
                return -1
        return 0

    def version_to_array(self, version):
        return version.split('.')

    def padd(self, v1, v2):
        if len(v1) > len(v2):
            diff = len(v1) - len(v2)
            for i in range(diff):
                v2 += ['0']
        elif len(v2) > len(v1):
            diff = len(v2) - len(v1)
            for i in range(diff):
                v1 += ['0']
        return v1, v2

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.