Largest number formed from an array

[@shivatomar4319]

This is only channel which talk about the intuition of the approach like he actually tells why we doing everything ! Great work man. Keep up the good work, please keeping bringing more questions like this if possible more frequently...we enjoy solving problems with you.

[@techdose4u]

Thanks :) I will try my best to keep it as frequent as possible.

[@faizanhassan2088]

@@techdose4u He is absolutely right, Sir.

[@nikhilkumarjamwal5322]

​@@techdose4u O(n^2)? Can you explain how it is O(n)?

[@akshatjain6854]

Brother I have been watching your videos and I am in love with coding just coz of u. Thank you so much bro. Keep uploading these type of videos. Coding community needs u.

[@jiteshkumar3112]

best channel who's main motive is to tell approach and clear the concept..thanks you Sir!

[@techdose4u]

Welcome :)

[@jiteshkumar3112]

@@techdose4u sir can you please upload some concepts and questions of backtracking. i tried alot but able to grab it in while solving dp and resursion problem

[@HariKrishnan-ff4hf]

Thanks for doing the inner explanation of Comparator..i was unhappy about geeksforgeeks explanation..but you cleared it👍

[@techdose4u]

Welcome :)

[@anilchaudhry804]

Exactly

[@deepikadhamija4548]

They way u explain things , clear all the doubts. Thnx for making such explanatory videos

[@techdose4u]

Welcome

[@blazedcosmicgoat5226]

for those saying it's O(N2) just implement the same logic in mergesort inside the merge function and you will have nlogn complexity.

[@mobilesuniverse]

yeh sabse best video hai, bhaut jagah solution deka , samaj ni aya, vector hashmap use kar rhe the

[@alokesh985]

Excellent video. Couldn't find a better explanation online!

[@techdose4u]

Welcome

[@cseengineering8582]

your voice and explanation both are so clear, this thing attracts me to this channel.

[@ShreyaSingh-vr9qi]

Video is good, but you used selection sort technique. So, time complexity is O(n^2). Thanks for making video bro, I am currently in my pre-final year preparing for product based companies. Whenever i stuck on a problem or not get good expaination from GFG. in 70./. of cases i got your tutorial which helps me. Thanks again for your hard work.

[@techdose4u]

Thanks :) The time complexity will be O(NlogN) because you will use Merge sort. I just chose it for simplicity.

[@vaibhavjain79]

Hello. I am a pre final year student now and by reading your comment I interpret that you have completed your graduation by now.. Didi can you please tell me which product based you were trying for and which company you are currently in and your preparation strategy.. I will be really helpful if you reply to me and help me by your guidance

[@akshayapanda2342]

Please don't provide wrong information, Do you think the sorting technique you have used here will give nlogn time complexity?

[@RIPNANI]

N*N😢

[@blume0f]

sir i have huge respect for u... if i land a job i will love to meet and thank u a dozen... and dont stop making videos until u hit a million!

[@techdose4u]

Thanks :)

[@Thorfin12346]

its O(n^2)

[@naresh45544]

Exactly. This is basically selection sort with the special comparison.

[@saitejaballa6759]

Using merge sort with custom sort operation is O(nlogn)

[@varunnarayanan8720]

Some kind of Bubble sort is used here but the logic is explained which is the most important part. Very good video

[@robertsedgewick1266]

Very clear explanation. Makes the solution so intuitive!

[@techdose4u]

Thanks :)

[@rhythmbhandari8549]

The explanation is pretty much simple and easy Thank you

[@techdose4u]

Welcome :)

[@rohittopal1498]

wooow , When i read question It seems very hard after I watched this video . It is very easy for me

[@davidjonson303]

Thanks sir ..for such video Your video is so easy to understand and help us a lot

[@CodeSuccessChronicle]

You’re my motivation to start coding.... thank you so much please keep inspiring us with your intuition.....

[@techdose4u]

Welcome :)

[@dineshs2484]

This technique will surely take o(n*2) as there is two loops comparing the eeach elements.but the solution was easy to understand.

[@mausham5449]

u really explain very well.thanks. plz keep posting regularly.

[@techdose4u]

Thanks....sure I am posting regularly.

[@ihopethiscommentisntabusiv4670]

Thank you for the video, but as someone mentioned the runtime is O(N^2), would be help to add the disclaimer that this can be done with mergesort to get N log(N). Either way thanks!

