Form the Largest Number

Problem

• Largest number: InterviewBit

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 1
Inputs: 25 and 27, output: 27 then 25
Inputs: 3 and 30, output: 3 then 30
Inputs: 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 1
Lexicographically 11 <= 11, output is 1 then 1
Inputs: 25 and 27
Lexicographically 2527 < 2725, output is 27 then 25
Inputs: 3 and 30
Lexicographically 303 < 330, output is 3 then 30
Inputs: 12 and 121
Lexicographically 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.

Further reading

• Solving Algo publication

Follow me on Twitter @teivah