Largest Number - Leetcode 179 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
💡 BINARY SEARCH PLAYLIST: • Binary Search
📚 STACK PLAYLIST: • Stack Problems
Problem Link: leetcode.com/problems/largest...
0:00 - Read the problem
1:25 - Drawing Explanation
5:13 - Coding Explanation
leetcode 179
This question was identified as an interview question from here: github.com/xizhengszhang/Leet...
#amazon #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[@nikkil7428]

You are the best one yet. Your videos had been helping me so much, from struggling doing medium, to now conquering medium leetcode. Your positive energy also giving me such a good vibe to work on supposed to be boring and painful leetcode questions. ❤❤❤ Thank you.

[@rhosymedra6628]

great explanation! tried this on my own, got stuck, and came here to listen to your explanation.

[@aswinbarath]

I struggled a more than 1 hour on this problem by doing it myself without the knowledge of Custom comparator concept. Thank you so much for this solution bro!

[@rakoonberry7879]

I'm not sure if your str(int(..)) solution at the end is the best way to go about it. The problem says that the number may be large (i.e. overflow) so we are asked to return a string. A loop would probably be a better albeit less elegant answer.

[@jessesinger4790]

Can just check first value of string too, concatenatedString[0] == '0' ? "0" : concatenatedString

[@jimmycheong7970]

I ended up writing a recursive comparator function which took me ages to figure out properly! Only I had submitted a successful solution did I find out you can just add the nums strings as strings in different orders. 🤦🏻‍♂️. Thanks for the video as always!

[@OneMoreLight1]

nums = list(map(str,nums)) this will convert every int list element into str and store in nums . Python ❤️💕

[@shrimpo6416]

Thank you!!!

[@OneMoreLight1]

@@shrimpo6416 WC Bro

[@leeroymlg4692]

nums = [str(num) for num in nums]

[@rohanchess8332]

@@leeroymlg4692 This is what I did too!

[@stephenbouldin8163]

As someone new to python, and coding in general, I learn something new in each of these videos. However, it would be more helpful if you explained the functions within the class a little more.

[@fer-ic1wh]

for those who don't understand the cmp function. paste source code here def cmp_to_key(mycmp): """Convert a cmp= function into a key= function""" class K(object): __slots__ = ['obj'] def __init__(self, obj): self.obj = obj def __lt__(self, other): return mycmp(self.obj, other.obj) < 0 def __gt__(self, other): return mycmp(self.obj, other.obj) > 0 def __eq__(self, other): return mycmp(self.obj, other.obj) == 0 def __le__(self, other): return mycmp(self.obj, other.obj) = 0 __hash__ = None return K

[@Cloud-577]

Do we have to write out own sorting function in an interview?

[@HolyCowSoft]

oh great and clear tip! thx

[@redfinance3403]

My solution was pretty ugly and consisted of making the number into separate digits within a map of maps of maps ... and then sorting each map in descending order based on the key. Then recursively iterating over the digits and eventually adding them in order to the answer. This comparator idea is very smart and its amazing how the idea didn't come to me earlier given the fact that my code is basically selecting the best possible order to add them in. Once again, amazing video!

[@weaponkid1121]

What drawing program do you use??

[@oneplusgeek7510]

Thanks!!

[@AlexSav]

0:25 It may be very large, so return string instead of an integer 10:35 - Just convert to an integer and then back to string Genius!

[@jfcherng]

lol... worked since Python has auto big number handling. return ''.join(nums).lstrip('0') or '0'

[@Cloud-577]

I had the same idea but struggled to code it up :( how do I improve?

[@neilgaliaskarov5341]

Can you please explain us Accounts merge problem from leer code? I just don’t understand other explainers…

[@longschlongify]

Great video, but I have a question. Why do we return 1 and -1 in the compare function instead of the actual n1 or n2 itself?

[@FCBarcelonaXMI]

The way cmp_to_key function works is that you pass it a method (compare) that will either return -1, 1, or 0 in order to sort the items in the list. You don't actually need to return the values themselves because it just has to compare them to know which item is less or greater, then it will automatically sort the items.

[@longschlongify]

@@FCBarcelonaXMI Thanks! That makes sense!

[@navamshuram]

@@FCBarcelonaXMI My doubt is why we should return -1 for n1 going first ??

[@FCBarcelonaXMI]

@@navamshuram I don't know if there is a particular reason why, that is just the way cmp_to_key function is designed to work in Python.

[@cocoatut49]

@@navamshuram I think this function sorted the return value. If the return value is -1 then it goes first.

[@santoshrathod9868]

You are a legend.

[@niharikkatyagi4089]

I'm not sure why, but this is returning a NULL value in each case when I try to run it. Is there any solution to this??

[@gskpsrikar1858]

Max length of the array is 100. So write simple sort algo in O(n^2) using the str comparator logic. Simple !

[@el_chivo99]

great solution. never knew about cmp_to_key until now!

[@Dezdichado1000]

can this not be done by a recursion?

[@FACS01]

Careful that converting str to int for handling the 000 case could produce overflow in large numbers

[@NeetCode]

That's definitely true, python makes it work but in other languages it probably won't work.

[@nandhakiran6523]

We can avoid that, just check if the sorted arrays first element is "0". if so, that means everything after it will also be "0" so we can just return "0" right there :) And if that is not good enough, we can sum the initial array, if it is 0, return "0". But that decreases the efficiency of the code.

[@HelloJaewon]

@@nandhakiran6523 Great! It's clear and does not dependent on programming language.

[@sharksinvestment9864]

Nums=list(map(str,nums))

[@pammugaadu]

