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. Since the result can be extremely large, it must be returned as a string rather than a numeric value.

Approach 1: Custom Sorting Using Concatenation Comparison (Greedy + Sorting) (Time: O(n log n * k), Space: O(n))

The key insight is that normal numeric sorting does not work. Instead, compare two numbers a and b by checking which concatenation produces a larger string: ab or ba. If ab > ba, then a should appear before b in the final order. This turns the problem into a custom comparator for sorting.

Convert all numbers to strings so concatenation is easy. Then sort the array using the comparator that compares a+b with b+a. After sorting in descending order of this rule, join all strings to form the final result. A small edge case appears when the largest element becomes "0" after sorting; this means every number is zero, so the correct output is simply "0" instead of multiple zeros.

This greedy ordering works because every local comparison ensures the globally optimal prefix for the final number. The algorithm is dominated by sorting, which performs O(n log n) comparisons, and each comparison takes up to O(k) time where k is the average digit length.

Approach 2: Custom Comparator Using Heap (Greedy + Heap) (Time: O(n log n * k), Space: O(n))

Another way to enforce the same ordering rule is to push elements into a priority queue (max‑heap) that uses the same concatenation comparison logic. Instead of sorting the entire array at once, repeatedly extract the element that should appear next in the final number.

Insert all numbers (as strings) into a heap where the comparator prioritizes the string that forms the larger concatenated value when paired with others. Each pop operation gives the next best candidate for the final string. Append popped elements sequentially to build the result.

This approach still relies on the same greedy principle but replaces sorting with a heap from array elements. The complexity remains O(n log n * k) because each insertion and removal from the heap costs O(log n), and the comparator still performs string concatenation comparisons.

Recommended for interviews: The custom sorting approach is the standard and expected solution. It demonstrates understanding of greedy ordering and custom comparators. Interviewers usually want to see the insight that comparing ab vs ba determines the correct order. The heap version works but is rarely necessary unless the problem specifically requires incremental extraction.