Compare Version Numbers

Problem

Compare two version numbers version1 and version2. If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0. You may assume that the version strings are non-empty and contain only digits and the . character. The . character does not represent a decimal point and is used to separate number sequences. Here is an example of version numbers ordering:

0.1 < 1.1 < 1.2 < 13.37

Examples

Example 1:

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

Example 2:

Input: version1 = "1.0", version2 = "1.0.0"
Output: 0
Explanation: version1 does not specify revision 2, which means it is treated as "0".

Example 3:

Input: version1 = "0.1", version2 = "1.1"
Output: -1
Explanation: version1's revision 0 is "0", while version2's revision 0 is "1". 0 < 1, so version1 < version2.

Solution

The tricky part of the problem is to handle cases like 1.0 and 1. They should be equal.

Method 1a - Iterative using split and compact

On way is to split the array, and then compare 1 part of version with another.

Intuition

• Version strings are sequences of integer components separated by .. Compare components from left to right; missing components are treated as 0.

Approach

• Split both strings on . to get arrays of numeric tokens.
• Iterate up to the maximum number of tokens; parse each token to an integer or treat it as 0 if missing.
• Return -1/1 as soon as a mismatch is found; otherwise return 0.

Video explanation

Here is the video explaining this method in detail. Please check it out:

<div class="youtube-embed"><iframe src="https://www.youtube.com/embed/RIItUM-2Ypg" frameborder="0" allowfullscreen></iframe></div>

Code

Java

class Solution {
	public int compareVersion(String version1, String version2) {
		String[] v1 = version1.split("\\.");
		String[] v2 = version2.split("\\.");
		int maxParts = Math.max(v1.length, v2.length);
		for (int i = 0; i < maxParts; 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;
	}
}

Python

class Solution:
	def compareVersion(self, version1: str, version2: str) -> int:
		v1 = version1.split('.')
		v2 = version2.split('.')
		max_parts = max(len(v1), len(v2))
		for i in range(max_parts):
			n1 = int(v1[i]) if i < len(v1) else 0
			n2 = int(v2[i]) if i < len(v2) else 0
			if n1 < n2:
				return -1
			if n1 > n2:
				return 1
		return 0

Complexity

• ⏰ Time complexity: O(N) — we split both strings and parse each numeric token once; N is the total length of the input strings.
• 🧺 Space complexity: O(L) — splitting creates token arrays (L = total number of components across both versions).

Method 1b - Iterative using split and two-pointers based

This variant also uses split, but advances a pointer over the token arrays and handles missing parts explicitly; useful when you prefer an explicit loop over for.

Intuition

• Same idea as 1a: compare numeric components left-to-right, treating missing parts as 0. Using pointers over split arrays emphasizes step-by-step token comparison and early exits.

Approach

• Split both versions into token arrays. Use a single index to traverse both arrays.
• At each step parse available tokens to integers (or 0 if missing) and compare.
• If one side has extra non-zero tokens, it is greater.

Code

Java

class Solution {
	public int compareVersion(String version1, String version2) {
		String[] arr1 = version1.split("\\.");
		String[] arr2 = version2.split("\\.");

		int i = 0;

		while (i < arr1.length || i < arr2.length) {
			int n1 = i < arr1.length ? Integer.parseInt(arr1[i]) : 0;
			int n2 = i < arr2.length ? Integer.parseInt(arr2[i]) : 0;
			if (n1 < n2) return -1;
			if (n1 > n2) return 1;
			i++;
		}

		return 0;
	}
}

Python

class Solution:
	def compareVersion(self, version1: str, version2: str) -> int:
		arr1 = version1.split('.')
		arr2 = version2.split('.')
		i = 0
		while i < len(arr1) or i < len(arr2):
			n1 = int(arr1[i]) if i < len(arr1) else 0
			n2 = int(arr2[i]) if i < len(arr2) else 0
			if n1 < n2:
				return -1
			if n1 > n2:
				return 1
			i += 1
		return 0

Complexity

• ⏰ Time complexity: O(N) — splitting and parsing each component once; N is the combined input length.
• 🧺 Space complexity: O(L) — token arrays from split (L = number of components).

Method 2 - Iterative solution using StringTokenizer

Intuition

• Tokenizers stream the numeric components one by one and are convenient when you want to avoid creating full arrays of tokens; the algorithm remains a left-to-right numeric comparison.

Approach

• Use a tokenizer (or iterator) for both version strings, parse tokens pairwise and compare.
• If one tokenizer finishes earlier, check remaining tokens on the other side — any non-zero remaining component makes that version larger.

Code

Java

class Solution {
	public int compareVersion(String version1, String version2) {
		StringTokenizer st1 = new StringTokenizer(version1, ".");
		StringTokenizer st2 = new StringTokenizer(version2, ".");
		while (st1.hasMoreTokens() && st2.hasMoreTokens()) {
			int token1 = Integer.parseInt(st1.nextToken());
			int token2 = Integer.parseInt(st2.nextToken());
			if (token1 > token2) {
				return 1;
			} else if (token2 > token1) {
				return -1;
			}
		}
		boolean left = st1.countTokens() > st2.countTokens();
		StringTokenizer remaining = left ? st1: st2;

		while (remaining.hasMoreTokens()){
			if (Integer.parseInt(remaining.nextToken()) > 0) {
				return left ? 1 : -1;
			}
		}

		return 0;
	}
}

Python

class Solution:
	def compareVersion(self, version1: str, version2: str) -> int:
		# iterate through tokens by index; splitting once for simplicity
		a = version1.split('.')
		b = version2.split('.')
		i = 0
		while i < len(a) and i < len(b):
			n1 = int(a[i])
			n2 = int(b[i])
			if n1 < n2:
				return -1
			if n1 > n2:
				return 1
			i += 1

		# check remaining tokens on either side
		while i < len(a):
			if int(a[i]) > 0:
				return 1
			i += 1
		while i < len(b):
			if int(b[i]) > 0:
				return -1
			i += 1

		return 0

Complexity

• ⏰ Time complexity: O(N) — processes each token once; N denotes total input length.
• 🧺 Space complexity: O(1) additional — uses iterators/single-pass checks and only constant extra storage (apart from the input tokens when using split, but no large auxiliary structures).