[@techdose4u]

:)

[@akashpradipj]

@@techdose4u in case of merge sort, how you are going to include the comparison of two strings based on their integer representation?

[@goutamkundu6392]

Great explanation Surya. Really liking your channel. Respect from your past colleague.

[@techdose4u]

Thanks Goutam ❤️

[@techacemidhun]

// Implementation of the logic class Solution{ public: // Merge two numbers string numberMerge(int a, int b){ string s1 = to_string(a); string s2 = to_string(b); return s1 + s2; } // Compare given two strings and decide they needed to be swapped. bool compareStrings( string s1, string s2 ){ if(s1 < s2){ return true; // need interchange }else{ return false; // no need to interchange } } // Core logic of the program string coreLogic(vector nums){ // Variables string largeNumber; int len = nums.size(); int temp; // Loop for(int i = 0 ; i < len ; i++){ for(int j = i+1; j < len ; j++){ string s1 = numberMerge(nums[i], nums[j]); string s2 = numberMerge(nums[j], nums[i]); if(compareStrings(s1, s2) == true){ // Swapping the numbers temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } } } // Return for(int i = 0 ; i < len ; i++){ largeNumber.append( to_string(nums[i]) ); } return largeNumber; } };

[@varsha9094]

is this c++?

[@ryanaugustine5940]

public static Integer getLargestNumberFromArray(int[] input) { PriorityQueue t = new PriorityQueue(Collections.reverseOrder()); for (int a : input) { t.add(Integer.toString(a)); } StringBuilder sb = new StringBuilder(); for (String aa : t) { sb.append(aa); } return Integer.parseInt(sb.toString()); }

[@prateeksrivastava9]

You are doing great job.Keep it up.Thanx!

[@techdose4u]

Welcome :)

[@rajarai732]

Very Helpfull explaination 😉😉

[@techdose4u]

Thanks :)

[@funcode-tw3cg]

thanks for the easy explaination of this problem !

[@vishnuv918]

Thank you brother its useful

[@techdose4u]

Welcome :)

[@nikitajaiswal9112]

implementation of your approach with edge case consideration class Solution: def largestNumber(self, nums: List[int]) -> str: if all([nums[i]==0 for i in range(len(nums))]): return "0" for i in range(len(nums)-1): for j in range(i+1,len(nums)): ij=str(nums[i])+str(nums[j]) ji=str(nums[j])+str(nums[i]) if ij

[@mysteriousocean3206]

really awesome explanation sir

[@techdose4u]

Thanks

[@gaddar1180]

Thanks for sharing the logic ☺

[@ShivamKumar-em9nr]

Very clear explanation.

[@techdose4u]

Thanks :)

[@ayushisharma1381]

Thanks for this video... Helped a lot :)

[@techdose4u]

Welcome :)

[@powersparkmotivation]

Hi Sir,,, Here we are using 2 loops (one for i and one for j) it's time complexity should be n^2 ....can u illustrate..

[@parekshamanchanda8083]

Yes correct, so you can use merge sort instead or stl's sort function with a custom comparator

[@alokesh985]

Say the first loop variable is i and second loop variable is j j starts from i+1 because we do not need to see the previous numbers, so j is decreasing every time we start 2nd loop which is why this is O(nlog(n))

[@sudosai]

@@alokesh985 you are wrong. This is similar to bubble sort. The time complexity for the method in the video is :: n+(n-1)+(n-2)+...(1) = n(n-1)/2 = O(n²) Of course you can use quick sort or merge sort to make it O(nlog(n)).

[@alokesh985]

@@sudosai Oh now i see... Thanks. I'll try using quick sort

[@deepakvm1475]

@@alokesh985 NOOOO BROO!! its O(n^2)

[@cold_water_gaming]

That was good teaching.

[@baburayhanshaik5121]

i really enjoyed your approach

[@techdose4u]

:)

[@rudra9535]

brilliant work. amazing man.

[@i.vigneshdavid1698]

Thank you for the detail explanation

[@techdose4u]

Nice ☺️ I hope you crack your job too 😀

[@i.vigneshdavid1698]

@@techdose4u 😅yeah i cracked that round.

[@techdose4u]

@@i.vigneshdavid1698 Nice :)

[@i.vigneshdavid1698]

Bro,i was not selected in designing round

[@velanganniinbaraj6593]

Awesome explanation. Thanks a lot.

