29. Compare Version Numbers

🔗 LeetCode Problem: 165. Compare Version Numbers
📊 Difficulty: Medium
🏷️ Topics: String, Two Pointers

Problem Statement

Given two version numbers, version1 and version2, compare them.

Version numbers consist of one or more revisions joined by a dot '.'. Each revision consists of digits and may contain leading zeros. Every revision contains at least one character. Revisions are 0-indexed from left to right, with the leftmost revision being revision 0, the next revision being revision 1, and so on.

To compare version numbers, compare their revisions in left-to-right order. Revisions are compared using their integer value ignoring any leading zeros. This means that revisions 1 and 001 are considered equal. If a version number does not specify a revision at an index, then treat the revision as 0.

Return the following: - If version1 < version2, return -1. - If version1 > version2, return 1. - Otherwise, return 0.

Example 1:

Input: version1 = "1.01", version2 = "1.001"
Output: 0
Explanation: Ignoring leading zeroes, both "01" and "001" represent the same integer 1.

Example 2:

Input: version1 = "1.0", version2 = "1.0.0"
Output: 0
Explanation: version1 does not specify revision 2, which means it is treated as "0".

Example 3:

Input: version1 = "0.1", version2 = "1.1"
Output: -1
Explanation: version1's revision 0 is "0", while version2's revision 0 is "1". 0 < 1, so version1 < version2.

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.

---

🎨 Visual Understanding

The Problem Visualized

Example: version1 = "1.2.3", version2 = "1.2.4"

Split by '.':
version1: [1, 2, 3]
version2: [1, 2, 4]

Compare revision by revision:
Index 0: 1 == 1 → Continue
Index 1: 2 == 2 → Continue
Index 2: 3 < 4  → version1 < version2

Return: -1

Handling Leading Zeros

version1 = "1.01"  → [1, 01]  → [1, 1]  (convert to int)
version2 = "1.001" → [1, 001] → [1, 1]  (convert to int)

After converting: Both are [1, 1]
Result: Equal → Return 0

Handling Different Lengths

version1 = "1.0"     → [1, 0]
version2 = "1.0.0.0" → [1, 0, 0, 0]

Compare:
Index 0: 1 == 1 → Continue
Index 1: 0 == 0 → Continue
Index 2: 0 (treated as 0) == 0 → Continue
Index 3: 0 (treated as 0) == 0 → Continue

All equal → Return 0

Key Rules

1. Leading zeros are ignored:
   "01" = "1" = "001"

2. Missing revisions are treated as 0:
   "1.0" = "1.0.0" = "1.0.0.0"

3. Compare integer values, not strings:
   "10" > "9" (not "10" < "9" lexicographically)

4. Compare left to right:
   Stop as soon as a difference is found

---

🎯 Approach 1: Split and Compare Arrays

The Most Natural Thinking 💭

Core Logic:

Split both version strings by '.' into arrays:
1. Split version1 by '.' → array1
2. Split version2 by '.' → array2
3. Compare elements one by one
4. Handle different lengths by treating missing as 0

Why This Works: - Easy to understand - String split is built-in - Can pad shorter array with zeros - Simple comparison logic

Why This Could Be Better: - Creates extra arrays (O(n) space) - Need to handle array length differences - Multiple passes through strings

Implementation

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

    int maxLen = Math.max(v1.length, v2.length);

    for (int i = 0; i < maxLen; i++) {
        // Get revision value, default to 0 if index out of bounds
        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;
        } else if (num1 > num2) {
            return 1;
        }
    }

    return 0;
}

⏰ Time: O(n + m) where n = length of version1, m = length of version2
💾 Space: O(n + m) - arrays created by split

---

✅ Approach 2: Two Pointers (Optimal)

The Breakthrough Insight 💡

Core Logic:

Use two pointers to parse versions without splitting:

1. Use two pointers (i for version1, j for version2)
2. Extract each revision on the fly
3. Compare revisions as we go
4. Handle different lengths naturally

Key insight: Parse numbers character by character
- Skip dots
- Build number digit by digit
- Compare when dot or end reached

Visual Explanation:

version1 = "1.2.3"
version2 = "1.2.4"

Round 1:
i=0: Parse "1" from version1
j=0: Parse "1" from version2
Compare: 1 == 1 → Continue
i=2, j=2 (after '.')

