Leetcode: Largest Number

Question

I was trying out leetcode's Largest Number.
As per the challenge's description:

Given a list of non-negative integers nums, arrange them such that they form the largest number and return it. Since the result may be very large, so you need to return a string instead of an integer.

Example 1:
Input: nums = [10,2]
Output: "210"

Example 2:
Input: nums = [3,30,34,5,9]
Output: "9534330"

Constraints:
1 <= nums.length <= 100
0 <= nums[i] <= \$10^9\$

Here is my solution:

class Solution {
  // custom comparator: comparing integers as strings
  // to decide which to place before the other.
  static class SortByFirstDigit implements Comparator<Integer> {
    @Override
    public int compare(Integer i1, Integer i2) {
        String a = Integer.toString(i1);
        String b = Integer.toString(i2);
        //compare integers as strings to know which will be picked up ie 'ab' and 'ba' for example
        return Integer.compare(0, (a + b).compareTo(b + a));
    }
  }

  // REF: Convert int[] to Integer[]
  // function toConvertInteger is taken from stackoverflow at:
  // https://stackoverflow.com/a/31967630/1063062
  public static Integer[] toConvertInteger(int[] ids) {
    Integer[] newArray = new Integer[ids.length];
    for (int i = 0; i < ids.length; i++) {
        newArray[i] = Integer.valueOf(ids[i]);
    }
    return newArray;
  }

  public String largestNumber(int[] nums) {
    Integer[] Nums = toConvertInteger(nums);
    Arrays.sort(Nums, new SortByFirstDigit());

    StringBuilder builder = new StringBuilder();
    for (int s : Nums) builder.append(s);
    
    //if we get a string of all zeros, strip to 1 zero.
    if (builder.toString().matches("^[0]+$")) return "0";
    
    return builder.toString();
   }
}

Question

• This code passes all test but runs in around 9ms. What part(s) of the code are making it slow? and how to make it faster?
• Or, is it better to solve this problem in other ways (ie more performant) like for example using a N-ary tree for example? While analyzing the problem I had at some point thought of a tree algorithm which I will explain graphically in this picture:

It will traverse from leafs to parents following:

concatenate(parent key + greater integer nodes (ie greater than parent)) ---> parent integer value --> concatenate (parent key + smaller integer nodes (ie smaller than parent))

ie in this example 9 5 34 3 30

Answer 1

Let's pretend that the purpose of LeetCode is to train for the real world. In the real world,

• you wouldn't call this class Solution;
• you would want to write your own tests;
• you would want to write your own benchmarks (I do not demonstrate this);
• largestNumber should be static; and
• once the performance is "good enough" for your application, move on rather than fussing with micro-optimisation.

To the last point: I (mostly) like your current approach, with some asterisks.

SortByFirstDigit is a lie, since it doesn't sort by the first digit only; I propose something like ByDigits with an explanatory comment.

Delete toConvertInteger and use a simple chain of stream operations. The stream will also obviate your use of a builder.

Don't toString() in the comparator; front-load this to a mapping operation that occurs prior to the sort.

Don't Integer.compare(0; you can use String.compare directly.

The comparator should be a final on the class, rather than being instantiated in the method. Same for the zero-trim regex.

The zero-trim regex should not put 0 in a character class; you can use the character directly.

Suggested

LexConcatenator.java

import java.util.Arrays;
import java.util.Comparator;
import java.util.regex.Pattern;
import java.util.stream.Collectors;

public class LexConcatenator {
    private static final Pattern allZero = Pattern.compile("^0+$");
    private static final ByDigits comp = new ByDigits();

    private static final class ByDigits implements Comparator<String> {
        // Compare string representations of integers to know which order produces the larger value when concatenated
        @Override
        public int compare(String i1, String i2) {
            // Use string-lexicographic comparison instead of parsing integers
            // and comparing those, because lex comparison can short-circuit
            return (i2 + i1).compareTo(i1 + i2);
        }
    }

    public static String largestNumber(int[] nums) {
        // nums is assumed positive.

        String s = Arrays.stream(nums)
            // Mark the stream as unordered to allow some optimisations
            // https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/stream/package-summary.html#Ordering
            .unordered()
            .parallel()
            .mapToObj(Integer::toString)
            .sorted(comp)
            .collect(Collectors.joining());

        if (allZero.matcher(s).matches())
            return "0";
        return s;
    }
}

LexConcatenatorTests.java

import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertEquals;

public class LexConcatenatorTests {
    private static void compare(String expected, int... values) {
        String actual = LexConcatenator.largestNumber(values);
        assertEquals(expected, actual);
    }

    @Test
    void basic() {
        compare("0", 0);
        compare("1", 1);
        compare("10", 0, 1);
        compare("10", 1, 0);
        compare("100", 1, 0, 0);
        compare("111", 1, 1, 1);
    }

    @Test
    void zeroTrim() {
        compare("0", 0, 0);
        compare("0", 0, 0, 0);
        compare("0", 0, 0, 0, 0);
    }

    @Test
    void orders() {
        compare("908070", 70, 80, 90);
        compare("900000", 9, 0, 0, 0, 0, 0);
        compare("9111", 9, 111);
        compare("991000", 99, 1000);
        compare("54321", 1, 2, 3, 4, 5);
        compare("43210", 0, 1, 2, 3, 4);
    }

    @Test
    void overflow() {
        // would overflow a uint64, though impl is just an int32
        compare("18999001001001001001", 1_899_900_100, 1_001_001_001);
    }
}