# Problem

`Given a list of non negative integers, arrange them such that they form the largest number.Example: Given [3, 30, 34, 5, 9], the largest formed number is 9534330. The result may be very large, so you need to return a string instead of an integer.`

Category: Arrays

# Solving Process

Arranging an array in a particular order should trigger the idea to implement our custom sorting strategy.

In Java, it means implementing the `Comparable` interface.

As such, this problem is not very complex but it might be easy to make a mistake during the sorting strategy implementation.

Let’s see some examples of the desired outputs of our sorting implementation, considering we would like to sort them in the reverse order (9 < 8 means we will produce the output 98):

`Inputs: 1 and 1, output: 1 then 1Inputs: 25 and 27, output: 27 then 25Inputs: 3 and 30, output: 3 then 30Inputs: 12 and 121, output: 12 then 121`

There’s a little trick here, hopefully, you spotted it.

The easiest solution is to concatenate (not adding, concatenate) the two integers in both ways and to compare them:

`For clarity, the first input is in bold.Inputs: 1 and 1Lexicographically 11 <= 11, output is 1 then 1Inputs: 25 and 27Lexicographically 2527 < 2725, output is 27 then 25Inputs: 3 and 30Lexicographically 303 < 330, output is 3 then 30Inputs: 12 and 121Lexicographically 12112 < 12121, output is 12 then 121`

A possible implementation in Java:

To return a valid integer representation, we just have to make sure the input `0 0 0 0` return `0` and not `0000`. This is done by checking if the first element of the `containers` array is equals to 0.

The time complexity is O(n log(n)) with `n` the number of elements of the list as we have to sort the array. The space complexity is O(n) (linear), with `n` representing also the number of elements, as we have to create another array to implement the sorting strategy.