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:
version1 < version2, return -1.version1 > version2, return 1.
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 <= 500version1 and version2 only contain digits and '.'.version1 and version2 are valid version numbers.version1 and version2 can be stored in a 32-bit integer.Problem Overview: You receive two version strings such as "1.02.3" and "1.2.003". Each dot-separated segment represents a revision number. Compare revisions from left to right and determine whether version1 is greater, smaller, or equal to version2 while ignoring leading zeros.
Approach 1: Split and Compare Each Component (Time: O(n), Space: O(n))
The direct solution splits both version strings using the dot delimiter and compares corresponding components one by one. Convert each segment to an integer so leading zeros like "001" and "1" become equivalent. Iterate through the longer of the two lists; if one version runs out of segments, treat the missing revision as 0. As soon as a pair of integers differs, return 1 or -1. If every segment matches, the versions are equal.
This approach is simple and readable. Most languages provide built-in string splitting and integer parsing, which keeps implementation short. The tradeoff is extra memory for storing arrays of revision components. Time complexity is O(n) where n is the total length of both version strings, and space complexity is also O(n) due to the split arrays. The method mainly relies on basic string processing.
Approach 2: Two-pointer Comparison Traversal (Time: O(n), Space: O(1))
This approach avoids splitting the strings entirely. Instead, traverse both version strings using two pointers. At each step, parse the next numeric segment by building the integer value until a dot or the end of the string appears. After extracting the numbers from both strings, compare them immediately. If one value is larger, return the result; otherwise continue scanning the next segment.
If one pointer reaches the end earlier, treat subsequent segments of the other version as integers and compare them against zero. This method processes characters directly and never allocates intermediate arrays. Time complexity remains O(n) since each character is visited once, but space complexity drops to O(1). The traversal pattern resembles classic two pointers techniques applied to sequential parsing.
Recommended for interviews: Start with the split-and-compare method to demonstrate the core idea clearly. Interviewers often accept it because the logic is straightforward and easy to verify. The two-pointer traversal is the stronger solution. It eliminates extra memory allocations and shows deeper control over string parsing and pointer movement. Candidates who implement the constant-space approach demonstrate stronger algorithmic thinking and familiarity with low-level string manipulation.
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.
C++
Java
Python
C#
JavaScript
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.
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.
C++
Java
Python
C#
JavaScript
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.
| Approach | Complexity |
|---|---|
| Split and Compare Each Component | Time Complexity: O(n + m), where n and m are lengths of version1 and version2 respectively. |
| Two-pointer Comparison Traversal | Time Complexity: O(n + m), where n and m are the lengths of version1 and version2. |
| 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 allocations or demonstrating pointer-based string parsing |
compare version numbers leetcode | leetcode 165 | string • Naresh Gupta • 12,209 views views
Watch 9 more video solutions →Practice Compare Version Numbers with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor