Skip to main content
Talentd

Compare Version Numbers - Solution & Explanation

MediumTwo PointersString17 min readAsked at: Amazon, Microsoft, Apple +8
Practice this problem

Problem Statement

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.

The C solution uses strtok to split the version strings by dot character. Each component is converted to an integer using atoi. We then compare corresponding components, returning -1 or 1 if one is smaller or greater, respectively. The loop continues until all components are compared.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n + m), where n and m are lengths of version1 and version2 respectively.
Space Complexity: O(n + m) for holding the 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.

The C solution employs a method where pointers traverse each version string, constructing numerical values between dots manually. This avoids unnecessary string operations and directly compares values to determine the result.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n + m), where n and m are the lengths of version1 and version2.
Space Complexity: O(1), as no significant additional space is used.

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.

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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 holding the split components.

Two-pointer Comparison Traversal

Time Complexity: O(n + m), where n and m are the lengths of version1 and version2.
Space Complexity: O(1), as no significant additional space is used.

Two Pointers—

Detailed Complexity Analysis

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

Video Solution

Compare Version Numbers | Leetcode 165 | Strings | Day-25 • Ayushi Sharma • 13,144 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Compare Version Numbers with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Palindromic Substring

Next

Container With Most Water