Compare Version Numbers (LeetCode 165) Explained | Brute Force to Optimal | C++

LeetCode 165, solved three ways — split into arrays, two-pointer substring extraction, and a single-pass digit scan — with intuition, C++ code, an animated dry run for each approach, and complexity analysis you can explain out loud.

1. Problem statement
2. Approach 1 — Brute force (split into arrays)
3. Approach 2 — Better (two pointers + substr)
4. Approach 3 — Optimal (single-pass digit scan)
5. Complexity comparison
6. Interview notes
7. FAQ

Problem Statement

Given two version strings version1 and version2, compare them revision by revision.

A revision's value is its integer conversion, ignoring leading zeros. If one version has fewer revisions, the missing ones count as 0. Return -1 if version1 < version2, 1 if version1 > version2, otherwise 0.

Example: version1 = "1.2", version2 = "1.10" → output -1, because the second revision 2 < 10 as integers (even though "2" looks bigger than "1" character by character).

To keep every approach grounded in the same example, we'll trace how each one compares "1.2" against "1.10" — once by building full token arrays, once by extracting one revision substring at a time, and once by parsing digits directly with no extra allocation at all.

Problem Statement

Given two version strings version1 and version2, compare them revision by revision.

A revision's value is its integer conversion, ignoring leading zeros. If one version has fewer revisions, the missing ones count as 0. Return -1 if version1 < version2, 1 if version1 > version2, otherwise 0.

Example: version1 = "1.2", version2 = "1.10" → output -1, because the second revision 2 < 10 as integers (even though "2" looks bigger than "1" character by character).

To keep every approach grounded in the same example, we'll trace how each one compares "1.2" against "1.10" — once by building full token arrays, once by extracting one revision substring at a time, and once by parsing digits directly with no extra allocation at all.

Approach 1 · Brute Force

Split Both Strings into Arrays, Then Compare

Intuition

The most direct translation of the problem statement: split each version string on '.' into a list of revision strings, pad the shorter list with "0"s so both lists have equal length, convert every entry to an integer, and compare position by position.

It works, and it's easy to reason about — but it fully materializes both revision lists in memory before comparing anything, even though you might only need to look at the very first revision to already know the answer.

Algorithm

1. Split version1 on '.' into a vector of strings; do the same for version2.
2. Let n be the larger of the two vector sizes; resize both vectors to length n, padding with "0".
3. Loop i from 0 to n - 1, converting both entries at index i to integers with stoi.
4. If the two integers differ, return -1 or 1 immediately.
5. If the loop finishes with no difference found, return 0.

C++ Code

vector<string> split(const string& s, char delim) {
    vector<string> tokens;
    string token;
    stringstream ss(s);
    while (getline(ss, token, delim)) {
        tokens.push_back(token);
    }
    return tokens;
}

int compareVersion(string version1, string version2) {
    vector<string> v1 = split(version1, '.');
    vector<string> v2 = split(version2, '.');

    int n = max(v1.size(), v2.size());
    v1.resize(n, "0");
    v2.resize(n, "0");

    for (int i = 0; i < n; i++) {
        int a = stoi(v1[i]);
        int b = stoi(v2[i]);
        if (a < b) return -1;
        if (a > b) return 1;
    }
    return 0;
}

Dry Run

Complexity Analysis

Approach 2 · Better

Two Pointers, One Revision at a Time

Intuition

You don't need every revision stored at once — you only need to compare them one pair at a time, stopping the moment they differ. Walk through both strings with two pointers, pull out just the current revision as a substring from each, compare, and only then move on to the next one.

Algorithm

1. Keep pointers i and j into version1 and version2, both starting at 0.
2. While either pointer still has characters left: extract the next revision from each string by scanning until a '.' or the end of the string.
3. If a string has been fully consumed, treat it

s revision as "0".

1. Convert both extracted revisions with stoi and compare; return immediately on a mismatch.
2. Advance both pointers past the '.' and repeat.

C++ Code

