165. Compare Version Numbers

MediumTwo PointersString
Leetcode Link

Problem Description

The challenge is to compare two version numbers, version1 and version2. A version number is a sequence of numbers separated by dots, with each number called a revision. The task is to compare the version numbers revision by revision, starting from the left (the first revision is revision 0, the next is revision 1, etc.).

Revision comparison is done based on the integer value of each revision, without considering any leading zeros. If a revision is missing in one of the version numbers, it should be treated as 0. Based on the comparison, if version1 is less than version2, we return -1; if version1 is greater than version2, we return 1; and if both version numbers are the same, we return 0.

This problem requires careful parsing of the string that represents each version number and a clear understanding of how version numbers are structured and compared.

Intuition

The intuition behind the solution is to simulate the way we compare version numbers in a real-world scenario. We start by comparing the first revision of each version. If they are equal, we proceed to the next one; if not, we determine the result based on which one is greater.

Translating this into code, we iterate through both string representations of the version numbers version1 and version2 simultaneously. Using two pointers, i for version1 and j for version2, we process each revision separately. We consider the end of a revision to be either the end of the string or the character '.'.

For each revision, we parse the number, skipping any leading zeroes, by multiplying the current value by 10 and adding the next digit. Once we have the integer values a and b for the current revisions of version1 and version2, respectively, we compare these values.

If we find a difference between a and b, we return -1 if a is smaller; otherwise, we return 1. If a and b are equal, we move on to the next revision. If we reach the end of both strings without finding any differences, we return 0.

The solution ensures that we only compare integer values of revisions and handles cases where the versions have a different number of revisions by treating missing revisions as 0.

Learn more about Two Pointers patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which data structure is used to implement priority queue?

Solution Approach

The implementation of the solution employs a straightforward parsing technique to compare version numbers. Here's a step-by-step walk-through:

  1. Initialize pointers and lengths: Start with defining two pointers, i and j, for iterating over version1 and version2 respectively. Also, determine the lengths of the two versions, m and n.

  2. Iterate over the version strings: Use a while loop to continue the iteration as long as either i < m or j < n. This is done to handle scenarios where one version string is longer than the other.

  3. Parse revisions: Parse the current revision for both versions. This is done in two nested while loops, one for each version. A temporary variable (say a for version1 and b for version2) is set to 0. For each digit encountered that is not a dot, multiply the current value of a or b by 10 and add the integer value of the current character. This effectively strips leading zeros and converts the string to an integer. Increments the appropriate pointer, i or j, when a digit is read.

  4. Compare revisions: Once both revisions are extracted, compare these integer values. If they are not equal, decide the return value based on which one is less. Return -1 if the integer from version1 (a) is less than the integer from version2 (b), and return 1 if it's the other way around.

  5. Move to the next revision: Increment the pointers i and j to skip the dot and proceed to the next revision.

  6. Return 0 if no differences are found: If the loop concludes without returning -1 or 1, this means all revisions were equal or non-specified revisions were implicitly treated as 0. Hence, return 0.

The algorithm avoids the use of additional storage or complex data structures, opting for a simple linear parsing approach. It leverages the properties of integer arithmetic to process revisions, and pointer arithmetic to move through the version strings. Additionally, by treating non-specified revisions as 0, the algorithm cleverly simplifies the case handling for version numbers with a different number of revisions.

The use of while-loops and conditional logic is quite efficient, ensuring that each character in the version strings is processed exactly once, giving the algorithm a time complexity of O(max(N, M)), where N and M are the lengths of the version strings. There is no reliance on additional significant space, making the space complexity O(1).

This approach to breaking down the problem, iterating through each character, and avoiding unnecessary complexity is a hallmark of many string parsing problems. By focusing on one revision at a time, the solution achieves a balance between clarity and efficiency.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?

Example Walkthrough

Let's walk through a small example to illustrate how the solution approach works. We will compare two version numbers:

version1: "1.02"
version2: "1.2.1"

As per the given solution approach:

  1. Initialize pointers and lengths:
    We set i = 0, j = 0, m = length of "1.02" = 4, and n = length of "1.2.1" = 5.

  2. Iterate over the version strings:
    We start a while loop where i < m or j < n; in this case, 0 < 4 or 0 < 5 is true.

  3. Parse revisions:
    We begin by parsing the first revision of each:

    • For version1, we parse until we encounter a dot. We skip the leading zero, and a = 1.
    • For version2, we do the same and get b = 1.
      The pointers now point to the dots, so i = 2 and j = 2.

  4. Compare revisions:

    • Since a (1) == b (1), we move forward.

  5. Move to the next revision:

    • We increment i and j to skip the dot, so i = 3 and j = 3.

  6. Parse and compare the next revisions:

    • For version1, there is no dot until the end, so parse the next number, getting a = 2.
    • For version2, we get b = 2 after parsing until the next dot at j = 4.
    • The comparison shows a (2) == b (2), so we move forward.

  7. Move to the next revision:

    • Increment i and j to skip the dots. i is now m (end of version1), but j = 5 is still within version2.

  8. Parse remaining revisions:

    • Since i has reached the end, a remains 0.
    • For version2, b is parsed as b = 1.

  9. Final comparison and result:

    • The next comparison is between a (0) and b (1). Since a is less, according to our rule, we return -1.

Therefore, for the example given version1: "1.02" and version2: "1.2.1", the result of our version number comparison would be -1, indicating that version1 is less than version2.

Solution Implementation