Round 2:
i=2: Parse "2" from version1
j=2: Parse "2" from version2
Compare: 2 == 2 → Continue
i=4, j=4 (after '.')

Round 3:
i=4: Parse "3" from version1
j=4: Parse "4" from version2
Compare: 3 < 4 → Return -1

Handling Leading Zeros:

version1 = "1.01"
           i

Start i=0:
Parse from i: '1' → num1 = 1
i moves to 2 (after '.')

Parse from i=2: '0' then '1' → num1 = 0*10 + 1 = 1
Leading zero naturally handled by multiplication

Implementation

public int compareVersion(String version1, String version2) {
    int n1 = version1.length();
    int n2 = version2.length();
    int i = 0, j = 0;

    while (i < n1 || j < n2) {
        // Parse next revision from version1
        int num1 = 0;
        while (i < n1 && version1.charAt(i) != '.') {
            num1 = num1 * 10 + (version1.charAt(i) - '0');
            i++;
        }

        // Parse next revision from version2
        int num2 = 0;
        while (j < n2 && version2.charAt(j) != '.') {
            num2 = num2 * 10 + (version2.charAt(j) - '0');
            j++;
        }

        // Compare current revisions
        if (num1 < num2) {
            return -1;
        } else if (num1 > num2) {
            return 1;
        }

        // Move past the '.' for next iteration
        i++;
        j++;
    }

    return 0;
}

⏰ Time: O(n + m) - single pass through both strings
💾 Space: O(1) - only a few variables

---

🔍 Step-by-Step Execution

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

Initial State:
═══════════════════════════════════════════════════════════════════
version1 = "1.01"
version2 = "1.001"
i = 0, j = 0


Round 1: Parse first revision
═══════════════════════════════════════════════════════════════════
Parse from version1 (i=0):
  char='1' → num1 = 0*10 + 1 = 1
  i=1, char='.' → Stop parsing
  Final: num1 = 1, i = 1

Parse from version2 (j=0):
  char='1' → num2 = 0*10 + 1 = 1
  j=1, char='.' → Stop parsing
  Final: num2 = 1, j = 1

Compare: num1=1, num2=1 → Equal
Move past '.': i=2, j=2


Round 2: Parse second revision
═══════════════════════════════════════════════════════════════════
Parse from version1 (i=2):
  char='0' → num1 = 0*10 + 0 = 0
  i=3
  char='1' → num1 = 0*10 + 1 = 1
  i=4, out of bounds → Stop parsing
  Final: num1 = 1, i = 4

Parse from version2 (j=2):
  char='0' → num2 = 0*10 + 0 = 0
  j=3
  char='0' → num2 = 0*10 + 0 = 0
  j=4
  char='1' → num2 = 0*10 + 1 = 1
  j=5, out of bounds → Stop parsing
  Final: num2 = 1, j = 5

Compare: num1=1, num2=1 → Equal
Move past '.': i=5, j=6


Round 3: Loop condition
═══════════════════════════════════════════════════════════════════
i=5 >= n1=4 AND j=6 >= n2=5
Loop terminates


═══════════════════════════════════════════════════════════════════
🎯 FINAL RESULT: 0 (versions are equal)
═══════════════════════════════════════════════════════════════════

Another Example: version1 = "1.0", version2 = "1.0.0"

Round 1: Parse "1" from both
num1 = 1, num2 = 1 → Equal
i=2, j=2

Round 2: Parse "0" from both
num1 = 0, num2 = 0 → Equal
i=3 (out of bounds), j=4

Round 3: Parse from version2 only
num1 = 0 (i out of bounds, default)
num2 = 0 (parsed from j=4)
Compare: 0 == 0 → Equal
i=4, j=6 (both out of bounds)

Result: 0 (equal)

Example: version1 = "0.1", version2 = "1.1"

Round 1:
num1 = 0 (parsed "0")
num2 = 1 (parsed "1")
Compare: 0 < 1

Return: -1

---

🔍 Edge Cases

Case 1: Equal versions with leading zeros
Input: version1 = "01", version2 = "1"
Output: 0
Explanation: 01 = 1

Case 2: Different lengths, same value
Input: version1 = "1.0", version2 = "1.0.0.0"
Output: 0
Explanation: Missing revisions treated as 0

Case 3: Single digit versions
Input: version1 = "1", version2 = "2"
Output: -1

