Given a list of non-negative integers, arrange them such that they form the largest number.

Example:

Input: nums = [4,40,44,6,92]
Output: "92644440"

Approach: Before moving to solution, lets consider one thing -

• The result may be very large, so we need to return a string instead of an integer.

At first look we came up with following two approaches immediately -

1. Sort integers in descending order: Won't work at all. Take an example - {2, 10}. With this approach it will produce 102 which is not correct.
2. Convert integers to string and then sort in descending order: It will initially look like the right approach and solve many cases like {2, 10} but take an example say {3, 31}. With this approach the result will be 313 where it should be 331 so it won't work too.

Now we can see that none of the inbuilt comparator will work for us. That means we need to write our own comparator while sorting these numbers. What should be our comparator? This is easy, if you see we are forming number by appending these numbers to each other so we just have to apply the same logic to our comparator. Here is how it can be done:

Say we need to compare two numbers NUM1 and NUM2, in our comparator we will actually be comparing numbers first formed by NUM2 appending at the end of NUM1 say NUM1NUM2 and second formed by NUM1 appending at the end of NUM2 say NUM2NUM1.

And that's all! Is it, Almost yes but we have a boundary condition here to handle. Say the input array is {0, 0}, in this case we will return "00" instead of "0"? How to handle this condition? Let's see, we know that the final array will be in descending order so we can check if first element of sorted array is 0 then the result is "0". Now that's all.

Implementation in C#:

        public static string LargestNumber(int[] nums)

        {

            Array.Sort(nums, LargeNumberComare);

            return nums[0] == 0 ? "0" : string.Join(string.Empty, nums);

        }

        private static int LargeNumberComare(int num1, int num2)

        {

            string num1num2 = $"{num1}{num2}";

            string num2num1 = $"{num2}{num1}";

            return num1num2.CompareTo(num2num1) > 0 ? -1 : 1;

        }

Complexity: O(nlogn)