Log inSign up
mediumLeetCodeNot Started

Compare Version Numbers

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on LeetCode
Lesson

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. For example 2.5.33 and 0.1 are valid version numbers.

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`. For example, version 1.0 is less than version 1.1 because their revision 0s are the same, but their revision 1s are 0 and 1 respectively, and 0 < 1.

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

Example 1 · Example:

Input: version1 = "1.2", version2 = "1.10"
Output: -1
Explanation: version1's revision 0 is "1", version2's revision 0 is "1". Revision 1s are "2" and "10" respectively. 2 < 10, so version1 < version2.

Example 2 · Example:

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

Example 3 · Example:

Input: version1 = "1.0", version2 = "1.0.0.0"
Output: 0
Explanation: Missing revisions default to 0. Both represent 1.0.0.0.

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.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the core string patterns underlying Compare Version Numbers.
  • Optimize time and space tradeoffs for string manipulation.
  • Handle string boundary conditions and unicode/ASCII edge cases.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Comparing multi-segment version or dotted identifier strings.
  • Need to normalize numeric tokens with variable leading zeros.

Algorithmic Decision Tree:

  • Two Pointers In-Place Chunk Accumulator
  • Delimiter-Delimited Segment Comparison

Connected Patterns:

String to Integer (atoi)Add StringsMultiply Strings

1. String Split by Dot and Integer Array Comparison

Intuition

1. Split version1 by "\." to get array v1. 2. Split version2 by "\." to get array v2. 3. Loop k from 0 to max(v1.length, v2.length): - num1 = k < v1.length ? Integer.parseInt(v1[k]) : 0 - num2 = k < v2.length ? Integer.parseInt(v2[k]) : 0 - If num1 != num2, return num1 < num2 ? -1 : 1 4. Return 0 if all revisions match.

When to apply: Quick solution using language string split utilities.

Algorithm

  1. Split strings by dot separator.
  2. Iterate up to max chunk count.
  3. Parse chunks to integer, defaulting missing chunks to 0.
  4. Return -1, 1, or 0 based on comparison.

String Split by Dot and Integer Array Comparison

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, ., 0, 1, |, 1, ., 0, 0, 1]
Current operationSTEP 1 OF 6
Observation: Split both version strings on
Visual state
Values and pointers at this exact step
array
S
1
.
0
1
|
1
.
0
0
1
0
↑ v1[0]
1
2
3
4
5
↑ v2[0]
6
7
8
9
Variables at this step
chunkIndex
0
v1Chunk
1
v2Chunk
1
v1Val
1
v2Val
1
diff
0
Check / comparison
Split v1 -> ['1', '01']. Split v2 -> ['1', '001'].
Decision / next transition
Parse first chunk: parseInt('1') = 1, parseInt('1') = 1. Compare 1 == 1.
Why this step matters

Observation: Split both version strings on . into token arrays: v1 = ['1', '01'] and v2 = ['1', '001'].

Decision: Parse index 0 tokens to integers: 1 vs 1. Difference is 0.

Invariant: Leading zeros are naturally discarded by integer conversion (01 -> 1).

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <sstream>
5
6class Solution {
7public:
8 int compareVersion(std::string version1, std::string version2) {
9 std::vector<int> v1, v2;
10 std::string token;
11
12 std::stringstream ss1(version1);
13 while (std::getline(ss1, token, '.')) {
14 v1.push_back(std::stoi(token));
15 }
16
17 std::stringstream ss2(version2);
18 while (std::getline(ss2, token, '.')) {
19 v2.push_back(std::stoi(token));
20 }
21
22 int n = std::max(v1.size(), v2.size());
23 for (int i = 0; i < n; ++i) {
24 int num1 = (i < v1.size()) ? v1[i] : 0;
25 int num2 = (i < v2.size()) ? v2[i] : 0;
26 if (num1 < num2) return -1;
27 if (num1 > num2) return 1;
28 }
29 return 0;
30 }
31};
32
33int main() {
34 Solution sol;
35 std::cout << sol.compareVersion("1.2", "1.10") << std::endl; // -1
36 std::cout << sol.compareVersion("1.01", "1.001") << std::endl; // 0
37 std::cout << sol.compareVersion("1.0", "1.0.0.0") << std::endl; // 0
38 return 0;
39}

Time & Space Complexity

  • Time complexity: O(N + M) — Splitting and parsing takes linear time in the combined length of the version strings.
  • Space complexity: O(N + M)

Why Brute Force Doesn't Scale:

Naive brute force re-examines already processed substrings multiple times.

For N = 105, O(N2) requires 1010 operations (TLE), while O(N) finishes in < 10ms.

2. Stream / Helper Function Chunk Extraction

Intuition

1. Maintain indices p1 = 0 and p2 = 0. 2. Write helper getNextChunk(str, startIndex) returning { value, nextIndex }. 3. Compare values on the fly. 4. Stop early as soon as a mismatch is detected.

When to apply: When optimizing memory usage over full array splitting.

Algorithm

  1. Iteratively extract next revision integers.
  2. Compare integers on the fly.
  3. Return early on first mismatch.

Stream / Helper Function Chunk Extraction

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, ., 0, 1, |, 1, ., 0, 0, 1]
Current operationSTEP 1 OF 6
Observation: Initialize helper reader for version1
Visual state
Values and pointers at this exact step
array
S
1
.
0
1
|
1
.
0
0
1
0
↑ STREAM 1
1
2
3
4
5
6
7
8
9
Variables at this step
stream1Chunk
1
ptr1
1
Check / comparison
Helper getNextChunk(version1, idx1) parses until dot.
Decision / next transition
Accumulate chars until '.' or end. Chunk 1 = 1.
Why this step matters

Observation: Initialize helper reader for version1. Scan until first delimiter ..

Decision: Token '1' extracted; advance stream pointer past ..

Invariant: Helper generator yields chunks on-demand without bulk memory pre-allocation.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3
4class Solution {
5public:
6 int compareVersion(std::string version1, std::string version2) {
7 int i = 0, j = 0;
8 int n1 = version1.size(), n2 = version2.size();
9
10 while (i < n1 || j < n2) {
11 long long num1 = 0;
12 while (i < n1 && version1[i] != '.') {
13 num1 = num1 * 10 + (version1[i] - '0');
14 i++;
15 }
16
17 long long num2 = 0;
18 while (j < n2 && version2[j] != '.') {
19 num2 = num2 * 10 + (version2[j] - '0');
20 j++;
21 }
22
23 if (num1 < num2) return -1;
24 if (num1 > num2) return 1;
25
26 i++; // skip __SF_TOKEN_A__
27 j++; // skip __SF_TOKEN_A__
28 }
29 return 0;
30 }
31};
32
33int main() {
34 Solution sol;
35 std::cout << sol.compareVersion("1.2", "1.10") << std::endl;
36 return 0;
37}

Time & Space Complexity

  • Time complexity: O(max(N, M)) — Scans each character of both strings once.
  • Space complexity: O(1) auxiliary

3. Two-Pointer In-Place Chunk Accumulator

Intuition

1. Initialize pointer i = 0 for version1 and j = 0 for version2. 2. While i < version1.length || j < version2.length: - Accumulate num1: while i < len && version1[i] != '.', num1 = num1 * 10 + (version1[i++] - '0') - Accumulate num2: while j < len && version2[j] != '.', num2 = num2 * 10 + (version2[j++] - '0') - If num1 < num2, return -1 - If num1 > num2, return 1 - Advance past dot: i++, j++ 3. Return 0 if all revisions are identical.

When to apply: The definitive, optimal industry solution for version comparison (no allocations, early exit).

Algorithm

  1. Initialize two pointers i = 0, j = 0.
  2. Accumulate integer values of current revision chunks.
  3. Compare revision integers.
  4. Advance pointers past the dot delimiters.
  5. Return comparison result.

Dot-Delimited Numerical Chunk Comparison

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [chunk_1, chunk_2]
Current operationSTEP 1 OF 6
Observation: Parse first dot-delimited revision: version1 has "1", version2 has "1"
Visual state
Values and pointers at this exact step
array
S
1
01
0
↑ Chunk 0: "1" vs "1"
1
Variables at this step
chunkIndex
0
rawV1
1
rawV2
1
num1
1
num2
1
cmp
0
Why this step matters

Observation: Parse first dot-delimited revision: version1 has "1", version2 has "1".

Decision: Convert both to integers: 1 === 1. Chunk comparison yields 0 (equal).

Invariant: Pointers advance to the next revision segment.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3
4class Solution {
5public:
6 int compareVersion(std::string version1, std::string version2) {
7 int i = 0, j = 0;
8 int n1 = version1.size(), n2 = version2.size();
9
10 while (i < n1 || j < n2) {
11 long long num1 = 0;
12 while (i < n1 && version1[i] != '.') {
13 num1 = num1 * 10 + (version1[i] - '0');
14 i++;
15 }
16
17 long long num2 = 0;
18 while (j < n2 && version2[j] != '.') {
19 num2 = num2 * 10 + (version2[j] - '0');
20 j++;
21 }
22
23 if (num1 < num2) return -1;
24 if (num1 > num2) return 1;
25
26 i++; // skip __SF_TOKEN_A__
27 j++; // skip __SF_TOKEN_A__
28 }
29
30 return 0;
31 }
32};
33
34int main() {
35 Solution sol;
36 std::cout << sol.compareVersion("1.2", "1.10") << std::endl; // Output: -1
37 std::cout << sol.compareVersion("1.01", "1.001") << std::endl; // Output: 0
38 std::cout << sol.compareVersion("1.0", "1.0.0.0") << std::endl; // Output: 0
39 return 0;
40}

Time & Space Complexity

  • Time complexity: O(max(N, M)) — Each character in version1 and version2 is visited exactly once.
  • Space complexity: O(1) auxiliary

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.String Split by Dot and Integer Array ComparisonO(N + M)O(N + M)Split both version strings by . into string arrays, parse individual components into integer arrays, pad the shorter array with zeros, and compare element-wise.Time / space complexity limits.
2.Stream / Helper Function Chunk ExtractionO(max(N, M))O(1) auxiliaryUse a helper function with sliding boundaries to extract next integer tokens without pre-splitting the entire string into memory.Time / space complexity limits.
3.Two-Pointer In-Place Chunk AccumulatorOptimalO(max(N, M))O(1) auxiliaryTraverse both strings with two pointers simultaneously. Accumulate numeric values between dots in-place with O(1) space and return early on the first non-equal revision.Time / space complexity limits.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Treating missing revisions as non-matching instead of defaulting to integer 0 (e.g. "1.0" vs "1.0.0").

Pitfall 2:

Comparing string values lexicographically rather than numerically (lexicographically "2" > "10", but numerically 2 < 10).

Pitfall 3:

Failing to advance pointers past the . delimiter, causing infinite loops.

Crucial Edge Cases to Validate:

  • Empty string or single character string.
  • String with duplicate or repeating characters.
  • Strings with different lengths or extreme character bounds.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clarify character constraints (lowercase English only vs full Unicode/ASCII).
  2. Explain your choice of data structure (array frequency map vs hash table) before coding.
  3. Walk through a concrete small example during the dry run.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time complexity for Compare Version Numbers?

Back to DSA Sheet