Definitely an interesting solution, nice one! I wonder why you couldn't just sort the original list straight-up for the same time complexity? Surely just `return sorted(unsorted)` would do the trick? Another question I thought about here was the true time complexity of sorting the strings: because they're stored in string format, and we can't (maybe in python we actually can, but nvm that for a moment) convert them directly to an integer, which has O(1) comparison using a CPU instruction, surely when comparing two strings when sorting, we in fact need to compare every character separately...? The only thing I can't tell is whether this introduces another factor into thr time complexity or not, because it definitely seems like more work, but is it technically constant because the inputs are no more than 2*10^5 in number?
Hey, thanks for watching! I didn't go into detail about sorting the list of numeric strings as it is, but doing so reveals 2 big problems. The first problem is that programming languages have an upper limit on how big an integer can be (as well as be reliable & "safe"). In python the max unsigned integer is 18,446,744,073,709,551,615 (as a string this would be 20 characters long) - meaning any number larger than this cannot be held in memory. In JavaScript, the max safe integer is 9,007,199,254,740,991 (as a string this would be 16 characters long). This is why we cannot handle these numeric strings as integers, they're just too big having a length of way more than 16 or 20 characters. So, we have to sort them as strings, which reveals the 2nd problem. Strings are sorted lexicographically, which is similar to how words are sorted in a dictionary. "A" goes before "Axe", which both go before "Be" - the same way numeric strings would be sorted as "1" goes before "183", which both go before "23". The sorting we need still has to use lexicographical sorting, but in such a way that it results in typical integer sorting. Hence the added complexity for the solution. In the video, I do make an error regarding the time complexity. I should have used a proper variable to denote the length of the string, it's not constant as I implied. Each string gets compared and is sorted for each string, so the total time complexity is more like O(k*nlogn) Let me know if that doesn't make sense.
