Hello Ninjas!!, I have a question for you. Have you ever encountered different versions of any product out there? Have you noticed the pattern all the version numbers follow? A dot usually separates them (â€ś.â€ť). The digits after the dot (â€ś.â€ť), are called revisions of the version.

Here, we shall discuss how to compare the two version numbers of any product and help our users get the latest version.

Problem Statement

More formally, we are given two numbers or versions of the same product, and we must determine which version number is the latest. If both are the same, return any version as the answer. Examples of version numbers are 1.0.1 and 1.0.0.1.

Each number after a dot is called a revision, containing at least one character. They are compared using their integer value. Trailing zeroes are to be ignored while comparing.

E.g. Version number 1.0.1 has two revisions, namely 0 and 1.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Input/Output Format

Input format: Two Strings depicting the two version numbers of the product to compare.

Output format: The name of the version which is latest.

Example 1

Given two versions of the product, v1 and v2. Compare the two versions, and return the latest version.

Input:

v1 = â€ś1.0.1â€ť
v2 = "1.1"

Output:

v2

Explanation:

Here we shall be comparing the strings by their revisions. A number between every two dots is a particular revision, so weâ€™ll compare each revision of the two versions.

v1 has three revisions, 1, 0, and 1.

v2 has two revisions, 1 and 1.

Now on comparing each revision of the two versions:

Revision 1: The first revisions of the two versions are 1 and 1. Since they are the same, we move forward

Revision 2: The second revisions of the two versions are 0 and 1. Since 1 > 0, we return v2 as the answer and stop further iterations.

Example 2

Given two versions of the product, v1 and v2. Compare the two versions, and return the latest version.

Input:

v1 = â€ś1.0â€ť
v2 = â€ś1.0.0â€ť

Output:

v1

Note: v2 is also correct, as v2 is the same as v1.

Explanation:

Here also, we shall be comparing the strings by their revisions. A number between every two dots is a particular revision, so weâ€™ll compare each revision of the two versions.

v1 has three revisions, 1, 0, and 0.

v2 has two revisions, 1 and 0.

Now on comparing each revision of the two versions:

Revision 1: The first revisions of the two versions are 1 and 1. Since they are the same, we move forward

Revision 2: The second revisions of the two versions are 0 and 0. Since they are also the same, so we move forward

Note: Here, v1 has only two revisions, whereas v2 has three revisions. So to compare them, we take v1 as three revisions, with the last revision being 0.

So now v1 becomes â€ś1.0.0â€ť, and v2 is â€ś1.0.0â€ť; since they are the same, we return any of the two strings as the answer.

Approach

We will be following the two-pointer approach to solving this problem. We will isolate each revision from the version number separately and compare the corresponding revision with the other string. Here are the steps which we will be following to compare the revisions

Algorithm

Isolate the revisions: Separate all the revisions of the version number. For this, we will be constructing a list/array of strings; each element represents a revision number.

E.g., Consider the string v1=â€ť1.0.1â€ť

So we will be splitting the string into a list of 3 elements, each element representing the revision number

So our list becomes

v1 = [â€ś1â€ť,â€ť0â€ť,â€ť1â€ť]

Similarly, we will be creating a list/array of elements of v2="1.1"

We get

v2 = [â€ś1â€ť,â€ť1â€ť]

Converting the datatypes: Now, we will convert all list elements to integers. This will help us in removing the trailing zeroes, as well as an easy comparison between the two numbers.

Two pointers: Now, for comparing the corresponding values from the two arrays, we have to make the two arrays of the same length. So we will be padding the shorter array with zeroes to make its length as same as the other one.

Now that we have two arrays of the same length, we take two pointers, i and j, where i traverse the string v1 and j traverse the string v2.

Now we compare the corresponding values of the two pointers

v1 [ i ] == v2 [ j ]

If the corresponding value is equal, then we move forward. Once we encounter a value greater than the other, we stop the iteration and return the answer.

Dry Run

Letâ€™s see the above approach with an example, to understand better.

Example

Consider these two versions of the product, v1 and v2.

v1 = â€ś1.0.1â€ť

v2 = â€ś1.1â€ť

Step 1: We will be isolating the revisions from the version number.

Letâ€™s make the array with revisions as elements.

Step 2: Convert the elements into integer datatype.

If any element had trailing zeroes, converting the string to an integer also helps remove those.

Step 3: Make the length of the two arrays equal.

We had the shorter array with zeroes to make them equal.

Step 4: Now take two pointers, i and j, where I point to v1 and j points to v2.

And start comparing the corresponding values.

So we increment both i and j

