algoadvance

Leetcode 165. Compare Version Numbers

Problem Statement

The task is to compare two version numbers, version1 and version2.

Each version number is composed of one or more revisions joined by a dot (.). Each revision consists of digits and may contain leading zeros. Each version can have multiple revisions.

Compare the versions and return:

For example:

Clarifying Questions

  1. Are the versions always valid and well-formed?
    • Yes, versions will be well-formed as described.
  2. What is the length range of the version strings?
    • Each version string length will be within reasonable limits for comparison.
  3. Is it safe to assume that versions with extra trailing zeros are equal to versions without those zeros (like 1.0 and 1.0.0)?
    • Yes, trailing zeros should not affect the comparison result.

Strategy

  1. Split the version strings: Using the split("\\.") method in Java to break the version strings into their individual numeric components.
  2. Normalize lengths: Compare corresponding components; if lengths differ, components beyond the shorter version are treated as zeros.
  3. Integer comparison: Convert each component to an integer and compare them sequentially from left to right.
  4. Return the appropriate comparison result based on the first non-equal pair of version components.

Code

public class CompareVersionNumbers {
    public int compareVersion(String version1, String version2) {
        String[] v1Parts = version1.split("\\.");
        String[] v2Parts = version2.split("\\.");
        
        int length = Math.max(v1Parts.length, v2Parts.length);
        
        for (int i = 0; i < length; i++) {
            int v1Component = i < v1Parts.length ? Integer.parseInt(v1Parts[i]) : 0;
            int v2Component = i < v2Parts.length ? Integer.parseInt(v2Parts[i]) : 0;
            
            if (v1Component > v2Component) {
                return 1;
            } else if (v1Component < v2Component) {
                return -1;
            }
        }
        
        return 0;
    }
    
    public static void main(String[] args) {
        CompareVersionNumbers comparator = new CompareVersionNumbers();
        
        System.out.println(comparator.compareVersion("1.01", "1.001")); // Output: 0
        System.out.println(comparator.compareVersion("1.0", "1.0.0"));  // Output: 0
        System.out.println(comparator.compareVersion("0.1", "1.1"));    // Output: -1
    }
}

Time Complexity

The time complexity of this solution is O(max(N, M)), where N and M are the lengths of the version strings when split by .. This ensures that we linearly compare each component pair and, therefore, achieve efficient comparison.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI