Jobs

Interviews

Discussions

Compare Version Numbers

Medium

Compare Version Numbers

Medium

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What characters, other than digits and dots, can the version strings contain? Should I assume only digits and dots?
Can version strings have leading zeros in any of the version segments (e.g., '01.2.3')? How should I handle them?
How should I handle missing version segments? For example, is '1.0' greater than, less than, or equal to '1'?
Are the version strings guaranteed to be valid (e.g., not containing consecutive dots or ending with a dot)?
What should I return if the two version numbers are equal (specifically the integer value: 1, 0, or -1)?

Brute Force Solution

Approach

The brute force approach to comparing version numbers involves looking at each number segment individually and comparing them. We will need to methodically go through all segments in both version numbers and deal with different lengths.

Here's how the algorithm would work step-by-step:

First, split both version strings into individual number segments using the period as the separator.
Then, go through the segments in both version numbers, one by one, and turn them into actual numbers.
Compare the corresponding segments. If they are different, determine which version is greater and we are done.
If the segments are the same, move to the next pair of segments.
If one version has more segments than the other, treat any missing segments as zeros for the shorter version.
Continue comparing until we find a difference or reach the end of both versions. If we reach the end without finding any differences, the versions are the same.

Code Implementation

def compareVersion(version1, version2):
    version1_segments = version1.split('.')
    version2_segments = version2.split('.')
    
    max_length = max(len(version1_segments), len(version2_segments))

    for segment_index in range(max_length):
        # Treat missing segments as 0
        version1_segment = int(version1_segments[segment_index]) if segment_index < len(version1_segments) else 0

        version2_segment = int(version2_segments[segment_index]) if segment_index < len(version2_segments) else 0
        
        # Compare the integer values of each version segment.
        if version1_segment > version2_segment:
            return 1

        if version1_segment < version2_segment:
            return -1

    # If all segments are equal, the versions are the same
    return 0

Big(O) Analysis

Time Complexity

O(max(n, m)) – Let n be the number of segments in version1 and m be the number of segments in version2 after splitting by the period delimiter. The algorithm iterates through the segments of both version strings. In the worst case, the algorithm will iterate through all segments of the longer version string to compare them. Therefore, the time complexity is determined by the maximum number of segments between the two versions, which is O(max(n, m)).

Space Complexity

O(N) – The algorithm splits both version strings into lists of number segments. In the worst case, each version string could consist of N segments where N is the length of the input string, leading to two lists of size N. Thus, the auxiliary space used to store these lists scales linearly with the input size. Therefore, the space complexity is O(N).

Optimal Solution

Approach

We need to compare version numbers like you would compare numbers with decimals. The key idea is to split the version numbers into chunks, and then compare corresponding chunks as whole numbers. We handle missing chunks by treating them as zero.

Here's how the algorithm would work step-by-step:

First, split both version strings into separate number parts using the dot (.) as a separator.
Then, go through each part of both version numbers at the same time. Compare the number parts at the same position.
Before comparing, turn the text parts into actual numbers.
If one version has more parts than the other, treat the missing parts in the shorter version as zeros.
If the number parts are different, you know which version is bigger or smaller based on the number comparison.
If you reach the end and all number parts were the same, then the versions are equal.

Code Implementation

def compareVersion(version1: str, version2: str) -> int:
    version1_numbers = version1.split(".")
    version2_numbers = version2.split(".")
    max_length = max(len(version1_numbers), len(version2_numbers))

    for i in range(max_length):
        version1_number = 0
        version2_number = 0

        if i < len(version1_numbers):
            version1_number = int(version1_numbers[i])

        if i < len(version2_numbers):
            version2_number = int(version2_numbers[i])

        # Comparing the integer values of the version parts
        if version1_number > version2_number:
            return 1
        elif version1_number < version2_number:
            return -1

    # Versions are equal if all parts are the same
    return 0

Big(O) Analysis

Time Complexity

O(max(n, m)) – The time complexity is determined by the number of version parts in the two input strings, version1 and version2. We split each string into arrays of integers. The dominant operation is the iteration through these arrays to compare corresponding parts. We iterate up to the maximum length of the two arrays (n and m), treating missing parts as zero. Therefore, the time complexity is proportional to max(n, m), which is O(max(n, m)).

Space Complexity