1class Solution:
2    def compareVersion(self, version1: str, version2: str) -> int:
3        # Length of the version strings
4        len_version1, len_version2 = len(version1), len(version2)
5      
6        # Initialize pointers for each version string
7        pointer1 = pointer2 = 0
8      
9        # Loop until the end of the longest version string is reached
10        while pointer1 < len_version1 or pointer2 < len_version2:
11            # Initialize numeric values of the current version parts
12            num1 = num2 = 0
13          
14            # Parse the version number from version1 until a dot is found or end is reached
15            while pointer1 < len_version1 and version1[pointer1] != '.':
16                num1 = num1 * 10 + int(version1[pointer1])
17                pointer1 += 1
18              
19            # Parse the version number from version2 until a dot is found or end is reached
20            while pointer2 < len_version2 and version2[pointer2] != '.':
21                num2 = num2 * 10 + int(version2[pointer2])
22                pointer2 += 1
23              
24            # Compare the parsed numbers
25            if num1 != num2:
26                # If they are not equal, determine which one is larger and return -1 or 1 accordingly
27                return -1 if num1 < num2 else 1
28          
29            # Move past the dot for the next iteration
30            pointer1, pointer2 = pointer1 + 1, pointer2 + 1
31      
32        # If no differences were found, the versions are equal
33        return 0
34
1class Solution {
2    public int compareVersion(String version1, String version2) {
3        int length1 = version1.length(), length2 = version2.length(); // Store the lengths of the version strings
4      
5        // Initialize two pointers for traversing the strings
6        for (int i = 0, j = 0; (i < length1) || (j < length2); ++i, ++j) {
7            int chunkVersion1 = 0, chunkVersion2 = 0; // Initialize version number chunks
8          
9            // Compute the whole chunk for version1 until a dot is encountered or the end of the string
10            while (i < length1 && version1.charAt(i) != '.') {
11                // Update the chunk by multiplying by 10 (moving one decimal place)
12                // and adding the integer value of the current character 
13                chunkVersion1 = chunkVersion1 * 10 + (version1.charAt(i) - '0');
14                i++; // Move to the next character
15            }
16          
17            // Compute the whole chunk for version2 until a dot is encountered or the end of the string
18            while (j < length2 && version2.charAt(j) != '.') {
19                chunkVersion2 = chunkVersion2 * 10 + (version2.charAt(j) - '0');
20                j++; // Move to the next character
21            }
22          
23            // Compare the extracted chunks from version1 and version2
24            if (chunkVersion1 != chunkVersion2) {
25                // Return -1 if chunkVersion1 is smaller, 1 if larger
26                return chunkVersion1 < chunkVersion2 ? -1 : 1;
27            }
28            // If chunks are equal, proceed to the next set of chunks
29        }
30        // If all chunks have been successfully compared and are equal, return 0
31        return 0;
32    }
33}
34
1#include <string> // Include necessary header
2
3class Solution {
4public:
5    // Compares two version numbers 'version1' and 'version2'
6    int compareVersion(std::string version1, std::string version2) {
7        int v1Length = version1.size(), v2Length = version2.size(); // Store the sizes of both version strings
8
9        // Iterate over both version strings
10        for (int i = 0, j = 0; i < v1Length || j < v2Length; ++i, ++j) {
11            int num1 = 0, num2 = 0; // Initialize version segment numbers for comparison
12
13            // Parse the next version segment from 'version1'
14            while (i < v1Length && version1[i] != '.') {
15                num1 = num1 * 10 + (version1[i] - '0'); // Convert char to int and accumulate
16                ++i; // Move to the next character
17            }
18
19            // Parse the next version segment from 'version2'
20            while (j < v2Length && version2[j] != '.') {
21                num2 = num2 * 10 + (version2[j] - '0'); // Convert char to int and accumulate
22                ++j; // Move to the next character
23            }
24
25            // Compare the parsed version segments
26            if (num1 != num2) {
27                return num1 < num2 ? -1 : 1; // Return -1 if 'version1' is smaller, 1 if larger
28            }
29        }
30
31        // If we get to this point, the versions are equal
32        return 0;
33    }
34};
35
1function compareVersion(version1: string, version2: string): number {
2    // Split both version strings by the dot (.) to compare them segment by segment.
3    let versionArray1: string[] = version1.split('.'),
4        versionArray2: string[] = version2.split('.');
5
6    // Iterate through the segments for the maximum length of both version arrays.
7    for (let i = 0; i < Math.max(versionArray1.length, versionArray2.length); i++) {
8        // Convert the current segment of each version to a number,
9        // using 0 as the default value if the segment is undefined.
10        let segment1: number = Number(versionArray1[i] || 0),
11            segment2: number = Number(versionArray2[i] || 0);
12
13        // If the current segment of version1 is greater than version2, return 1.
14        if (segment1 > segment2) return 1;
15
16        // If the current segment of version1 is less than version2, return -1.
17        if (segment1 < segment2) return -1;
18    }
19
20    // If all segments are equal, return 0.
21    return 0;
22}
23
Not Sure What to Study? Take the 2-min Quiz：

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Time and Space Complexity

The time complexity of the given code can be considered to be O(max(M, N)), where M is the length of version1 and N is the length of version2. This is because the code uses two while loops that iterate through each character of both version1 and version2 at most once. The inner while loops, which convert the version numbers from string to integer, contribute to the same overall time complexity because they iterate through each subsection of the versions delimited by the period character '.', still not exceeding the total length of the versions.

The space complexity of the code is O(1), since it only uses a fixed number of integer variables and does not allocate any variable-sized data structures dependent on the size of the input.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

Recommended Readings

Tech Interview Pattern | Two Pointers Introduction

Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers iframe width 560 height 315 src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe Two pointers is a common interview technique

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