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.
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!
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.
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.
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!
I spent like 45 minutes writing this convoluted sorting algorithm that looped through each digit to compare the values, got stuck, then came here. Now I feel stupid knowing the solution takes like 3 lines of code 😂
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!
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.
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; }
Yea, this works in languages like Python. But go into C++ even and two large enough ints concatenated together will overflow even a long int. So you will really be down to by-position comparison.
You can put a check, if the first element of your sorted array is 0, the rest all would obviously be zero coz the number would logically be the biggest possible after the sort. So in that case, you can just return "0".
class Solution: def largestNumber(self, arr: List[int]) -> str: for i in range(len(arr)): arr[i]=str(arr[i]) arr=sorted(arr,key=lambda x:x*10,reverse=True) ans="".join(arr) return str(int(ans))#[0,0,0] should return 0
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
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.
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
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.
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!
great explanation! tried this on my own, got stuck, and came here to listen to your explanation.
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
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.
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.
Can just check first value of string too, concatenatedString[0] == '0' ? "0" : concatenatedString
Python never overflows
Pretty sure you can't overflow int in Python.
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!
lol... worked since Python has auto big number handling.
return ''.join(nums).lstrip('0') or '0'
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!
nums = list(map(str,nums))
this will convert every int list element into str and store in nums . Python ❤️💕
Thank you!!!
@@shrimpo6416 WC Bro
nums = [str(num) for num in nums]
@@leeroymlg4692 This is what I did too!
I spent like 45 minutes writing this convoluted sorting algorithm that looped through each digit to compare the values, got stuck, then came here. Now I feel stupid knowing the solution takes like 3 lines of code 😂
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!
Careful that converting str to int for handling the 000 case could produce overflow in large numbers
That's definitely true, python makes it work but in other languages it probably won't work.
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.
@@nandhakiran6523 Great! It's clear and does not dependent on programming language.
Nums=list(map(str,nums))
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;
}
Yea, this works in languages like Python. But go into C++ even and two large enough ints concatenated together will overflow even a long int. So you will really be down to by-position comparison.
You can put a check, if the first element of your sorted array is 0, the rest all would obviously be zero coz the number would logically be the biggest possible after the sort. So in that case, you can just return "0".
@@thepriestofvaranasi you were probably replying to some other comment?
Max length of the array is 100. So write simple sort algo in O(n^2) using the str comparator logic. Simple !
great solution. never knew about cmp_to_key until now!
Thanks!!
The sound feels like ASMR, which makes me personally feel disturbing. Content is clear
Thank you
Do we have to write out own sorting function in an interview?
oh great and clear tip! thx
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) ?
9 + 34 == 34 + 9
why if n1 is the bigger significant digit, we would want to return -1?
Thank you very much
Please do 708. Insert into a Sorted Circular Linked List
You are a legend.
class Solution:
def largestNumber(self, arr: List[int]) -> str:
for i in range(len(arr)):
arr[i]=str(arr[i])
arr=sorted(arr,key=lambda x:x*10,reverse=True)
ans="".join(arr)
return str(int(ans))#[0,0,0] should return 0
Can you explain
What drawing program do you use??
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"
Actually you are supposed to preserve the order of the numbers so technically the answer you have for question 2 is incorrect 😕
Thanks 👍
nlogn or knlogn where k is the avg. length of the strings were comparing?
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.
it doesn't compare numbers individually , it compares after concatenating them.
I had the same idea but struggled to code it up :( how do I improve?
But the question states that the number could be very large hence should be returned as an string. Why didn't you used lstrip ?
Can you please explain us Accounts merge problem from leer code? I just don’t understand other explainers…
can this not be done by a recursion?
Can you do 1721. Swapping Nodes in a Linked List?
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
Thanks for the help bro,saved my time 😊
Wow this is a genius solution wtf
Did anyone try all the combinations ?
i did not get the greedy approach intuitively
Whats the time complexity?
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??
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
did anyone else tried extracting just the first character and arranging as such and got stuck.
Damn You are good
555
Custom comparator in Python sucks
My core logic was correct but execution was wrong
I love it
First
Sixth
Fourth
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!
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.
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
Second
Third