Largest Number - Solution & Explanation

Problem Overview: You are given an array of non‑negative integers. Rearrange them so that their concatenation forms the largest possible number. The tricky part is that normal numeric sorting does not work. For example, 9 should come before 34, but 34 should come after 3 because 343 is smaller than 334. The solution depends on comparing numbers based on their concatenated order.

Approach 1: Custom Sorting Using Concatenation Comparison (O(n log n))

Convert all integers to strings and sort them using a custom comparator. For two values a and b, compare a + b with b + a. If a + b is larger, a should appear before b in the final ordering. This works because the goal is maximizing the combined string, not the numeric value of each element individually. The algorithm relies on a customized comparison inside a standard sorting routine.

After sorting, concatenate all strings to produce the final number. A special edge case appears when the largest value is "0". This means all numbers are zeros, so return "0" instead of something like "0000". The time complexity is O(n log n) due to sorting, and each comparison costs up to O(k) where k is the digit length. Space complexity is O(n) for storing string representations.

This approach combines ideas from array manipulation and greedy ordering. The greedy insight is that the locally optimal concatenation decision between two numbers leads to a globally optimal result after sorting.

Approach 2: Custom Comparator Using Heap (O(n log n))

Instead of sorting directly, push all numbers (as strings) into a heap that uses the same concatenation comparator rule. The heap ensures that every extraction returns the element that should appear next in the largest concatenated result. Each push and pop operation maintains the comparator order internally.

Repeatedly pop from the heap and append values to the result string. The comparison logic remains identical: choose the element where a + b produces a larger string than b + a. This method still performs about O(n log n) heap operations, and each comparison takes O(k). Space complexity remains O(n) for the heap structure and string storage.

Heap-based ordering is useful if elements are processed incrementally or when you prefer explicit priority queue control instead of full sorting. In most implementations, direct sorting is simpler and faster in practice.

Recommended for interviews: The custom sorting approach is what most interviewers expect. It demonstrates understanding of comparator logic and greedy ordering. Mentioning brute intuition (trying permutations) shows you understand the search space, but implementing the concatenation comparator with a + b vs b + a is the key insight that signals strong problem‑solving skills.