[@techdose4u]

Welcome :)

[@amangoel8724]

@TECH DOSE The Time Complexity for sorting is going to be O(N^2)

[@techdose4u]

No...you can sort in NlogN time. Just for the sake of explanation, I took the easiest method.

[@amangoel8724]

@@techdose4u Thanks got it. Yes you are correct we can do it in nlogn.

[@techdose4u]

:)

[@tejaswigutta9017]

Aman Goel could you please explain how you did it in nlogn

[@abhinavreddy5350]

keep doing more tutorials tq .........................................

[@techdose4u]

Thanks for your motivation :)

[@harishvenkatesan8751]

Great work man ! Kudos !!

[@techdose4u]

Thanks

[@liutian3]

So basically what you demonstrated here is a selection sort but we can also reformulate it into an nlogn sorting method like mergesort based on the defined string comparison rule?

[@techdose4u]

Yea correct. I showed selection sort to clear the other concepts. But you need to select different algo. You can use STL and write the comparator separately which will save you the pain of implementing the entire sorting algo.

[@tejuschaturvedi6234]

Good explained 👍🔥

[@techdose4u]

Thanks

[@amermd9254]

Thanks for the explanation, I have a doubt about the sorting process Let's take an example [3,30,34] i = 0, j =1 => 330>303 so we don't swap i = 0, j = 2 => 334 3034 why this condition is not checked, is it every time the condition is satisfied?

[@pranavkochhar9352]

very good explanation

[@pratikwankhade8801]

Great solution sir

[@sakthim7160]

Hello tech dose, I have tried to reduce the time and space complexity of this approach and I have find something. In this approach in order to make swap operation of give two number(string), you are telling to merge and compare like if a and b are given we have to make ab and ba and we have to compare. So for every time we are creating two new string, it won't be efficient know and string compare also will take some time. My approach is that, we have to focus on the the first digit of the given two number, as now we are taking all the number in string format so we can access specific digit very easily. For example If 8 ,120 is given Just compare 8 and 1 and 8 is greater so don't swap 45,56 is given compare 4 and 5 and 5 is great so swap Now if 99 and 98 is given , There is clash in first digit so move to the second digit and compare 9 and 8 now 9 is greater so wap Now if 99 9 is given Here also clash in first digit and we don't have second digit to check in second number. In this case the decision should be taken based on the fully processed number. If first number fully processed no need to swap and if second number fully processed we have to swap. If both are fully processed means both are Same number and no need to swap.

[@techdose4u]

This will be inefficiet and can be complex to implement. If you take an example 21 and 219 then according to you, Number will be 21219 but instead, it should have been 21921. I hope you get it.

[@sakthim7160]

@@techdose4u I will take this case into consideration and more thing this not an inefficient approach. I have to work on it. Can you explain why are you telling it's inefficient?

[@brajkishoredubey9319]

@@sakthim7160 i think your approch looks good , just check size of string for swapping for above scenario (21 and 219 )

[@brajkishoredubey9319]

@@techdose4u ​ @Sakthi M i think your approch looks good , just check size of string for swapping for above scenario (21 and 219 ) and then do compare as you mentioned .

[@anantpatel8342]

Sir, if i solved it by using the permutations from the itertools library. I generated all the possible numbers from the given elements and stored it in a list, then i sorted the array to get the maximum possible number. Just wanted to ask, is this approch correct? Will this soloution be approved in interviews? The code is - from itertools import permutations arr = [3, 30, 34, 9] arr = list(map(str, arr)) fin = list(permutations(arr, len(arr))) fin = list(map(''.join, [i for i in fin])) fin = list(map(int, fin)) fin.sort(reverse=True) print('The maximum number is',fin[0])

[@techdose4u]

This can work in coding round if STL is allowed but try to use common STLs only in interviews and not these. If you have no resort then you should use it but be ready for the follow-up question to implement permutation 😅

[@anantpatel8342]

@@techdose4u Thank you sir.

[@techdose4u]

Welcome :)

[@ankitsihag6324]

i think the t.c. will be n! so its better to use this method

[@diconicabastion5790]