int compareVersion(string version1, string version2) {
    int i = 0, j = 0;
    int n = version1.size(), m = version2.size();

    while (i < n || j < m) {
        int start1 = i;
        while (i < n && version1[i] != '.') i++;
        string rev1 = (start1 < n) ? version1.substr(start1, i - start1) : "0";

        int start2 = j;
        while (j < m && version2[j] != '.') j++;
        string rev2 = (start2 < m) ? version2.substr(start2, j - start2) : "0";

        int a = rev1.empty() ? 0 : stoi(rev1);
        int b = rev2.empty() ? 0 : stoi(rev2);

        if (a != b) return a < b ? -1 : 1;

        i++; j++; // skip the '.'
    }
    return 0;
}

Dry Run

Complexity Analysis

Approach 3 · Optimal

Single Pass, No Substrings at All

Intuition

A revision's numeric value can be built up directly while scanning its digits — there's no real need to carve out a substring and hand it to stoi. Multiply the running total by 10 and add each digit as you go, exactly like manual long-hand integer parsing. This also handles leading zeros for free: "0" then "1" in "01" simply produces 0 → 1, the correct value.

Algorithm

1. Keep pointers i and j into version1 and version2, both starting at 0.
2. While either pointer still has characters left, accumulate revision a by reading digits from version1 until a '.' or the end.
3. Accumulate revision b the same way from version2.
4. Compare a and b directly as integers; return immediately on a mismatch.
5. Advance both pointers past the '.' and repeat; return 0 if the loop completes.

C++ Code

int compareVersion(string version1, string version2) {
    int i = 0, j = 0;
    int n = version1.size(), m = version2.size();

    while (i < n || j < m) {
        long a = 0, b = 0;

        while (i < n && version1[i] != '.') {
            a = a * 10 + (version1[i] - '0');
            i++;
        }
        while (j < m && version2[j] != '.') {
            b = b * 10 + (version2[j] - '0');
            j++;
        }

        if (a != b) return a < b ? -1 : 1;

        i++; j++; // skip the '.'
    }
    return 0;
}

Dry Run

Complexity Analysis

Interview Notes

How to talk through it

• Say out loud early that this is fundamentally a two-pointer problem disguised as string splitting — that framing alone signals strong pattern recognition.
• Write the split-based version first if it's the most natural to reason about, then proactively point out that it allocates memory for revisions it may never need to look at.
• Land on the digit-accumulation version as your final answer, and explain why it naturally ignores leading zeros without any special-casing.

Common follow-ups

• "What if a version has an empty revision, like `"1..2"`?" → clarify with the interviewer whether this is guaranteed not to happen per constraints; if it can, an empty revision should be treated as 0.
• "What if revisions could be arbitrarily long, overflowing an int?" → this is exactly why the optimal solution accumulates into a long rather than an int.
• "Can you do it without any extra pointers, using built-in split utilities?" → yes (Approach 1), but be ready to explain the extra memory tradeoff clearly.

Edge cases to mention

• Leading zeros in a revision, like "01" vs "1" — both must compare as equal.
• Unequal revision counts, like "1.0" vs "1.0.0.0" — missing revisions default to 0, so these are equal.
• Identical strings — the loop should terminate cleanly and return 0 without ever hitting a mismatch.
  

Frequently Asked Questions

How do you compare two version strings like "1.2" and "1.10"?

Split each into revisions separated by dots, convert each revision to its integer value ignoring leading zeros, and compare revisions left to right. Since 2 is numerically smaller than 10, "1.2" is less than "1.10".

Which approach should I lead with in an interview?

Mention the split-into-arrays idea briefly since it maps directly to the problem statement, but write the single-pass digit-accumulation version as your main solution — it's the one that best demonstrates two-pointer thinking and careful space management.

What happens if one version has fewer revisions than the other?

Any missing revision is treated as 0. "1.0" and "1.0.0.0" are equal because the extra trailing revisions of the second string are all zero.

Why not just compare the version strings directly without parsing?

Because revision lengths vary — comparing raw characters would incorrectly treat "2" as greater than "10", since string comparison looks at characters, not numeric value. Each revision must be converted to an integer first.