On Trying things out

The more you look at things through the lens of the familiar, the more you end up reproducing what already exists.
— Unknown

I came across an interesting (and quite popular) LeetCode question a few days ago, Largest Number. The problem is quite straightforward; here’s the description:

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.


Example 1:
Input: nums = [10, 2]
Output: "210"

Example 2:
Input: nums = [3,30,34,5,9]
Output: "9534330"


Constraints:
1 <= nums.length <= 100
0 <= nums[i] <= 10^9

I decided to give it a shot, and as I was thinking through and trying out different possible implementations, I realized the most optimized solution I could come up with had different time complexities for the worst, average, and best cases. Here’s what each of them worked out to be:

Worst case: O(n log n)
Average case: O(n log n), but with much better constant factors (I will get to this a little later)
Best case: O(n)

Curious to see what others had come up with and if there was a general solution for this problem, I went through all the popular solutions in LeetCode’s solutions tab, several blog posts providing solutions, and prompted different LLMs (ChatGPT and Claude) for solutions. All the solutions I could find had the same implementation with minor variations (depending on the language they were written in). This was expected, as the top solutions are usually going to be the most optimized and well-accepted solutions. What surprised me was that all solutions I could find performed at O(n log n) time in all cases, which in my solution was only for the worst case.

Here’s a variation of the common solution in Python:

from functools import cmp_to_key

def largestNumber(nums):
    def compare(n1, n2):
        if n1 + n2 > n2 + n1:
            return -1
        else: 
            return 1

    for i, num in enumerate(nums):
        nums[i] = str(num)
            
    nums = sorted(nums, key=cmp_to_key(compare))
    return str(int("".join(nums)))

I won’t walk through each line of the algorithm as it’s pretty straightforward, but here’s an overview:

We convert each integer inside the nums array to a string.
We sort based on the result of the function compare, which compares the passed arguments by concatenating them both ways.
We assign the sorted array to nums, convert it to a string, and return the converted string.
We also handle the special case where all numbers in nums are 0.

The heavy lifting happens in line 13, where we sort the nums array based on a custom sorting function compare. If you’re familiar with sorting algorithms, you know the fastest sorting algorithms provide a time complexity of O(n log n) in the worst case. As you might have guessed, sorting is also the bottleneck in this solution - regardless of any optimizations we make at any other step, the overall time complexity will be O(n log n) due to sorting.

Now, let’s look at the solution I came up with:

from functools import cmp_to_key

def largestNumber(nums):
    if not any(nums): return "0" # If all numbers in nums are 0

    buckets = [[] for i in range(10)]
    res = ""

    def compare(n1, n2):
        if n1 + n2 > n2 + n1:
            return -1
        else: 
            return 1

    for num in nums:
        if num < 10:
            buckets[num].append(str(num))
        else:
            idx = int(str(num)[0])
            buckets[idx].append(str(num))

    for i in range(len(buckets)-1, -1, -1):
        if len(buckets[i]):
            if (len(buckets[i])==1):
                res+=buckets[i][0]
            else:
                buckets[i] = sorted(buckets[i], key=cmp_to_key(compare))
                for elm in buckets[i]:
                        res+=elm
        
    return res

So what changed? Well, you can guess just by the length of the code snippet that we’re doing more operations than the first solution. Let’s quickly walk through the algorithm:

We start by declaring a buckets array which contains ten empty arrays.
We also declare a string res which will be our returned string.
We convert the integers to strings and push them from nums to buckets based on their first digit. For instance, 2 would be pushed at position 2 in buckets, and 340 would be pushed at position 3 .
Now we iterate through the buckets in reverse and start concatenating the values from all non-empty buckets with res.
If we encounter a bucket that has more than one item, we sort that bucket based on the same compare function as the previous solution and concatenate each value from the sorted bucket with res.
We handle the special case where all numbers in nums are 0 here as well.

I agree we certainly had to do more operations to get to the same result as the first solution; however, this has significantly optimized our solution in certain cases. Let’s look at the time complexity for each case:

Worst case: This occurs when all numbers in nums begin with the same digit (e.g., nums = [20, 244, 2, 21, 255]). In this case, all the numbers would need to be sorted, and our time complexity would be O(n log n). This is same as the first solution.
Average case: Now this is where we differ from the first solution. Average case occurs with datasets having diverse first digits, where only some buckets need to be sorted. The time complexity works out to be O(n + k * (m/k) log(m/k)), where n = the total number of elements in nums, k = total number of buckets (10), and m = number of elements in the largest bucket.

While O(n + k * (m/k) log(m/k)) simplifies to O(n log n), making them asymptotically equivalent from a pure algorithmic complexity standpoint, in practice, this would perform much better due to the reduction in the size of subarrays that need sorting and by avoiding sorting altogether for some buckets.
Best case: This occurs when all elements are in different buckets, i.e., all elements have different first digits. In this case, we would eliminate sorting altogether, and the time complexity would be O(n).

So, just by using some simple but clever techniques we were able to optimize our solution.

Now, reading through all that, you might be asking, “So, you came up with a solution, why did I have to go through all this?”

That’s a fair question, and the point I’m hoping to make is about the value of trying things out and the joy of figuring things out. Had I skimmed through a solution first or looked at the hints, I likely wouldn’t have come up with the solution that I did.

With almost all imaginable information available to us so easily, our first instinct is usually to do a Google search or ask our favorite AI friend when we hit a roadblock. But maybe we’re reaching for these tools too quickly? Maybe we could sit with a problem for a while? Sure, you might spend some extra time. Yeah, you’ll probably go down some dead ends, but that’s actually the fun part! When you give yourself permission to just try things out - even ideas that seem kind of weird - you might stumble onto something interesting that you wouldn’t have found otherwise.

I’m not saying every problem needs to be solved from scratch. That would be ridiculous (and a waste of time). But every once in a while, it’s worth closing the browser, putting away the AI assistant, and just playing around with the problem yourself. Who knows? You might come up with something that hasn’t been done before. And even if you don’t, you’ll understand the problem way better than if you’d just looked up the solution.

Before closing, I want to go back to the problem and make the remark, in true engineering spirit, that the solution you choose “depends.” I hope I didn’t give the impression of dismissing the first solution. If you’re working with a small dataset, you should certainly go with the first solution as it’s more concise, and the performance gain from the second solution would be minimal at best. If performance is critical to you and even the smallest gain counts, then you would benefit from the second solution.

Notes

I intentionally left out space complexity as both solutions use linear auxiliary space and it wasn’t relevant to the discussion.