If you are simply looking at creating a char string from them your answer is correct. However, if you are looking at them as integers trying to form the largest integer or unsigned integer your answer is wrong. bytes, words and integers all have a specific length. so there are hidden values in them. Well make this simple and assume they are unsigned integers. 0x00000003u = 3, 0x00000022u = 34, 0x00000009u = 9, 0x0000001Eu = 30 thus the largest integer that can be made with them is 0x000000220000001E0000000900000003u or 0x220000001E0000000900000003u or 2,693,757,526,038,389,800,430,435,565,571. Your problem is you used the term array and integer when in a programming reference. For those that don't know what I am talking about integers or int is usually a 32bit sized value. words 16 bits and bytes 8bits. Long int is 64 bits same with long long. you can also have a __uint128_t which is a 128bit unsigned int

[@kirtishghosh8950]

Very well explained

[@abhinabadas7606]

the sorting technique here is based on selection sort so the time complexity should be n2, how is it nlogn

[@techdose4u]

You can change the sorting technique to make it NlogN

[@abhishek__anand__]

Nice Explanation

[@tusharkumar3277]

awesome video man

[@techdose4u]

Thanks :)

[@daniekpo]

I don't get how that's O(n log n). We're pretty much doing an insertion sort which is O(n^2).

[@techdose4u]

It will be N^2 due to string addition which is O(N).

[@knightcoder]

CODE ==> sort(a.begin(),a.end(), [](int x,int y){ return (stoi(to_string(x)+to_string(y)) > stoi(to_string(y)+to_string(x)));});

[@deepukathait6916]

Nice approach sir

[@techdose4u]

Thanks :)

[@nithinchitra1570]

superb work bro

[@ppujari]

What software do you use for explaining in this video? This is very nice.

[@nextgeneration2835]

respect++; thanks for the video

[@techdose4u]

Welcome :)

[@narendrakumariitb]

Thanks nicely explained. Time complexity won't be O(n*n x O(string comparison)). Since it looks similar like bubble sort

[@beautifultime9031]

Narendra Singh but we can pick a sort algorithm such as Quick Sort with the string comparator.

[@techdose4u]

@@beautifultime9031 yea Vishal correct. I explained using selection sort for easy explanation but we need to change the algo (like use Merge sort etc.).

[@yyndsai]

Is there any better algorithm than this?

[@geekforgeeks3836]

owsome explanation

[@techdose4u]

Thanks :)

[@shubhamsumanvishwakarma7113]

Can we prove transitivity? Say A, B, C are strings, If AB >= BA and BC >= CB then is AC >= CA?

[@hoyinli7462]

great explanation. one comment. could you please use standard letter instead of cursive letter? overall great

[@techdose4u]

Sure

[@rajeevcbhatia]

great explanation sir. i have a question about the complexity of such a sort, seems like every element is compared n times here. does that make the complexity O(n2)? don't native sorting algorithms have an O(NlogN) performance?

[@techdose4u]

O(N^2) because string comparision is O(N)

[@rajchaudhary1645]

same question came in my mind.

[@rajeevcbhatia]

@@techdose4u thanks! so would it be NlogN if they are int with this comparator?

[@minnuanish9828]

can you explain how to implement the coding also,the append part

[@techdose4u]

You can use string append to solve

[@neerajmahapatra5239]

Amazing 👍

[@trishulcurtis1810]

Very Intuitive

[@MainakDev]

I understood the problem but didn’t understand the code, you took 2 strings as input Whats the input should be an Array. I’m confused.

[@MainakDev]

Never mind I’m an idiot

[@amitjaiswal6594]

Can we sort the array in decreasing order by last digit of every string?

[@techdose4u]

How? If you only compare last digit then what about other digits? Please mention the steps for sorting.

[@amitjaiswal6594]

@@techdose4u i don't know exactly but i am trying reduce the complexity can we?

[@techdose4u]

I think we need to atleast compare all the elements then only we make a decision for largest number. Sorting does that. Does any other algo do it in less time? Think about it. There might be one.

[@subhambanerjee6334]

the technique you used is similar to bubble sort so how is this O(N log N) ?

[@techdose4u]

You will use optimized sorting using library

[@shourabhpayal1198]

We are checking for every i,j pairs. Shouldn't the complexity be n square if strings are considered to be constant len instead of nlogn ?

[@techdose4u]

Actually I have shown simple sort. But you can use optimized search like mergesort implemented in library to get NlogN.

[@shourabhpayal1198]

@@techdose4u thank you i have figured it out and implemented a custom mergesort as well. If anyone wants to know how let me know.

[@techdose4u]

@@shourabhpayal1198 👍🏼 Share the link for code.

