_165. Compare Version Numbers.md

165. Compare Version Numbers

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : July 02, 2024

Last updated : July 02, 2024

---

Related Topics : Two Pointers, String

Acceptance Rate : 41.75 %

---

For both, we simply compare chunk by chunk to check if the values are equal integer-wise. If we run out, we simply iterate through the remainder of each pointer and see if it's equal to zero, or if we need to return +/- 1.

Version 2:

Runtime: $O(n)$ Space: $O(1)$

Compared to V2, the process is very similar. In this case, it updates it current indices one at a time to avoid having to use $O(n)$ storage to preprocess and avoids having to compute integer conversions when it's unnecessary (i.e. if the answer is solvable early in the strings length).

Version 1:

Runtime: $O(n)$ Space: $O(n)$

Splits both strings and parses them into integers first, extending the array itself by the missing zeros if necessary. This is still $O(1)$ but uses much more space than Version 2 and also can result in unnecessary processing from when the answer is determined early on in the comparisons.

---

Solutions

• m165 v1 Initial Splitting and Processing.py
• m165 v2 Progressive Pass.py
• m165 v2.c

Python

m165 v1 Initial Splitting and Processing.py

class Solution:
    def compareVersion(self, version1: str, version2: str) -> int:
        v1 = [int(x) for x in version1.split('.')]
        v2 = [int(x) for x in version2.split('.')]

        if len(v1) < len(v2) :
            v1.extend([0 for _ in range(len(v2) - len(v1))])
        elif len(v1) > len(v2) :
            v2.extend([0 for _ in range(len(v1) - len(v2))])

        for one, two in zip(v1, v2) :
            if one < two :
                return -1

            if two < one :
                return 1
            
        return 0

m165 v2 Progressive Pass.py

class Solution:
    def compareVersion(self, version1: str, version2: str) -> int:
        one, two = 0, 0

        while one < len(version1) and two < len(version2) :
            oneNew = version1.find('.', one)
            twoNew = version2.find('.', two)

            if oneNew < 0 :
                oneNew = len(version1)
            if twoNew < 0 :
                twoNew = len(version2)

            oneInt = int(version1[one:oneNew])
            twoInt = int(version2[two:twoNew])

            if oneInt < twoInt :
                return -1
            if twoInt < oneInt :
                return 1
            
            one = oneNew + 1
            two = twoNew + 1

        while one < len(version1) :
            oneNew = version1.find('.', one)
            if oneNew < 0 :
                oneNew = len(version1)
            oneInt = int(version1[one:oneNew])

            if oneInt < 0 :
                return -1
            if oneInt > 0 :
                return 1

            one = oneNew + 1

        while two < len(version2) :
            twoNew = version2.find('.', two)
            if twoNew < 0 :
                twoNew = len(version2)
            twoInt = int(version2[two:twoNew])

            if twoInt > 0 :
                return -1
            if twoInt < 0 :
                return 1

            two = twoNew + 1

        return 0

C

m165 v2.c

int compareVersion(char* version1, char* version2) {
    int one = 0;
    int two = 0;

    while (true) {
        int oneRight = one + 1;
        int twoRight = two + 1;
        while (version1[oneRight] && version1[oneRight] != '.') {
            oneRight++;
        }
        while (version2[twoRight] && version2[twoRight] != '.') {
            twoRight++;
        }

        int oneVal = 0;
        int twoVal = 0;
        for (int i = one; i < oneRight; i++) {
            oneVal = 10 * oneVal + (version1[i] - '0');
        }
        for (int i = two; i < twoRight; i++) {
            twoVal = 10 * twoVal+ (version2[i] - '0');
        }

        if (oneVal < twoVal) {
            return -1;
        }
        if (oneVal > twoVal) {
            return 1;
        }

        one = oneRight;
        two = twoRight;

        if (!version1[oneRight] && !version2[twoRight]) {
            break;
        }
        if (!version1[oneRight]) {
            two++;
            break;
        }
        if (!version2[twoRight]) {
            one++;
            break;
        }
        one++;
        two++;
    }

    // Finish off one
    while (version1[one]) {
        int oneRight = one + 1;
        while (version1[oneRight] && version1[oneRight] != '.') {
            oneRight++;
        }

        int oneVal = 0;
        for (int i = one; i < oneRight; i++) {
            oneVal = 10 * oneVal + (version1[i] - '0');
        }

        if (oneVal < 0) {
            return -1;
        }
        if (oneVal > 0) {
            return 1;
        }
        if (!version1[oneRight]) {
            break;
        }

        one = oneRight + 1;
    }


    // Finish off two
    while (version2[two]) {
        int twoRight = two + 1;
        while (version2[twoRight] && version2[twoRight] != '.') {
            twoRight++;
        }
        int twoVal = 0;
        for (int i = two; i < twoRight; i++) {
            twoVal = 10 * twoVal + (version2[i] - '0');
        }

        if (twoVal > 0) {
            return -1;
        }
        if (twoVal < 0) {
            return 1;
        }
        if (!version2[twoRight]) {
            break;
        }

        two = twoRight + 1;
    }

    return 0;
}