[Solution]Problem 27: Create largest possible number using list[Amazon]

Integer List, String Conversions, Custom Comparitors

Problem

This problem was asked by Amazon

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, you need to return a string instead of an integer.

For example, given the list, nums = [3,30,34,5,9] we want to return the string, “9534330”

The solution we get for this

Step 1: Looking at the basic structure

A good way to start solving problems is to identify the I/O and the basic process. This gives us a skeleton that we can approach:

1. Input--We are given a list of integers. We want to combine the elements of the list into a big number.

2. Output— A string representing the biggest number.

What about the approach? We can keep things simple. Notice the following fact: the biggest possible number has the largest digit in the biggest number place. Between the option, of having 9 in the first place , and 8 in the first place, the number starting with 9 will be bigger (90 is bigger than every number <=89).

Finding GIFs is pretty fun.

Let’s verify this with a few examples-

Take nums= [50 491]. Here the largest number is 50491. This matches the pattern of fitting the largest number first. A more complex example is [10,28,37,42,5]. The largest number here will be 542372810.

This should make one thing clear, we want to go digit by digit and compare. Only the biggest digit at a place matters. This is starting to look kind of like a Lexicographic order problem

I could give you a long definition, but this image suffices. The details of the sorting depending on your specific problem.

Using terms like this are important in your interviews because it is an easy way to show off your knowledge. Fortunately, the solution to this question is relatively straightforward.

Step 2: Figuring out the sorting

Noticing the lexicographic sorting is 70% of the portion. The next 20% lies in the specific details. How should we handle the sorting between cases like [3,30]. What about [3,34]. Essentially two numbers who’s string form follows the specific format [number, number+other_number].

Here 12 and 1221111111111 follow the format

Notice in such as case we can break our possible other number into two cases:

1. Substring is lexicographically smaller - Here the digits after the common substring are lexicographically smaller than the common substring. Take the example of 3,310. Here the common substring (3) is larger than the substring after common/other_number (10).

2. Substring is lexicographically larger. Opposite case. Here the digits after the common substring are lexicographically larger than the common substring. Take the example of 3,3410. Here the common substring (3) is smaller than the substring after common (410).

For an example of case by case solutions, check out this solution.

In case 1, it seems like we want the smaller string (length-wise) first. This makes sense, because we want to push the small one as far back as possible. For our example, 3103 becomes smaller than 3310.

In case 2, the opposite is the case. However, it’s not a good idea to be sure after one example. Can we make things more rigorous?

Let’s look at the situation closely. We can either create a number following the format number-number+other_number (331) or number+other_number-number(313). This should make it quite clear why the rule makes sense.

Step 3: Code

Once we have the logic, let’s combine everything into code. The code is relatively straightforward as:

class LargerNumKey(str):
    def __lt__(x, y):
        return x+y > y+x
        
class Solution:
    def largestNumber(self, nums):
        largest_num = ''.join(sorted(map(str, nums), key=LargerNumKey))
        return '0' if largest_num[0] == '0' else largest_num

The comparitor might seem weird. Why didn’t I just give to you straight? It would’ve been easier for both parties involved. Simple, I wanted to make sure you understood the theory aspect first. Being able to lexicographically compare strings is a neat aspect of Python, but it is not common across all languages. I wanted to let you see the thinking behind the process.

We are mapping each element to a string and them concatening them. This is constant time. The big part is the sorting which is O(nlog n) time.

For the space- we have to store a string the length of all the digits in the list. This is linearly proportional to the length of the list.

Time- O(nlog n) because of the sort

Space- O(n) to store the solution.

Bonuses/Promotion (Get Free Stuff)

To learn how to interview better DM me. Let’s set up mock interviews and go over different interview techniques. In addition to focused questions, and a detailed personalized plan, we will go over the right questions to ask during your interviews.

For most of my students, mock interviews have been very helpful. Enough mock interview practice is the key between getting that job offer and rejection. If you can get three people to become paying subscribers to this newsletter, you win a free mock interview. This offer has no upper limit, so the more subs you can get, the more mock interviews you win.

To share interesting problems/solutions 2with me, reach out to me. Different social media of mine also have other content from me. Good problems and/or solutions receive a free shoutout + 2 months of the paid newsletter:

Reach out to me on:

Instagram: https://www.instagram.com/iseethings404/

Message me on Twitter: https://twitter.com/Machine01776819

My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/

My content:

Read my articles: https://rb.gy/zn1aiu

My YouTube: https://rb.gy/88iwdd

Get a free stock on Robinhood. No risk to you, so not using the link is losing free money: https://join.robinhood.com/fnud75