[@MilindGupta]

@@shourabhpayal1198 please share that code

[@shourabhpayal1198]

@@MilindGupta I think youtube is removing the link comment

[@nobita7231]

how do calculate time complexity and space complexity Brother??????? Can u teach please

[@techdose4u]

I have uploaded some basic videos on it. Please watch them.

[@satyasahoo9573]

Instead of swapping, if we do insertion, we can get rid of comparision of the same elements multiple times.

[@techdose4u]

🤔 If you have implemented then can you share your code. It will be much more clear that way.

[@fazilshafi8083]

Java Folks, here is the complete working solution: class Solution { public class CustomComparator implements Comparator{ @Override public int compare(String a, String b){ String n1 = a+b; String n2 = b+a; return n2.compareTo(n1); } } public String largestNumber(int[] nums) { String[] arr = new String[nums.length]; for(int i=0; i

[@tarunkumar.d8379]

Why do we return false when both ij and ji are equal???

[@nikitajaiswal9112]

any optimized techinique for this problem??

[@prasad.patil12]

How can sorting time is nlogn you are comparing current element with all the rest of the elements shouldn't it be n^2?

[@techdose4u]

Yea N^2. But I just it in a generalized way NlogN. Even adding 2 strings is O(N).

[@himankgupta7968]

Can't we find out density of each element (element divided by the number of digits) and then sort them elements on basis of decreasing density...we get same answer O(n)...any case where it will fall?

[@ravikant-hi8mz]

Can we have merge sort here? That will also be nlogn

[@saumya1singh]

GREAT

[@techdose4u]

Thanks

[@willturner3440]

You always rock🤘

[@consistentthoughts826]

Shouldt it be N²logN right as we are traversing the array 1 time

[@rajatmishra6628]

Can be done in O(n) only

[@techdose4u]

Please share the algo

[@rishisharma5249]

Is it correct to say that you are sorting using a comparator which compares two numbers formed by appending after each other

[@techdose4u]

I think you can say that (Descending order).

[@rishisharma5249]

@@techdose4u Okay, thanks 😊

[@deepakvm1475]

bro even on merge sort this takes same no of compriationswhen doin it in c,can you explain whta logic inside that mergeing funtion (i took 1st element from left array and compared all the elements in right array));

[@danish829]

really helpful

[@techdose4u]

Thanks :)

[@rakshith3547]

"179. Largest Number" , Please update the description with leetcode number.

[@techdose4u]

I will try.

[@rosankumarsenapati3510]

Hello sir can we do it in this way we will sort it based the 1st digit and we will also have their indices in a map then we itrate over the map and with their indices we can for the number Total time complexity will be O(N)

[@rosankumarsenapati3510]

Correct me if i am wrong

[@chiluvurideepthi6822]

I had implemented this and I was getting TLE .Could you please help me out...

[@gauthamarunachalam]

The time complexity will be O(N^2)

[@Nature-fp7zv]

It will be nlogn

[@deepakvm1475]

@@Nature-fp7zv how

[@MeraBaapHaiTu31]

Thnakyou Sir

[@techdose4u]

Welcome

[@tanyachhetri9406]

how is the time complexity of sorting not n2 but nlogn?

[@nikhilsingh5854]

Use Merge or Quick sort :)

[@NihalSingh-ld2en]

no the time complexity will not be nlongn, you are simply doing bubble sort, with string comparing.... it is n^2

[@rushikeshpujari2364]

sir if the array contain -ve number .(-1-2-3-4)-->o/p will be -1234 but getting {-4,-3,-2,-1} [using your approach]

[@gauthamarunachalam]

Does radix sort wont work?

[@syedkaja2045]

how are u thinking like this pls tell😆

[@techdose4u]

😀 You will become a pro with practice and better than me bro :)

[@syedkaja2045]

thanks bro😄

[@SomnathDas-fg2qc]

cann't we do it least possible approach that means O(N) because the approach which u have explained in worst time comolexity would be very high

[@manikantabandla3923]

We can solve this using radix sort which takes O(n) time

[@aadityaupadhyay6264]

Coursera brings me here GFG got the worst explanation thanks, man

[@techdose4u]

Welcome :)

[@rohittopal1498]

same brother

[@MeraBaapHaiTu31]

Algorithmic Toolbox?

[@SameerSk]

University of California San Diego Algorithm Toolbox squad.