Since we get v2_arr > v1_arr, we return v2 as our answer.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
/*
function to split string to array of strings.
via a seperator
*/
vector<string> split_into_revisions(string version) {
vector<string> split_arr;
string str;
// stringstream object referencing version string
stringstream ss(version);
/*
checking the getline() function condition.
" . " acts as seperator
*/
while (getline(ss, str, '.'))
split_arr.push_back(str);
// returns the array of revisions
return split_arr;
}
int main() {
// input
string version1 = "1.0.1";
string version2 = "1.1";
// split the strings into vector of revisions
vector<string> v1 = split_into_revisions(version1);
vector<string> v2 = split_into_revisions(version2);
// length of padding to insert
int high = v2.size();
int low = v1.size();
int diff = abs(high - low);
// vector to pad with 0 (zeroes)
if (v1.size() > v2.size()) {
for (int i = 0; i < diff; i++) {
v2.push_back("0");
}
}
else {
for (int i = 0; i < diff; i++) {
v1.push_back("0");
}
}
vector<int> val1, val2;
for (int i = 0; i < v1.size(); i++)
val1.push_back(stoi(v1[i]));
for (int i = 0; i < v2.size(); i++)
val2.push_back(stoi(v2[i]));
// two pointer to compare the corresponding indices
int i = 0;
int j = 0;
// if the versions are same, then return any version
string ans = "Version 1";
while (i < val1.size() and j < val2.size()) {
if (val1[i] > val2[j]) {
ans = "Version 1";
break;
}
else if (val1[i] < val2[j]) {
ans = "Version 2";
break;
}
i++;
j++;
}
// returns the string
cout << ans << endl;
return 0;
}

Output

Implementation in Java

class Main {
public static void main(String args[]) {
// input
String version1 = "1.0.1";
String version2 = "1.1";
// spliting the strings into revisions
String v1[] = version1.split("\\.");
String v2[] = version2.split("\\.");
// padding the array with extra '0'
int max_len = Math.max(v1.length, v2.length);
int val1[] = new int[max_len];
int val2[] = new int[max_len];
for (int i = 0; i < v1.length; i++)
val1[i] = Integer.parseInt(v1[i]);
for (int i = 0; i < v2.length; i++)
val2[i] = Integer.parseInt(v2[i]);
// comparing the two pointers side by side
for (int i = 0; i < max_len; i++) {
if (val1[i] > val2[i]) {
System.out.println("Version 1");
return;
}
if (val1[i] < val2[i]) {
System.out.println("Version 2");
return;
}
}
System.out.println("Version 1");
return;
}
}

Output

Implementation in Python

def get_revision_list(version: str) -> list:
# gets the list of revisions of version
return version.split(".")
def increase_length(array: list, low: int, high: int) -> list:
# increases the length of list
# appends/pads the array with 0 (zeroes)
array.extend(["0"] * abs(high - low))
return array
def compare_version(version1: str, version2: str) -> str:
# function to compare the two versions
v1, v2 = get_revision_list(version1), get_revision_list(version2)
v1 = increase_length(v1, len(v1), len(v2))
v2 = increase_length(v2, len(v1), len(v2))
# type-casting the revisions from string to int
v1, v2 = map(lambda char: int(char), v1), map(lambda char: int(char), v2)
# traversing the two versions simultanously (two-pointer)
for n1, n2 in zip(v1, v2):
if n1 > n2:
return "Version 1"
elif n1 < n2:
return "Version 2"
return "Version 1"
# driver code
version1 = "1.0.1"
version2 = "1.1"
print(compare_version(version1, version2))

Output

Complexity Analysis

So letâ€™s discuss the complexity analysis of the implementation above.

Time Complexity: Since we are traversing two arrays, and in the worst case, if both arrays are the same, we must traverse the entire array. So our time complexity reaches O(max(v1,v2)), or if n denotes the length of the longer array, our worst-case time complexity goes O(n).

Space complexity: Since we are creating an array of revisions of the version number. So our space complexity reaches the order O(max(number of revisions in v1, number of revisions in v2)). So, if n denotes the maximum number of revisions among the two arrays, our space complexity reaches O(n).

How to compare two arrays according to their values?

We take two pointers, i and j, pointing to two arrays. Next, we compare the corresponding values and move the two pointers forward. If one of the values is greater than the other at any instant, we get the larger array (according to the value).

How to change the datatype / typecast datatype of all the elements in the array?

We can use a map or transform (in the case of C++), to solve this problem. It takes a function as an argument, which gets applied to all the elements of the iterable.

So to convert a list of strings to a list of integers, we use a map, with the function taking char as a parameter and returning its integer typecase. So the values get converted into integers.

How to split a string into an array of elements?

Many languages support the inbuilt function called split, which takes a character as a parameter and is applied over a string. It returns an array of strings, separated by the separation character taken as a parameter.

How to join an array of strings to one string?

For joining the list of strings, we take an empty string. Then we iterate over the array and concatenate the elements into the empty string. On reaching the end, we got one string formed from an array of strings. Many languages have an inbuilt join function for this functionality.

How to handle the case when one pointer reaches the end of an array while the other doesnâ€™t?

We either pad the array with any integer/empty strings to make its length equal to the other array and then compare the corresponding values. Or we could have two while loops, one traversing the common size of both and the other traversing the extra length.

So, Ninjas, I hope you can now quickly determine the latest version of any product.

In this article, we learned how to compare two product versions to determine which is the latest. We follow the two-pointer approach for the same.

We hope this has helped you to increase your understanding of Two Pointers and how to check if two arrays of strings/characters are the same. If you want to learn more about such topics, do read more of our articles

If you want to study more about Two Pointers and practice the questions that require you to take your basic knowledge on these topics a bit higher, you can visit our Guided Path for DSA on Coding Ninjas Studio.To be more confident in data structures and algorithms, try out our DS and Algo Courses. Until then, All the best for your future endeavors, and Keep Coding.