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.

Problem statement
Approach 1 — Brute force (split into arrays)
Approach 2 — Better (two pointers + substr)
Approach 3 — Optimal (single-pass digit scan)
Complexity comparison
Interview notes
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).

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

Split version1 on '.' into a vector of strings; do the same for version2.
Let n be the larger of the two vector sizes; resize both vectors to length n, padding with "0".
Loop i from 0 to n - 1, converting both entries at index i to integers with stoi.
If the two integers differ, return -1 or 1 immediately.
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

Metric	Value	Why
Time	O(n + m)	Each character is visited once during splitting, plus one pass to compare
Space	O(n + m)	Both full token vectors are stored, plus padding entries
Practical issue	Unnecessary upfront work	Every revision is extracted and stored even if the answer is decided at the first one

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

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

s revision as "0".

Convert both extracted revisions with stoi and compare; return immediately on a mismatch.
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

Metric	Value	Why
Time	O(n + m)	Each pointer moves forward only, one full pass across both strings combined
Space	O(k)	k = length of the current revision only, not the whole input
Improvement	No full token arrays	Can exit as soon as a mismatch is found, without preparing every revision first

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

Keep pointers i and j into version1 and version2, both starting at 0.
While either pointer still has characters left, accumulate revision a by reading digits from version1 until a '.' or the end.
Accumulate revision b the same way from version2.
Compare a and b directly as integers; return immediately on a mismatch.
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

Metric	Value	Why
Time	O(n + m)	Each character is visited exactly once across both strings
Space	O(1)	Only two accumulator variables and two pointers — no strings created
Why optimal	Zero string allocations	No split, substr, or stoi calls anywhere in the algorithm

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.

Problem Statement

Problem Statement

Approach 1 · Brute Force

Split Both Strings into Arrays, Then Compare

Intuition

Algorithm

C++ Code

Dry Run

Complexity Analysis

Approach 2 · Better

Two Pointers, One Revision at a Time

Intuition

Algorithm

C++ Code

Dry Run

Complexity Analysis

Single Pass, No Substrings at All

Intuition

Algorithm

C++ Code

Dry Run

Complexity Analysis

Interview Notes

How to talk through it

Common follow-ups

Edge cases to mention

Frequently Asked Questions

Chakradhar

Problem Statement

Problem Statement

Approach 1 · Brute Force

Split Both Strings into Arrays, Then Compare

Intuition

Algorithm

C++ Code

Dry Run

Complexity Analysis

Approach 2 · Better

Two Pointers, One Revision at a Time

Intuition

Algorithm

C++ Code

Dry Run

Complexity Analysis

Single Pass, No Substrings at All

Intuition

Algorithm

C++ Code

Dry Run

Complexity Analysis

Interview Notes

How to talk through it

Common follow-ups

Edge cases to mention

Frequently Asked Questions