Compare Version Numbers | InterviewBit | Solution Explained

I explain the solution to the problem Compare Version Numbers on InterviewBit in detail. Problem Link.

0. Compare Version Numbers: Problem Discussion

0.0. IO Format

  • Given: two strings which are version numbers, ver1 and ver2
  • Goal: 
    • If ver1 > ver2 return 1,
    • If ver1 < ver2 return -1,
    • otherwise return 0.

0.1. Examples

 Compare Version Numbers: sample test case
Compare Version Numbers: sample test case

1. Compare Version Numbers: Observations & Logic

1.0. Intuitions

  • the versions are strings, and we need a way to compare the versions
  • converting strings to integers will help us compare them
  • we know that a version has different numbers split by ‘.’, so we can
    • split the string by ‘.’ character
    • map all the string values to an integer
    • get the list
  • we can do all that in python using one single line: list(map(int, ver.split('.')))
 Compare Version Numbers: converting the string to a list of integers
Compare Version Numbers: converting the string to a list of integers

All right! We have extracted the information out of the input. Now what?

We need a way to compare two items in the two lists, simultaneously. So, we can use the zip operator in python3.

class Solution:
    def compareVersion(self, ver1, ver2):
        ver1 = list(map(int, ver1.split('.')))
        ver2 = list(map(int, ver2.split('.')))

        for v1, v2 in zip(ver1, ver2):
            if v1 > v2: return 1
            elif v2 > v1: return -1
        
        return 0

1.1. Implementation Issue

Here’s the thing though, zip only works well if the length of the iterables are the same. That is, only when len(v1) == len(v2) list.

In the case where there is a smaller list, zip will terminate with it.

For example, if we zip([1,2,3], [1,2,3,7]) we will terminate at 3! We will never get a chance to compare 7. So what do we do?

Here lies a key point: if one version is shorter in length to the other, we can append dummy zeroes to it!

For example, if we have a tricky case like [1,3,3,0,0,7] and [1,3,3], we need to be able to pad zeroes like so:

 Compare Version Numbers: padding the list with zeroes
Compare Version Numbers: padding the list with zeroes

One way to not do this manually is to use zip_longest from itertools, as the implementation below will show.

2. Compare Version Numbers: Implementation

2.0. Code

from itertools import zip_longest

class Solution:
    def compareVersion(self, ver1, ver2):
        ver1 = list(map(int, ver1.split('.')))
        ver2 = list(map(int, ver2.split('.')))
        
        for v1, v2 in zip_longest(ver1, ver2, fillvalue=0):
            if v1 > v2: return 1
            elif v2 > v1: return -1
        
        return 0

2.1. Code (without zip_longest)

class Solution:
    def compareVersion(self, ver1, ver2):
        ver1 = list(map(int, ver1.split('.')))
        ver2 = list(map(int, ver2.split('.')))
        
        i, j = 0, 0
        m, n = len(ver1), len(ver2)
        if m > n: 
            ver2.extend([0]*(m-n))
        elif n > m:
            ver1.extend([0]*(n-m))

        for v1, v2 in zip(ver1, ver2):
            if v1 > v2: return 1
            elif v2 > v1: return -1
        
        return 0

2.2. Complexity Analysis

  • Time: O(N), where N is the number of elements in the longest list, which can be the same order as the number of characters in the string: 1.1.1 --> [1,1,1]
  • Space: O(N), since we have to store the lists of integers of both the versions separately

Avatar for Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.

    Comments

    1. Please write the proof.

    2. This solution need an amendment for 2 digit number.

    3. Please write a Proof for this

    Leave a Reply

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

    This site uses Akismet to reduce spam. Learn how your comment data is processed.