Problem Statement
Given two version strings:
version1
version2
Each version consists of revisions separated by dots (.).
Compare the two versions.
Return:
1 → version1 > version2
-1 → version1 < version2
0 → Both are equal
Leading zeros should be ignored.
Brute Force Intuition
In an interview, you can explain it like this:
Split both version strings using
".", convert each revision to an integer, and compare corresponding revisions one by one.
If one version has fewer revisions, treat the missing revisions as 0.
Complexity
- Time Complexity: O(N + M)
- Space Complexity: O(N + M)
Brute Force Code
class Solution {
public int compareVersion(String version1,
String version2) {
String[] v1 = version1.split("\\.");
String[] v2 = version2.split("\\.");
int n = Math.max(v1.length, v2.length);
for (int i = 0; i < n; 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;
}
}
Moving Towards the Optimal Approach
Instead of creating arrays using split(),
we can process both strings directly.
Traverse both strings simultaneously,
extract one revision at a time,
and compare immediately.
This avoids creating extra arrays.
Pattern Recognition
Whenever you see:
- Dot Separated Values
- Version Strings
- Sequential Comparison
Think:
Two Pointers + String Parsing
Key Observation
Every revision is simply a number.
Read characters until:
'.'
or
End of String
Convert that revision into an integer.
Compare corresponding revisions.
Optimal Approach
Maintain two pointers:
i → version1
j → version2
Extract one revision from both strings.
Compare:
num1
vs
num2
If equal,
move to the next revision.
Optimal Java Solution
class Solution {
public int compareVersion(String version1,
String version2) {
int i = 0;
int j = 0;
while (i < version1.length() ||
j < version2.length()) {
int num1 = 0;
while (i < version1.length() &&
version1.charAt(i) != '.') {
num1 = num1 * 10
+ (version1.charAt(i) - '0');
i++;
}
int num2 = 0;
while (j < version2.length() &&
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;
}
}
Dry Run
Input
version1 = "1.01"
version2 = "1.001"
Compare:
1
=
1
Next Revision:
01
=
001
↓
1
=
1
Answer:
0
Example 2
version1 = "1.0"
version2 = "1.0.1"
Compare:
1 = 1
0 = 0
0 < 1
Answer:
-1
Why This Works?
Each revision is processed exactly once.
Instead of storing all revisions,
we compare them as soon as they are parsed.
Missing revisions are naturally treated as:
0
because the extracted value remains zero when one version ends.
Complexity Analysis
| Metric | Complexity |
|---|---|
| Time Complexity | O(N + M) |
| Space Complexity | O(1) |
Where:
N = version1.length()M = version2.length()
Interview One-Liner
Traverse both version strings simultaneously, parse one revision at a time using two pointers, and compare corresponding revision numbers without splitting the strings.
Pattern Learned
Delimited String
↓
Parse Number
↓
Compare
↓
Move Forward
Similar Problems
- Compare Version Numbers
- String to Integer (ATOI)
- Roman to Integer
- Basic Calculator
- Valid Number
Memory Trick
Think:
Read Revision
↓
Convert to Number
↓
Compare
↓
Next Revision
Mental Model
1.0.23
↓
1
↓
0
↓
23
↓
Compare One by One
Whenever you hear:
"Compare version strings"
your brain should immediately think:
Two Pointers + Parse Each Revision
SOCIAL SHARE CARD GENERATOR