Get relative path from to/from path Is there a better way to optimize this code? It started with \$O(n^2)\$ (nested loops) then \$O(n)\$ (with index).

public static String getRelativePath(String from, String to) {
    String relative = "";
    String regexPath = "/";
    String regexLow = "..";

    List&lt;String&gt; toList = Arrays.asList(to.split(regexPath));
    List&lt;String&gt; fromList = Arrays.asList(from.split(regexPath));

    int toSize = toList.size();
    int fromSize = fromList.size();

    relative += regexPath;

    for(int index = 0; index &lt; fromSize; index++) {
        if(index &lt;= toSize-1) {
            String toValue = toList.get(index);
            String fromValue = fromList.get(index);

            if(toValue.equals(fromValue)) {
                relative += regexLow + regexPath;
            }
            else
                relative += fromValue + regexPath;
        }
        else {
            if(index != fromSize-1)
                relative += fromList.get(index) + regexPath;
            else
                relative += fromList.get(index);
        }
    }

    return relative;
}


Inputs:


  fromPath -> "/a/b/c" toPath -> "/a/b/d/f"


Output:


  relativePath -> "/../../d/f
Performance-wise, yes, you can optimize it by going character-by-character through the input looking for / characters, such as below. It's weakly tested, and I wouldn't ever consider it in a whiteboard interview. This runs an order of magnitude faster than your method on my old laptop.

public static String getRelativePathMessy(final String from, final String to) {
    final int lastIndex = Math.min(from.length(), to.length());
    int index = 0;
    while ((index &lt; lastIndex) &amp;&amp; (from.charAt(index) == to.charAt(index))) {
        index += 1;
    }

    final StringBuilder relativePath = new StringBuilder();
    int fromIndex = from.lastIndexOf(PATH_SEPARATOR, index);
    while (fromIndex &gt; 0) {
        relativePath.append("../");
        fromIndex = from.indexOf(PATH_SEPARATOR, fromIndex + 1);
    }

    if (index &lt; lastIndex) {
        final String toPath = to.substring(to.lastIndexOf(PATH_SEPARATOR, index) + 1);
        relativePath.append(toPath);
    }
    return relativePath.toString();
}


Readability-wise, yes you can optimize it. This is marginally faster than your implementation, probably because it avoids the unnecessary use of Lists. I would argue it's a lot easer to understand what's going on. Why? Fewer branches, especially nested ones, and better names. 

public static String getRelativePathNeat(final String from, final String to) {
    final String[] fromPathElements = from.split(PATH_SEPARATOR);
    final String[] toPathElements = to.split(PATH_SEPARATOR);

    final int firstDifferentPathIndex = findFirstDifferentPathIndex(fromPathElements, toPathElements);

    final StringBuilder relativePath = new StringBuilder();
    for (int i = firstDifferentPathIndex; i &lt; fromPathElements.length; i++) {
        relativePath.append("..");
        relativePath.append(PATH_SEPARATOR);
    }

    for (int i = firstDifferentPathIndex; i &lt; toPathElements.length; i++) {
        relativePath.append(toPathElements[i]);
        relativePath.append(PATH_SEPARATOR);
    }
    relativePath.delete(relativePath.length() - 1, relativePath.length());

    return relativePath.toString();
}

private static int findFirstDifferentPathIndex(final String[] fromPathElements, final String[] toPathElements) {
    final int maxIndex = Math.min(fromPathElements.length, toPathElements.length);
    int arrayIndex = 0;
    while ((arrayIndex &lt; maxIndex) &amp;&amp; fromPathElements[arrayIndex].equals(toPathElements[arrayIndex])) {
        arrayIndex += 1;
    }

    return arrayIndex;
}