165. Compare Version Numbers - Solution

Q: Is Compare Version Numbers easy or hard?

Compare Version Numbers is classified as a medium-level problem. The logic is straightforward, but edge cases such as leading zeros, unequal revision counts, and empty segments require careful handling.

Q: Compare Version Numbers Python/Java solution

In Python or Java, you can split the version strings using '.' and iterate through the resulting arrays while converting each component to an integer. Alternatively, implement a two-pointer loop that constructs revision numbers character by character for a constant-space solution.

Q: How to solve Compare Version Numbers in O(n)?

Traverse both version strings and parse each revision sequentially. Either split the strings by '.' and compare each numeric component, or use two pointers to build integers until a dot is reached. Compare each revision pair and return once a difference is found.

Q: What is the best approach for Compare Version Numbers?

The two-pointer traversal approach is generally considered the best. It scans both version strings simultaneously, builds each revision number on the fly, and compares them without creating additional arrays. This achieves O(n) time and O(1) space complexity while keeping the logic efficient for large inputs.

Q: Is Compare Version Numbers asked at Google/Amazon/Meta?

Compare Version Numbers has appeared in interviews at companies such as Amazon and Google because it tests careful string parsing and edge case handling. Candidates must handle leading zeros, different revision lengths, and missing components correctly.

Q: What data structure is used in Compare Version Numbers?

The problem mainly uses string processing and sequential traversal. The split-based solution temporarily stores revisions in arrays, while the optimized solution relies on two pointers and integer variables to parse revisions directly from the string.

Q: What is the time complexity of Compare Version Numbers?

The time complexity is O(n), where n is the total length of both version strings. Every character is processed at most once while parsing revision numbers and comparing them. Both the split-based method and the two-pointer approach run in linear time.

The problem

Given two version strings, version1 and version2, compare them. A version string consists of revisions separated by dots '.'. The value of the revision is its integer conversion ignoring leading zeros.

To compare version strings, compare their revision values in left-to-right order. If one of the version strings has fewer revisions, treat the missing revision values as 0.

Return the following:

If version1 < version2, return -1.
If version1 > version2, return 1.
Otherwise, return 0.

Example 1:

Input: version1 = "1.2", version2 = "1.10"

Output: -1

Explanation:

version1's second revision is "2" and version2's second revision is "10": 2 < 10, so version1 < version2.

Example 2:

Input: version1 = "1.01", version2 = "1.001"

Output: 0

Explanation:

Ignoring leading zeroes, both "01" and "001" represent the same integer "1".

Example 3:

Input: version1 = "1.0", version2 = "1.0.0.0"

Output: 0

Explanation:

version1 has less revisions, which means every missing revision are treated as "0".

Constraints:

1 <= version1.length, version2.length <= 500
version1 and version2 only contain digits and '.'.
version1 and version2 are valid version numbers.
All the given revisions in version1 and version2 can be stored in a 32-bit integer.

Approach overview

Problem Overview: You are given two version strings such as "1.01" and "1.001". Each version is composed of revisions separated by dots. The task is to compare them numerically revision by revision and return whether one version is greater, smaller, or equal.

Approach 1: Split and Compare Each Component (O(n) time, O(n) space)

The most direct solution splits both version strings using the dot delimiter and compares the resulting revision numbers. Each component is parsed as an integer to ignore leading zeros. Iterate through both arrays simultaneously and compare corresponding revisions. If one version has fewer parts, treat missing revisions as 0. This approach is straightforward and easy to implement using built-in string utilities, making it a practical choice during interviews when clarity matters more than micro-optimizations.

Most languages provide efficient split operations, so implementation becomes a simple loop comparing integers. However, splitting creates extra arrays, which introduces O(n) space complexity. For extremely long version strings or memory-constrained environments, avoiding additional allocations can be beneficial. The approach relies purely on string manipulation and sequential iteration.

Approach 2: Two-pointer Comparison Traversal (O(n) time, O(1) space)

This method avoids splitting entirely by scanning both version strings using two pointers. Each pointer traverses its string and constructs the current revision number digit by digit until reaching a dot or the end. After parsing the current revision for both strings, compare the two integers. If they differ, return the result immediately. Otherwise, move past the dot and continue processing the next revision.

The key insight is that each revision can be built incrementally while traversing the string, eliminating the need for intermediate arrays. Missing revisions naturally evaluate to 0 once a pointer reaches the end of its string. This keeps space usage constant while still processing every character once, resulting in O(n) time complexity. This pattern frequently appears in problems involving segmented string comparisons.

Recommended for interviews: Start with the split-based approach because it clearly communicates the logic of comparing revision numbers. After that, mention the two-pointer traversal as an optimization that removes extra memory usage. Interviewers often expect candidates to recognize the two pointers technique for parsing structured string input efficiently.

Approach 1: Split and Compare Each Component

This approach involves splitting the version strings into individual components using the dot delimiter. We then convert these components into integers and compare them one by one. If one version string is shorter, we treat the missing components as 0, allowing a fair comparison.

Python

class Solution:
    def compareVersion(self, version1: str, version2: str) -> int:
        v1 = version1.split('.')
        v2 = version2.split('.')

        length = max(len(v1), len(v2))
        for i in range(length):
            num1 = int(v1[i]) if i < len(v1) else 0
            num2 = int(v2[i]) if i < len(v2) else 0
            if num1 < num2:
                return -1
            if num1 > num2:
                return 1

        return 0

Java

public class CompareVersion {
    public int compareVersion(String version1, String version2) {
        String[] v1 = version1.split("\\.");
        String[] v2 = version2.split("\\.");

        int length = Math.max(v1.length, v2.length);
        for (int i = 0; i < length; i++) {
            int num1 = i < v1.length ? Integer.parseInt(v1[i]) : 0;
            int num2 = i < v2.length ? Integer.parseInt(v2[i]) : 0;
            if (num1 < num2) return -1;
            if (num1 > num2) return 1;
        }

        return 0;
    }
}

C++

#include <iostream>
#include <vector>
#include <sstream>

using namespace std;

int compareVersion(string version1, string version2) {
    istringstream v1(version1), v2(version2);
    string num1, num2;
    while (getline(v1, num1, '.') || getline(v2, num2, '.')) {
        int n1 = num1.empty() ? 0 : stoi(num1);
        int n2 = num2.empty() ? 0 : stoi(num2);
        if (n1 < n2) return -1;
        if (n1 > n2) return 1;
        num1.clear();
        num2.clear();
    }
    return 0;
}

JavaScript

