Compare Version Numbers
MedPrompt
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 <= 500version1andversion2only contain digits and'.'.version1andversion2are valid version numbers.- All the given revisions in
version1andversion2can be stored in a 32-bit integer.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves splitting the two version strings by the dot delimiter to get arrays of revision numbers. Then, it iterates through these arrays, comparing corresponding revision numbers. If one version has fewer revisions, they are treated as zeros.
Algorithm
- Split
version1string by.into an arrayv1Revisions. - Split
version2string by.into an arrayv2Revisions. - Find the maximum length between
v1Revisionsandv2Revisions, let's call itmaxLength. - Iterate from
i = 0tomaxLength - 1. - Get the
i-th revision forversion1. Ifiis out of bounds, the revision is0. Otherwise, parse the string revision to an integer. - Get the
i-th revision forversion2. Ifiis out of bounds, the revision is0. Otherwise, parse the string revision to an integer. - Compare the two integer revisions. If
rev1 < rev2, return-1. Ifrev1 > rev2, return1. - If the loop finishes, it means all revisions are equal. Return
0.
Walkthrough
The core idea is to break down the problem into simpler parts: splitting the strings, parsing the numbers, and then comparing them.
- First, we use the
splitmethod with the regular expression"\\."to divideversion1andversion2into arrays of strings, where each string represents a revision. - We then determine the maximum number of revisions between the two versions to set the boundary for our comparison loop.
- We iterate from the first revision (
i=0) up to the maximum length. In each iteration:- We retrieve the
i-th revision for both versions. Ifiexceeds the number of revisions for a version string, we treat its revision value as0. - We parse the string revisions into integers.
Integer.parseInt()conveniently handles any leading zeros. - We compare the two integer revision values. If they are not equal, we have found the result and can return
1or-1immediately.
- We retrieve the
- If the loop completes without returning, it means all revisions are equal (including the implicit trailing zeros), so we return
0.
class Solution { public int compareVersion(String version1, String version2) { String[] v1Revisions = version1.split("\\."); String[] v2Revisions = version2.split("\\."); int length1 = v1Revisions.length; int length2 = v2Revisions.length; int maxLength = Math.max(length1, length2); for (int i = 0; i < maxLength; i++) { int rev1 = (i < length1) ? Integer.parseInt(v1Revisions[i]) : 0; int rev2 = (i < length2) ? Integer.parseInt(v2Revisions[i]) : 0; if (rev1 < rev2) { return -1; } if (rev1 > rev2) { return 1; } } return 0; }}Complexity
Time
O(N + M)
Space
O(N + M)
Trade-offs
Pros
Conceptually simple and straightforward to implement.
Effectively uses built-in language features for string manipulation and parsing.
Cons
Requires extra memory to store the arrays of revision strings, which can be significant if the version strings are long.
This is a more optimized approach that avoids the overhead of splitting the strings and creating intermediate arrays. It uses two pointers to iterate through the version strings simultaneously, parsing the revision numbers on the fly and comparing them in a single pass.
Algorithm
- Initialize two pointers,
p1forversion1andp2forversion2, both to0. - Loop as long as
p1is less thanversion1's length orp2is less thanversion2's length. - Inside the loop, parse the next revision number from
version1starting atp1. Iterate fromp1until a.or the end of the string is found, calculating the integer value. Updatep1to the position after the parsed number. - Similarly, parse the next revision number from
version2starting atp2and updatep2. - Compare the two parsed revision numbers. If
rev1 > rev2, return1. Ifrev1 < rev2, return-1. - After comparison, advance both pointers by one to skip the
.character. - If the loop completes, return
0.
Walkthrough
This method processes both strings in one go, maintaining a pointer for each string to keep track of the current position.
- We initialize two pointers,
p1andp2, to the start ofversion1andversion2. - The main loop continues as long as we haven't reached the end of both strings (
p1 < n1orp2 < n2). - Inside the loop, for each version string, we have a nested loop that reads characters until a dot
.is encountered or the end of the string is reached. While reading, we construct the integer value of the current revision. For example, for "123", we dorev = 0 * 10 + 1, thenrev = 1 * 10 + 2, thenrev = 12 * 10 + 3. - After parsing a revision number from each string (or
0if one pointer is already at the end), we compare them. - If
rev1 > rev2, we return1. Ifrev1 < rev2, we return-1. - If they are equal, we advance both main pointers (
p1andp2) past the dot to start parsing the next revision in the next iteration. - If the main loop completes, it means all revisions were equal, and we return
0.
class Solution { public int compareVersion(String version1, String version2) { int p1 = 0, p2 = 0; int n1 = version1.length(), n2 = version2.length(); while (p1 < n1 || p2 < n2) { int rev1 = 0; while (p1 < n1 && version1.charAt(p1) != '.') { rev1 = rev1 * 10 + (version1.charAt(p1) - '0'); p1++; } int rev2 = 0; while (p2 < n2 && version2.charAt(p2) != '.') { rev2 = rev2 * 10 + (version2.charAt(p2) - '0'); p2++; } if (rev1 > rev2) { return 1; } else if (rev1 < rev2) { return -1; } // Move past the dot p1++; p2++; } return 0; }}Complexity
Time
O(N + M)
Space
O(1)
Trade-offs
Pros
Highly efficient in terms of memory usage, as it operates in constant extra space.
Processes the strings in a single pass, which can be faster in practice by avoiding the overhead of creating intermediate data structures.
Cons
The implementation logic is slightly more complex than the split-and-parse approach due to manual parsing and pointer management.
Solutions
Solution
public class Solution { public int CompareVersion(string version1, string version2) { int m = version1.Length, n = version2.Length; for (int i = 0, j = 0; i < m || j < n; ++i, ++j) { int a = 0, b = 0; while (i < m && version1[i] != '.') { a = a * 10 + (version1[i++] - '0'); } while (j < n && version2[j] != '.') { b = b * 10 + (version2[j++] - '0'); } if (a != b) { return a < b ? -1 : 1; } } return 0; }}class Solution {public int compareVersion(String version1, String version2) { int m = version1.length(), n = version2.length(); for (int i = 0, j = 0; i < m || j < n; ++i, ++j) { int a = 0, b = 0; while (i < m && version1.charAt(i) != '.') { a = a * 10 + (version1.charAt(i++) - '0'); } while (j < n && version2.charAt(j) != '.') { b = b * 10 + (version2.charAt(j++) - '0'); } if (a != b) { return a < b ? -1 : 1; } } return 0; }}class Solution {public: int compareVersion(string version1, string version2) { int m = version1.size(), n = version2.size(); for (int i = 0, j = 0; i < m || j < n; ++i, ++j) { int a = 0, b = 0; while (i < m && version1[i] != '.') { a = a * 10 + (version1[i++] - '0'); } while (j < n && version2[j] != '.') { b = b * 10 + (version2[j++] - '0'); } if (a != b) { return a < b ? -1 : 1; } } return 0; }};class Solution: def compareVersion(self, version1: str, version2: str) -> int: m, n = len(version1), len(version2) i = j = 0 while i < m or j < n: a = b = 0 while i < m and version1[i] != '.': a = a * 10 + int(version1[i]) i += 1 while j < n and version2[j] != '.': b = b * 10 + int(version2[j]) j += 1 if a != b: return - 1 if a < b else 1 i, j = i + 1, j + 1 return 0Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.