Largest Number

The problem. Given a list of non-negative integers, arrange them so that, written one after another, they form the largest possible number. Return it as a string (it may be too big for any integer type).

Example

nums = [10, 2]            ->  "210"
nums = [3, 30, 34, 5, 9]  ->  "9534330"
nums = [0, 0]             ->  "0"

The idea: compare by concatenation

Numeric order doesn't work (9 must come before 30), and neither does plain string order ("3" vs "30" is ambiguous). The right question for any two values a and b is: which order of the two makes the bigger number? Compare the strings a + b and b + a — they have the same length, so comparing them as strings compares them as numbers. Put a first if a + b is bigger.

This comparison is consistent (transitive), so a normal sort with it produces an order where every neighbouring pair is in its best order — and that is the largest number overall. One last detail: if the biggest piece is "0", every value is 0, and the answer is "0", not "000".

1. Brute force: try every order

1function largestNumber(nums) {2  const strs = nums.map(String);3  let best = "";4  const used = new Array(strs.length).fill(false);5  const build = (cur, count) => {6    if (count === strs.length) {7      if (cur > best) best = cur;               // same length, so string order is number order8      return;9    }10    for (let i = 0; i < strs.length; i++) {11      if (used[i]) continue;12      used[i] = true;13      build(cur + strs[i], count + 1);14      used[i] = false;15    }16  };17  build("", 0);18  return best[0] === "0" ? "0" : best;19}

Time O(n! · n·k), space O(n·k). Every one of the n! orders is built and compared — fine for 8 values, hopeless for 100.

2. Sort with the concatenation comparator

1function largestNumber(nums) {2  const strs = nums.map(String);3  strs.sort((a, b) => (b + a > a + b ? 1 : b + a < a + b ? -1 : 0));   // a first if a+b is the bigger number4  if (strs[0] === "0") return "0";                                     // every value was 05  return strs.join("");6}

Time O(n log n · k), space O(n·k) for numbers of up to k digits: each comparison builds two strings of length up to 2k.

Comparing the approaches

Edge cases to test

Variations