function compareVersion(version1, version2) {
    const v1 = version1.split('.');
    const v2 = version2.split('.');

    const length = Math.max(v1.length, v2.length);
    for (let i = 0; i < length; i++) {
        const num1 = i < v1.length ? parseInt(v1[i]) : 0;
        const num2 = i < v2.length ? parseInt(v2[i]) : 0;
        if (num1 < num2) return -1;
        if (num1 > num2) return 1;
    }

    return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compareVersion(char * version1, char * version2){
    char *v1 = strdup(version1);
    char *v2 = strdup(version2);
    char *part1;
    char *part2;
    int num1, num2;

    part1 = strtok(v1, ".");
    part2 = strtok(v2, ".");

    while(part1 != NULL || part2 != NULL) {
        num1 = part1 ? atoi(part1) : 0;
        num2 = part2 ? atoi(part2) : 0;

        if(num1 < num2) return -1;
        if(num1 > num2) return 1;

        part1 = part1 ? strtok(NULL, ".") : NULL;
        part2 = part2 ? strtok(NULL, ".") : NULL;
    }

    return 0;
}

public class Solution {
    public int CompareVersion(string version1, string version2) {
        string[] v1 = version1.Split('.');
        string[] v2 = version2.Split('.');

        int length = Math.Max(v1.Length, v2.Length);
        for (int i = 0; i < length; i++) {
            int num1 = i < v1.Length ? int.Parse(v1[i]) : 0;
            int num2 = i < v2.Length ? int.Parse(v2[i]) : 0;
            if (num1 < num2) return -1;
            if (num1 > num2) return 1;
        }

        return 0;
    }
}

The Python solution utilizes the split method for breaking down version strings. Each component is converted to an integer for comparison using a loop that handles shorter version strings by assuming missing components as 0.

Complexity

Time Complexity: O(n + m), where n and m are lengths of version1 and version2 respectively.
Space Complexity: O(n + m) for storing split components.

Try this approach in the editor

Approach 2: Two-pointer Comparison Traversal

This approach utilizes two pointers to traverse each version string's components simultaneously. By identifying and isolating numerical values between dots without splitting the string, we optimize for memory usage. Each number is evaluated and compared until a determination is made or the end is reached.

Python

class Solution:
    def compareVersion(self, version1: str, version2: str) -> int:
        i, j = 0, 0

        while i < len(version1) or j < len(version2):
            num1, num2 = 0, 0

            while i < len(version1) and version1[i] != '.':
                num1 = num1 * 10 + int(version1[i])
                i += 1
            while j < len(version2) and version2[j] != '.':
                num2 = num2 * 10 + int(version2[j])
                j += 1

            if num1 < num2:
                return -1
            if num1 > num2:
                return 1

            i += 1
            j += 1

        return 0

Java

public class CompareVersion {
    public int compareVersion(String version1, String version2) {
        int i = 0, j = 0;
        int n = version1.length(), m = version2.length();

        while (i < n || j < m) {
            int num1 = 0, num2 = 0;
            while (i < n && version1.charAt(i) != '.') {
                num1 = num1 * 10 + version1.charAt(i) - '0';
                i++;
            }
            while (j < m && version2.charAt(j) != '.') {
                num2 = num2 * 10 + version2.charAt(j) - '0';
                j++;
            }

            if (num1 < num2) return -1;
            if (num1 > num2) return 1;
            i++;
            j++;
        }

        return 0;
    }
}

C++

#include <iostream>
#include <string>

using namespace std;

int compareVersion(string version1, string version2) {
    int i = 0, j = 0;
    while (i < version1.length() || j < version2.length()) {
        long num1 = 0, num2 = 0;

        while (i < version1.length() && version1[i] != '.') {
            num1 = num1 * 10 + (version1[i] - '0');
            i++;
        }
        while (j < version2.length() && version2[j] != '.') {
            num2 = num2 * 10 + (version2[j] - '0');
            j++;
        }

        if (num1 < num2) return -1;
        if (num1 > num2) return 1;

        i++;
        j++;
    }

    return 0;
}

JavaScript

function compareVersion(version1, version2) {
    let i = 0, j = 0;

    while (i < version1.length || j < version2.length) {
        let num1 = 0, num2 = 0;

        while (i < version1.length && version1[i] !== '.') {
            num1 = num1 * 10 + (version1[i] - '0');
            i++;
        }
        while (j < version2.length && version2[j] !== '.') {
            num2 = num2 * 10 + (version2[j] - '0');
            j++;
        }

        if (num1 < num2) return -1;
        if (num1 > num2) return 1;

        i++;
        j++;
    }

    return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

int compareVersion(char* version1, char* version2) {
    int i = 0, j = 0;
    while (version1[i] != '\0' || version2[j] != '\0') {
        long num1 = 0, num2 = 0;
        while (isdigit(version1[i])) {
            num1 = num1 * 10 + (version1[i] - '0');
            i++;
        }
        while (isdigit(version2[j])) {
            num2 = num2 * 10 + (version2[j] - '0');
            j++;
        }
        if (num1 < num2) return -1;
        if (num1 > num2) return 1;
        if (version1[i] != '\0') i++;
        if (version2[j] != '\0') j++;
    }
    return 0;
}

public class Solution {
    public int CompareVersion(string version1, string version2) {
        int i = 0, j = 0;

        while (i < version1.Length || j < version2.Length) {
            int num1 = 0, num2 = 0;

            while (i < version1.Length && version1[i] != '.') {
                num1 = num1 * 10 + (version1[i] - '0');
                i++;
            }
            while (j < version2.Length && version2[j] != '.') {
                num2 = num2 * 10 + (version2[j] - '0');
                j++;
            }

            if (num1 < num2) return -1;
            if (num1 > num2) return 1;

            i++;
            j++;
        }

        return 0;
    }
}

This Python approach aligns with using manual parsing, moving through each string character-by-character to logically assemble each integer for a direct comparison of non-preprocessed data.

Complexity

Time Complexity: O(n + m), with n and m representing the lengths of version1 and version2.
Space Complexity: O(1) since only a few scalar integers are held throughout the process.

Try this approach in the editor

Approach 3: Two Pointers

Traverse both strings simultaneously using two pointers i and j, which point to the current positions in each string, starting with i = j = 0.

Each time, extract the corresponding revision numbers from both strings, denoted as a and b. Compare a and b: if a \lt b, return -1; if a \gt b, return 1; if a = b, continue to compare the next pair of revision numbers.

The time complexity is O(max(m, n)), and the space complexity is O(1), where m and n are the lengths of the two strings.

TypeScript

function compareVersion(version1: string, version2: string): number {
    const [m, n] = [version1.length, version2.length];
    let [i, j] = [0, 0];
    while (i < m || j < n) {
        let [a, b] = [0, 0];
        while (i < m && version1[i] !== '.') {
            a = a * 10 + +version1[i];
            i++;
        }
        while (j < n && version2[j] !== '.') {
            b = b * 10 + +version2[j];
            j++;
        }
        if (a !== b) {
            return a < b ? -1 : 1;
        }
        i++;
        j++;
    }
    return 0;
}

func compareVersion(version1 string, version2 string) int {
	m, n := len(version1), len(version2)
	for i, j := 0, 0; i < m || j < n; i, j = i+1, j+1 {
		var a, b int
		for i < m && version1[i] != '.' {
			a = a*10 + int(version1[i]-'0')
			i++
		}
		for j < n && version2[j] != '.' {
			b = b*10 + int(version2[j]-'0')
			j++
		}
		if a < b {
			return -1
		}
		if a > b {
			return 1
		}
	}
	return 0
}

Rust

impl Solution {
    pub fn compare_version(version1: String, version2: String) -> i32 {
        let (bytes1, bytes2) = (version1.as_bytes(), version2.as_bytes());
        let (m, n) = (bytes1.len(), bytes2.len());
        let (mut i, mut j) = (0, 0);

        while i < m || j < n {
            let mut a = 0;
            let mut b = 0;

            while i < m && bytes1[i] != b'.' {
                a = a * 10 + (bytes1[i] - b'0') as i32;
                i += 1;
            }
            while j < n && bytes2[j] != b'.' {
                b = b * 10 + (bytes2[j] - b'0') as i32;
                j += 1;
            }

            if a != b {
                return if a < b { -1 } else { 1 };
            }

            i += 1;
            j += 1;
        }

        0
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Split and Compare Each Component	Time Complexity: O(n + m), where n and m are lengths of version1 and version2 respectively. Space Complexity: O(n + m) for storing split components.
Two-pointer Comparison Traversal	Time Complexity: O(n + m), with n and m representing the lengths of version1 and version2. Space Complexity: O(1) since only a few scalar integers are held throughout the process.
Two Pointers	–

Complexity analysis

Approach	Time	Space	When to Use
Split and Compare Each Component	O(n)	O(n)	Best for readability and quick implementation using built-in string split utilities.
Two-pointer Comparison Traversal	O(n)	O(1)	Preferred when minimizing memory usage or demonstrating deeper string parsing skills.

Frequently asked questions

Is Compare Version Numbers easy or hard?

Compare Version Numbers is classified as a medium-level problem. The logic is straightforward, but edge cases such as leading zeros, unequal revision counts, and empty segments require careful handling.

Compare Version Numbers Python/Java solution

In Python or Java, you can split the version strings using '.' and iterate through the resulting arrays while converting each component to an integer. Alternatively, implement a two-pointer loop that constructs revision numbers character by character for a constant-space solution.

How to solve Compare Version Numbers in O(n)?

Traverse both version strings and parse each revision sequentially. Either split the strings by '.' and compare each numeric component, or use two pointers to build integers until a dot is reached. Compare each revision pair and return once a difference is found.

What is the best approach for Compare Version Numbers?

The two-pointer traversal approach is generally considered the best. It scans both version strings simultaneously, builds each revision number on the fly, and compares them without creating additional arrays. This achieves O(n) time and O(1) space complexity while keeping the logic efficient for large inputs.

Is Compare Version Numbers asked at Google/Amazon/Meta?

Compare Version Numbers has appeared in interviews at companies such as Amazon and Google because it tests careful string parsing and edge case handling. Candidates must handle leading zeros, different revision lengths, and missing components correctly.

What data structure is used in Compare Version Numbers?

The problem mainly uses string processing and sequential traversal. The split-based solution temporarily stores revisions in arrays, while the optimized solution relies on two pointers and integer variables to parse revisions directly from the string.

What is the time complexity of Compare Version Numbers?

The time complexity is O(n), where n is the total length of both version strings. Every character is processed at most once while parsing revision numbers and comparing them. Both the split-based method and the two-pointer approach run in linear time.

Compare Version Numbers solution and explanation

The problem

Approach overview

Approach 1: Split and Compare Each Component

Approach 2: Two-pointer Comparison Traversal

Approach 3: Two Pointers

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Compare Version Numbers solution and explanation

The problem

Approach overview

Approach 1: Split and Compare Each Component

Approach 2: Two-pointer Comparison Traversal

Approach 3: Two Pointers

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems