Compare version numbers

Problem Statement

Given two version strings:

version1

version2

Enter fullscreen mode Exit fullscreen mode

Each version consists of revisions separated by dots (.).

Compare the two versions.

Return:

1  → version1 > version2

-1 → version1 < version2

0  → Both are equal

Enter fullscreen mode Exit fullscreen mode

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;
    }
}

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

Convert that revision into an integer.

Compare corresponding revisions.

Optimal Approach

Maintain two pointers:

i → version1

j → version2

Enter fullscreen mode Exit fullscreen mode

Extract one revision from both strings.

Compare:

num1

vs

num2

Enter fullscreen mode Exit fullscreen mode

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;
    }
}

Enter fullscreen mode Exit fullscreen mode

Dry Run

Input

version1 = "1.01"

version2 = "1.001"

Enter fullscreen mode Exit fullscreen mode

Compare:

1

=

1

Enter fullscreen mode Exit fullscreen mode

Next Revision:

01

=

001

↓

1

=

1

Enter fullscreen mode Exit fullscreen mode

Answer:

0

Enter fullscreen mode Exit fullscreen mode

Example 2

version1 = "1.0"

version2 = "1.0.1"

Enter fullscreen mode Exit fullscreen mode

Compare:

1 = 1

0 = 0

0 < 1

Enter fullscreen mode Exit fullscreen mode

Answer:

-1

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

Mental Model

1.0.23

↓

1

↓

0

↓

23

↓

Compare One by One

Enter fullscreen mode Exit fullscreen mode

Whenever you hear:

“Compare version strings”

your brain should immediately think:

Two Pointers + Parse Each Revision