Compare Version Numbers - Practice Coding Problems

Compare Version Numbers - Problem

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

Input & Output

Example 1 — Basic Comparison

$ Input: version1 = "1.01", version2 = "1.001"

› Output: 0

💡 Note: Both versions have revisions [1, 1] after removing leading zeros from "01" and "001", so they are equal

Example 2 — Missing Revision

$ Input: version1 = "1.0", version2 = "1.0.0"

› Output: 0

💡 Note: version1 has revisions [1, 0] and version2 has [1, 0, 0]. Missing revisions are treated as 0, so they are equal

Example 3 — Clear Difference

$ Input: version1 = "0.1", version2 = "1.1"

› Output: -1

💡 Note: First revision: 0 < 1, so version1 is smaller than 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

Visualization

Tap to expand

Understanding the Visualization

Input

Two version strings with dot-separated revisions

Parse

Extract and convert revisions to integers, ignoring leading zeros

Compare

Compare revisions left-to-right, treating missing as 0

Key Takeaway

🎯 Key Insight: Parse revisions numerically while handling leading zeros and missing parts

Asked in

Apple 15 M Microsoft 12 a Amazon 8

The key insight is to compare version strings by parsing revisions numerically while treating missing revisions as 0 and ignoring leading zeros. The optimal approach uses two pointers to parse revisions on-the-fly without extra space. Time: O(n + m), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Two Pointers Approach	O(n + m)	O(1)	Use two pointers to traverse both version strings simultaneously
Split and Pad Approach	O(n + m)	O(n + m)	Split both versions, pad shorter one with zeros, compare each revision

Two Pointers Approach — Algorithm Steps

Initialize two pointers at start of both strings
Extract current revision from each string
Compare current revisions numerically
Move pointers past current revision and dot
Repeat until both strings are fully processed

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set pointers to start of both strings

Parse

Extract current revision from each string

Compare

Compare extracted values and advance pointers

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(char* version1, char* version2) {
    int i = 0, j = 0;
    int n1 = strlen(version1), n2 = strlen(version2);
    
    while (i < n1 || j < n2) {
        // Extract current revision from version1
        int val1 = 0;
        while (i < n1 && version1[i] != '.') {
            val1 = val1 * 10 + (version1[i] - '0');
            i++;
        }
        i++; // Skip dot
        
        // Extract current revision from version2
        int val2 = 0;
        while (j < n2 && version2[j] != '.') {
            val2 = val2 * 10 + (version2[j] - '0');
            j++;
        }
        j++; // Skip dot
        
        // Compare current revisions
        if (val1 < val2) {
            return -1;
        } else if (val1 > val2) {
            return 1;
        }
    }
    
    return 0;
}

int main() {
    char version1[1000], version2[1000];
    
    fgets(version1, sizeof(version1), stdin);
    version1[strcspn(version1, "\n")] = 0;
    
    fgets(version2, sizeof(version2), stdin);
    version2[strcspn(version2, "\n")] = 0;
    
    int result = solution(version1, version2);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + m)

Single pass through both strings with pointer advancement

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables for pointers and current values

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two Pointers Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler