Problem Statement

Given two version numbers,version1andversion2, compare them.

Version numbers consist of one or more revisions joined by a dot'.'. Each revision consists of digits and may contain leading zeros. Every revision contains at least one character. Revisions are 0-indexed from left to right, with the leftmost revision being revision 0, the next revision being revision 1, and so on. For example 2.5.33 and 0.1 are valid version numbers.

To compare version numbers, compare their revisions in left-to-right order. Revisions are compared using their  integer value ignoring any leading zeros. This means that revisions  1  and  001  are considered  equal. If a version number does not specify a revision at an index, then treat the revision as0. For example, version 1.0 is less than version 1.1 because their revision 0s are the same, but their revision 1s are 0 and 1 respectively, and 0 < 1.

Return the following:

• If version1 < version2, return -1.

• If version1 > version2, return 1.

• Otherwise, return 0.

Examples

Example 1:

Input: version1 = "1.01", version2 = "1.001"
Output: 0
Explanation: Ignoring leading zeroes, both "01" and "001" represent the same integer "1".

Example 2:

Input: version1 = "1.0", version2 = "1.0.0"
Output: 0
Explanation: version1 does not specify revision 2, which means it is treated as "0".

Example 3:

Input: version1 = "0.1", version2 = "1.1"
Output: -1
Explanation: version1's revision 0 is "0", while version2's revision 0 is "1". 0 < 1, so version1 < version2.

Constraints

• 1 <= version1.length, version2.length <= 500

• version1 and version2 only contain digits and '.'.

• version1 and version2are valid version numbers.

• All the given revisions in  version1 and version2  can be stored in a  32-bit integer.

Intuition

Understanding the problem

Before diving into solving this problem, let's take a moment to understand the problem itself.

We're given two versions version1 and version2 we need to check:

• if version1 > version2, then return 1

• else if version1 < version2, then return -1

• else return 0 (meaning both are equal)

The most important part is to understand how to compare the two versions. The versions look like this:

A version is a '.' separated group of revisions, for example 5.004.3.06 .

• We compare versions from left to right, comparing revisions in order from left to right. In the example given, version1has 4 revisions andversion2has 3 revisions.

• We compare the 0th revision of each version, then the 1st revision, followed by the 2nd, and so on.

• It's important to note that a revision might have a leading zeros, which should be disregarded.

• Additionally, it's not required for version1 and version2 to have the same number of revisions. If a revision is not present then it should be treated as 0.

Approach

One way to approach this question is to split version1 and version2 by '.' and then compare indexes of the resulting arrays. Lets explore this approach:

• Split version1 and version2 by '.'

• Find which resulting array is larger.

• Loop over the larger range.

• Convert each revision to integer, if a revision is not present, consider it as zero.

• Compare revision1 and revision2.

  • if revision1 > revision2, then return 1

  • else if revision1 < revision2, the return -1

• After we have looped over, we can return 0, as it means all the revisions were the same. Hence the versions are same as well.

Solution

Python code:

# TC: O(n)
# SC: O(n)
class Solution:
    def compareVersion(self, version1: str, version2: str) -> int:
        # split version1 by '.'
        version1_split=version1.split('.')
        # split version2 by '.'
        version2_split=version2.split('.')
        # find the larger length
        n=max(len(version1_split),len(version2_split))        
        # iterate over larger range
        for index in range(n):
            # form revision1, if valid, else 0
            revision2=int(version1_split[index]) if index<len(version1_split) else 0
            # form revision2, if valid, else 0
            revision2=int(version2_split[index]) if index<len(version2_split) else 0
            # check if revision1>revision2
            if revision1>revision2:
                return 1
            # check if revision1<revision2
            elif revision2<revision2:
                return -1
        # return 0, meaning both versions are equal
        return 0

Time and Space complexity

Time Complexity:

$$O(n)$$

As we're iterating over the larger range and in worst case we will iterate over the entire range.

Space Complexity:

$$O(n)$$

As we're allocating extra space when we split the versions by '.'

Conclusion

This problem is quite simple. Once you understand the problem statement, it becomes clear what needs to be done.

Hope that explanation made sense and you found this blog helpful. If you've made it this far, please give it a like and drop a comment.

Happy Coding!🚀