O(N) – The algorithm splits both version strings into separate number parts, resulting in two lists. In the worst case, if the version strings consist only of '.' separators, the lists will contain N elements, where N is the length of the longer version string after splitting by '.' . Therefore, the auxiliary space used is proportional to the length of the longer version string when split into parts. This gives a space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty version strings	Return 0 if both are null/empty, -1 if version1 is null/empty and version2 is not, and 1 if version2 is null/empty and version1 is not.
Version strings with leading zeros in a version part	Parse each version part to an integer to effectively ignore leading zeros.
Version strings with only zeros (e.g., '0.0.0')	The integer parsing handles this correctly as the integer representation would be 0.
One version string is a prefix of the other (e.g., '1.0' vs '1.0.0')	Iterate through both version components, and consider missing components as 0.
Very large version numbers to cause integer overflow	Use long integers to avoid overflow issues during comparison of version parts.
Version strings with non-numeric characters	Throw an exception or return an error code, as only numeric versions are valid.
Extremely long version strings (memory constraints)	Implement the algorithm to process version numbers in chunks to avoid loading the entire string into memory.
Different number of parts in each version string	When one version string runs out of parts, treat the remaining parts of the other string as significant and continue comparison.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What characters, other than digits and dots, can the version strings contain? Should I assume only digits and dots?
Can version strings have leading zeros in any of the version segments (e.g., '01.2.3')? How should I handle them?
How should I handle missing version segments? For example, is '1.0' greater than, less than, or equal to '1'?
Are the version strings guaranteed to be valid (e.g., not containing consecutive dots or ending with a dot)?
What should I return if the two version numbers are equal (specifically the integer value: 1, 0, or -1)?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, split both version strings into individual number segments using the period as the separator.
Then, go through the segments in both version numbers, one by one, and turn them into actual numbers.
Compare the corresponding segments. If they are different, determine which version is greater and we are done.
If the segments are the same, move to the next pair of segments.
If one version has more segments than the other, treat any missing segments as zeros for the shorter version.
Continue comparing until we find a difference or reach the end of both versions. If we reach the end without finding any differences, the versions are the same.

Code Implementation

def compareVersion(version1, version2):
    version1_segments = version1.split('.')
    version2_segments = version2.split('.')
    
    max_length = max(len(version1_segments), len(version2_segments))

    for segment_index in range(max_length):
        # Treat missing segments as 0
        version1_segment = int(version1_segments[segment_index]) if segment_index < len(version1_segments) else 0

        version2_segment = int(version2_segments[segment_index]) if segment_index < len(version2_segments) else 0
        
        # Compare the integer values of each version segment.
        if version1_segment > version2_segment:
            return 1

        if version1_segment < version2_segment:
            return -1

    # If all segments are equal, the versions are the same
    return 0

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, split both version strings into separate number parts using the dot (.) as a separator.
Then, go through each part of both version numbers at the same time. Compare the number parts at the same position.
Before comparing, turn the text parts into actual numbers.
If one version has more parts than the other, treat the missing parts in the shorter version as zeros.
If the number parts are different, you know which version is bigger or smaller based on the number comparison.
If you reach the end and all number parts were the same, then the versions are equal.

Code Implementation

def compareVersion(version1: str, version2: str) -> int:
    version1_numbers = version1.split(".")
    version2_numbers = version2.split(".")
    max_length = max(len(version1_numbers), len(version2_numbers))

    for i in range(max_length):
        version1_number = 0
        version2_number = 0

        if i < len(version1_numbers):
            version1_number = int(version1_numbers[i])

        if i < len(version2_numbers):
            version2_number = int(version2_numbers[i])

        # Comparing the integer values of the version parts
        if version1_number > version2_number:
            return 1
        elif version1_number < version2_number:
            return -1

    # Versions are equal if all parts are the same
    return 0

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty version strings	Return 0 if both are null/empty, -1 if version1 is null/empty and version2 is not, and 1 if version2 is null/empty and version1 is not.
Version strings with leading zeros in a version part	Parse each version part to an integer to effectively ignore leading zeros.
Version strings with only zeros (e.g., '0.0.0')	The integer parsing handles this correctly as the integer representation would be 0.
One version string is a prefix of the other (e.g., '1.0' vs '1.0.0')	Iterate through both version components, and consider missing components as 0.
Very large version numbers to cause integer overflow	Use long integers to avoid overflow issues during comparison of version parts.
Version strings with non-numeric characters	Throw an exception or return an error code, as only numeric versions are valid.
Extremely long version strings (memory constraints)	Implement the algorithm to process version numbers in chunks to avoid loading the entire string into memory.
Different number of parts in each version string	When one version string runs out of parts, treat the remaining parts of the other string as significant and continue comparison.