TRT
Sign in
mediumCoreLeetCode#custom comparator

Largest number

Arrange numbers so their concatenation is as large as possible, using a custom comparator that defines a valid total order.

The Runtime Theory Team1 min read
Taught inStability and what libraries usePro — members onlyA stable sort keeps equal elements in their original order, which is what makes sorting by several keys work. Here is which library sorts are stable, what algorithms they really are, and how to write comparators that don't break them.
Solve it

Solving happens on the judge — come back and mark it done

Sample cases

innums = [10, 2]

out"210"

innums = [3, 30, 34, 5, 9]

out"9534330"

innums = [0, 0]

out"0"

Given a list of non-negative integers, arrange them so that they form the largest number when concatenated, and return it as a string.

Before you code

Sorting by numeric value fails ([10, 2] should give "210"), and sorting the strings in reverse lexicographic order fails too ([3, 30]: "330" beats "303"). The right order compares two numbers by which concatenation is bigger.

Hints

  1. Convert to strings. Put a before b when a + b > b + a as strings.
  2. That comparison is a valid total order (it is transitive), which is what a sort requires. Convince yourself with 3, 30 and 34.
  3. In Python, use functools.cmp_to_key; in Java, a Comparator<String>.
  4. If the result starts with "0", every number was 0: return "0", not "00".

Production & complexity notes

When solving Largest number on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Stability and what libraries use to reinforce the underlying pattern.

What it practices

Writing a comparator that defines a consistent order, from Stability and what libraries use.

More practice in this track

hard · dsaDesign a skip listmedium · dsaDesign a bounded blocking queueeasy · dsaRange sum query: immutable

Not started

Sign in to save your learning progress.

Sign in to save