Case 4: Many revisions
Input: version1 = "1.2.3.4.5", version2 = "1.2.3.4.6"
Output: -1

Case 5: All zeros
Input: version1 = "0.0.0", version2 = "0.0.0.0"
Output: 0

Case 6: Large numbers
Input: version1 = "1.2.1000", version2 = "1.2.999"
Output: 1
Explanation: 1000 > 999

Case 7: One very short, one very long
Input: version1 = "1", version2 = "1.0.0.0.0.0.0.1"
Output: -1
Explanation: Last revision differs

Case 8: Leading zeros with large numbers
Input: version1 = "1.0001", version2 = "1.1"
Output: 1
Explanation: 0001 = 1, but comparing gives 1 > 1 is false
Actually: 0001 = 1, so 1 == 1, equal at this level
Wait, let me recalculate: "1.0001" means revision [1, 0001] = [1, 1]
"1.1" means [1, 1]
So equal. Output: 0

---

Common Mistakes

Mistake 1: Lexicographic comparison instead of numeric
❌ Wrong: 
    String[] v1 = version1.split("\\.");
    if (v1[i].compareTo(v2[i]) < 0) return -1;
✓ Right: 
    int num1 = Integer.parseInt(v1[i]);
    int num2 = Integer.parseInt(v2[i]);
    if (num1 < num2) return -1;
Reason: "10" < "9" lexicographically, but 10 > 9 numerically

Mistake 2: Not handling leading zeros
❌ Wrong: 
    Treating "01" and "1" as different
✓ Right: 
    parseInt("01") = 1, parseInt("1") = 1
Reason: Integer parsing automatically handles leading zeros

Mistake 3: Not handling different lengths
❌ Wrong: 
    int maxLen = Math.min(v1.length, v2.length);
✓ Right: 
    int maxLen = Math.max(v1.length, v2.length);
Reason: Need to check all revisions, treating missing as 0

Mistake 4: Wrong split regex
❌ Wrong: 
    String[] v1 = version1.split(".");
✓ Right: 
    String[] v1 = version1.split("\\.");
Reason: '.' is regex metacharacter, needs escaping

Mistake 5: Not moving pointer past dot
❌ Wrong: 
    while (i < n1 && version1.charAt(i) != '.') {
        num1 = num1 * 10 + (version1.charAt(i) - '0');
        i++;
    }
    // Missing i++ to skip '.'
✓ Right: 
    // After parsing
    i++;  // Skip the '.'
Reason: Need to move past dot for next iteration

Mistake 6: Array index out of bounds
❌ Wrong: 
    for (int i = 0; i < v1.length; i++) {
        int num1 = Integer.parseInt(v1[i]);
        int num2 = Integer.parseInt(v2[i]);  // v2 might be shorter!
    }
✓ Right: 
    int num1 = i < v1.length ? Integer.parseInt(v1[i]) : 0;
    int num2 = i < v2.length ? Integer.parseInt(v2[i]) : 0;
Reason: Arrays might have different lengths

Mistake 7: Not returning 0 for equal versions
❌ Wrong: 
    // Missing return statement after loop
✓ Right: 
    return 0;  // After loop completes, versions are equal
Reason: If loop completes without returning, versions are equal

---

🎯 Key Takeaways

⚡ Algorithm Comparison

Approach 1: Split and Compare Arrays
  Time: O(n + m)
  Space: O(n + m)
  Use: Simple and readable, acceptable for interviews

Approach 2: Two Pointers (RECOMMENDED)
  Time: O(n + m)
  Space: O(1)
  Use: Optimal space, best for interviews

🔑 The Core Insight

Version Comparison Rules:
1. Split by '.' to get revisions
2. Compare revisions as INTEGERS (not strings)
3. Leading zeros are ignored (parseInt handles this)
4. Missing revisions treated as 0
5. Compare left to right until difference found

Two Pointers Strategy:
- Parse each revision on the fly
- Build number digit by digit: num = num * 10 + digit
- Compare when dot or end reached
- Handle different lengths naturally (default to 0)
- O(1) space vs O(n) for split approach

Key Formula:
num = num * 10 + (char - '0')

This naturally handles leading zeros:
"01" → 0*10 + 0 = 0, then 0*10 + 1 = 1

🎯 Pattern Recognition

Problem Type: String Parsing and Comparison
Core Pattern: Two Pointers for Parsing

