Largest Number

Try It Yourself

Use the editor below to order number strings by which concatenation produces the larger prefix. Comparing a and b requires comparing a + b with b + a.

Submit your implementation when it passes the examples. Handle shared prefixes and collapse an all-zero result to one zero.

Largest Number

mediumSorting · Custom Comparator35 minLC 179

Problem

Arrange a list of non-negative integers so their decimal strings form the largest possible number.

Return the result as a string. If every value is zero, return a single zero.

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] ≤ 1,000,000,000

0 attempts

Solution

Convert every number to a string and merge-sort using a custom comparison. Place a before b when a + b is lexicographically greater than b + a.

Join the sorted strings. If the first string is zero, every value must be zero, so return a single zero.

function largestNumber(nums) {
  function comesFirst(first, second) {
    return first + second >= second + first;
  }

  function merge(left, right) {
    const result = [];
    let first = 0;
    let second = 0;

    while (first < left.length && second < right.length) {
      if (comesFirst(left[first], right[second])) {
        result.push(left[first++]);
      } else {
        result.push(right[second++]);
      }
    }

    return result.concat(left.slice(first), right.slice(second));
  }

  function mergeSort(values) {
    if (values.length <= 1) return values;
    const middle = Math.floor(values.length / 2);
    return merge(
      mergeSort(values.slice(0, middle)),
      mergeSort(values.slice(middle)),
    );
  }

  const ordered = mergeSort(nums.map(String));
  return ordered[0] === "0" ? "0" : ordered.join("");
}

Big O notation

Measure	Complexity	Explanation
Time	`O(n log n · k)`	Merge sort performs O(n log n) comparisons of strings up to k digits long.
Auxiliary space	`O(n · k)`	The string values and merge buffers require linear storage.