5
\$\begingroup\$

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: enter image description here

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

\$\endgroup\$
4
  • 2
    \$\begingroup\$ You do not take into account that the input numbers are not necessarily unique. You are essentially submitting for review your data structure for the algorithm and the data stucture is not ready. Also, the question about the traversal algorithm is better suited at stackoverflow.com. \$\endgroup\$ Commented Apr 4 at 11:09
  • 1
    \$\begingroup\$ Wouldn't a simple sort of the input strings offer a way to immediately read out the solution? Short strings (e.g. "9") sorting before long ones (e.g. "91") helps us quickly find the answer. The example highlights "2" > "10". \$\endgroup\$
    – J_H
    Commented Apr 4 at 17:03
  • 3
    \$\begingroup\$ @J_H no see example 2, you have 3 34 and 30. In the output 34 is before 3, and 30 is after 3 ie 34330. \$\endgroup\$
    – ccot
    Commented Apr 5 at 12:44
  • \$\begingroup\$ @TorbenPutkonen Could you indicate an example where the calculation is incorrect? If not could you remove your comment? \$\endgroup\$ Commented Apr 7 at 14:46

1 Answer 1

6
\$\begingroup\$

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);
    }
}
\$\endgroup\$
11
  • \$\begingroup\$ (Don't Integer.compare(0, ‹comparison›(a, b)): do ‹comparison›(b, a) instead.) \$\endgroup\$
    – greybeard
    Commented Apr 7 at 15:35
  • \$\begingroup\$ I was writing a similar answer. One thing that I would indicate (which is kinda hidden in your example solution) is to convert to string early. There is no need to keep operating in the realm of integers if the solution is entirely based on decimal digits represented as strings. If you're performing the change in the comparator then this is performed for each comparison, which is of course detrimental to runtime as well as dynamic mem allocation. \$\endgroup\$ Commented Apr 7 at 16:17
  • 1
    \$\begingroup\$ That's... not hidden. I call it out in the front-load description, and it's a pretty clear part of the stream. \$\endgroup\$
    – Reinderien
    Commented Apr 7 at 16:19
  • \$\begingroup\$ @Reinderien thanks for the valuable feedback. Before I comment on your points, just tried to run your code on leetcode's platform it runs in ~20ms (compared to 8 ms in my code). Why is that you think? is it because of streaming? \$\endgroup\$
    – ccot
    Commented Apr 7 at 16:52
  • 1
    \$\begingroup\$ Maybe! I'm not very good at DP. I suggest that you file a theory-focused question on cs.stackexchange.com . My first wild guess is that any tree-based solution won't improve on the time complexity of a basic sort, but it might win if you take advantage of some structural knowledge i.e. the digit count and the radix. \$\endgroup\$
    – Reinderien
    Commented Apr 7 at 17:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.