When to Apply:
✓ Need to parse delimited strings
✓ Want to avoid extra space for arrays
✓ Compare values as you parse
✓ Handle variable-length inputs

Key Techniques:
→ Parse numbers character by character
→ Build number: num = num * 10 + digit
→ Skip delimiters
→ Handle end of string naturally
→ Treat missing values as default (0)

Related Problems:
- Valid Number (LC 65)
- Compare Strings by Frequency of Smallest Character (LC 1170)
- Version Control (system design)
- Semantic Versioning

🧠 Interview Strategy

Step 1: "Need to compare version numbers with special rules"
Step 2: "Parse by dots, compare as integers"
Step 3: "Leading zeros ignored, missing = 0"
Step 4: "Can use split or two pointers"
Step 5: "Two pointers for O(1) space"

Key Points to Mention:
- Integer comparison, not string comparison
- Leading zeros handled by parseInt
- Different lengths handled by treating missing as 0
- Two pointers approach saves space
- Stop as soon as difference found

---

📝 Quick Revision Notes

🎯 Core Concept:

Parse version strings by dots, compare revisions as integers (not strings). Leading zeros ignored, missing revisions treated as 0.

⚡ Quick Implementation (Two Pointers):

public int compareVersion(String version1, String version2) {
    // Few examples:
    // "1.01" == "1.001" => "1.1" == "1.1" (leading zeros are of no value)
    // "1.0" == "1.0.0" => "1.0.0" == "1.0.0" (consider 0 when no revision)
    // "1.0" == "1.0.0.0" => "1.0.0.0" == "1.0.0.0" (consider 0 when no revision)
    // "0.1" < "1.1"
    // "1.2.3" < "1.2.4"

    // // Approach 1 - using arrays
    // String[] v1 = version1.split("\\."); // 1.01 => [1, 01]
    // String[] v2 = version2.split("\\."); // 1.001 => [1, 001]
    // int len1 = v1.length;
    // int len2 = v2.length;

    // for(int i = 0; i < Math.max(len1, len2); i++) {
    //     int num1 = (i < len1) ? Integer.parseInt(v1[i]) : 0; // consider 0 when no value
    //     int num2 = (i < len2) ? Integer.parseInt(v2[i]) : 0; // consider 0 when no value

    //     if(num1 == num2) {
    //         continue;
    //     } else if(num1 < num2) {
    //         return -1;
    //     } else {
    //         return 1;
    //     }
    // }

    // Approach 2 - using 2 pointers
    int i = 0; // tracks version1
    int j = 0; // tracks version2
    int len1 = version1.length();
    int len2 = version2.length();

    while (i < len1 || j < len2) {
        // Track part by part of version (till .)
        // For example, in 1.23.115: 1, 23 and 115 will be extracted
        // and in 1.23.11: 1, 23 and 11 will be extracted.
        int num1 = 0;
        while (i < len1 && version1.charAt(i) != '.') {
            num1 = num1 * 10 + version1.charAt(i) - '0';
            i++;
        }

        int num2 = 0;
        while (j < len2 && version2.charAt(j) != '.') {
            num2 = num2 * 10 + version2.charAt(j) - '0';
            j++;
        }

        if(num1 == num2) {
            i++; // skip .
            j++; // skip .
            continue;
        } else if(num1 < num2) {
            return -1;
        } else {
            return 1;
        }
    }

    return 0;
}

🔑 Key Insights:

• Parse on the fly: Build numbers digit by digit
• Formula: num = num * 10 + (char - '0')
• Leading zeros: Automatically handled by formula (0*10 + 0 = 0)
• Skip dots: Move pointer past '.' after parsing
• Different lengths: Loop condition i < n1 || j < n2 handles both
• Missing revisions: Default to 0 when pointer out of bounds
• Stop early: Return as soon as difference found
• Time: O(n + m), Space: O(1)
• Split alternative: split("\\.") works but uses O(n) space

🎪 Memory Aid:

"Parse by DOT, compare as INT, missing is ZERO!"
Think: "Build number digit by digit: num = num*10 + digit"

---

Related Patterns

• Valid Number (LC 65)
• String to Integer (atoi) (LC 8)
• Restore IP Addresses (LC 93)
• Compare Strings by Frequency of Smallest Character (LC 1170)

---

Happy practicing! 🎯