Thank you very much for your valuable time. I really appreciate. If anyone is looking for Java code: public static String getLargestNumber(int[] input) { String output[] = Arrays.stream(input).mapToObj(String::valueOf).toArray(String[]::new); Arrays.sort(output, (n1, n2) -> { return (n2 + n1).compareTo(n1 + n2); }); String result = Arrays.stream(output).collect(Collectors.joining()); if (result.matches("^[0]*$")) { return "0"; } return result; }

[@mickeymacke1780]

Can you do 1721. Swapping Nodes in a Linked List?

[@shubhamsingla8182]

Please do 708. Insert into a Sorted Circular Linked List

[@rohanchess8332]

Wait, how can you compare strings like integers, it compares the ascii value right, so shouldn't we use int(n1+n2) > int(n2+n1) ?

[@jessesinger4790]

9 + 34 == 34 + 9

[@hueydo3522]

why if n1 is the bigger significant digit, we would want to return -1?

[@nikhil199029]

If we compare 9 and 930 then 930 has a higher value so this code should return 9309 instead of 9930? Not sure what am I missing.

[@dakshbhayana237]

it doesn't compare numbers individually , it compares after concatenating them.

[@its_me_tabs]

Whats the time complexity?

[@user-hf7ef6nm4s]

nlogn or knlogn where k is the avg. length of the strings were comparing?

[@miguelangelrodriguez8999]

Thank you

[@symbol767]

Wow this is a genius solution wtf

[@monicawang8447]

Hey can anyone explain why we return -1 when n1 + n2 > n2 + n1? I'm confused about how returning -1 or 1 works here..Thanks!

[@iaingavinsoutherland4369]

Hey, my guess is as good as any but I was playing around with it. We're trying to compare elements, e.g. if we have a='30' and b='3' (in python notation), we are trying to figure out if a+b ('303') is larger than b+a ('330'). The cmp_to_key function is part of the functools module, and tells the sorting to use our comparison method. So if we want to decide whether to put '30' or '3' first, we look at whether a+b or b+a is bigger. In order to tell the key which is better, in almost a boolean sense, we say positive means change/don't change order, and negative means don't change/change order. So if we get in a='30' and b='3', (note that in the key function, the first value is later, so we would have a list that had [......, 3, 30, .......] in there, if a+b > b+a (303 > 330, not true in this case), we would pass a -1 (red flag), and the key function would switch order to have [...., 30, 3, .....]. In real life, that case wouldn't be true, and the key function would receive a 1 (green flag) so that it wouldn't have to switch the two. Bit long, but it's an odd question. Can't imagine answering this in an interview. Also note that you could return any positive/negative (e.g. 420/-69), but you can't return a 0 or it gets screwy. The delineator is positive vs negative as switch position after comparison vs don't switch position after comparison.

[@SkyeTian]

1. This key is eventually helping sorted() to arrange elements in ascending order; 2. It returns a negative value indicating the first argument is lesser than the second argument or a positive value indicating the first argument is greater than the second argument. So if n1 + n2 > n2 + n1 we want to put n1 first so we must tell it that n1 is the smaller one thus return -1

[@amarnathmishra8697]

Damn You are good

[@aprily5016]

The sound feels like ASMR, which makes me personally feel disturbing. Content is clear

[@numberonep5404]

I love it

[@tanaypatel8412]

did anyone else tried extracting just the first character and arranging as such and got stuck.

[@jugsma6676]

I always solve my way before watching the solution, and this is my solution, def max_number(nums): res_lst = permute(nums) max_str_numb = -sys.maxsize for i in range(len(res_lst)): appended_str = ''.join([str(r) for r in res_lst[i]]) max_str_numb = max_str_numb if max_str_numb > int(appended_str) else int(appended_str) return str(max_str_numb) def permute(nums): if len(nums) == 1: return [nums] res = [] for i in range(len(nums)): head = nums[i] remainder = nums[:i] + nums[i+1:] for p in permute(remainder): buffer = [head] + p res.append(buffer) return res

[@lakshyasaharan5348]

First

[@saurabhverma7366]

555

[@shrio272]

Second

[@awukugodfred6610]

Third

[@brogrammer8783]

Fourth

[@linggesarulsamy]

I wrote the function in JavaScript: 1) Arr_To_Single_String = Array.join(""); Convert the Interger Array to a Single String: [10, 2] => "102" 2) Arr = Arr_To_Single_String.split(""); Split the String to each character individually in Array; "102" => ["1", "0", "2"] 3) Sorted = Arr.sort().reverse(); Sort the Array in descending order ["1", "0", "2"] => ["2", "0", "1"] => "210" function sortString(Array) { let Arr_To_Single_String = Array.join(""); let Arr = Arr_To_Single_String.split(""); let Sorted = Arr.sort().reverse(); return Sorted.join(""); } // Question 1 let Q1 = [10, 2]; console.log(`sortString(${Q1}) = ${sortString(Q1)}`); // Output: "210" // Question 2 let Q2 = [3, 30, 34, 5, 9]; console.log(`sortString(${Q2}) = ${sortString(Q2)}`); // Output: "9543330" // Question let Q3 = [10, 2, 5000, 321]; console.log(`sortString(${Q3}) = ${sortString(Q3)}`); // Output: "5322110000"

[@jimmycheong7970]

Actually you are supposed to preserve the order of the numbers so technically the answer you have for question 2 is incorrect 😕

[@navamshuram]

def comp(a,b): if (a+b)>(b+a): return -1 else: return 1 # arr.sort(key = functools.cmp_to_key(comp)) ans="".join(arr) return ans

[@guruprasadv7972]

Sixth